On 7/9/06, Ondrej Mikle <[EMAIL PROTECTED]> wrote:
I believe I have the proof that factorization of N=p*q (p, q prime) is polynomially reducible to discrete logarithm problem. Is it a known fact or not? I searched for such proof, but only found that the two problems are believed to be equivalent (i.e. no proof).
Take a look at this paper: http://portal.acm.org/citation.cfm?id=894497 Eric Bach "Discrete Logarithms and Factoring" ABSTRACT: "This note discusses the relationship between the two problems of the title. We present probabilistic polynomial-time reduction that show: 1) To factor n, it suffices to be able to compute discrete logarithms modulo n. 2) To compute a discrete logarithm modulo a prime power p^E, it suffices to know It mod p. 3) To compute a discrete logarithm modulo any n, it suffices to be able to factor and compute discrete logarithms modulo primes. To summarize: solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes." Max --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
