### Re: Factorization polynomially reducible to discrete log - known fact or not?

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

### Re: Factorization polynomially reducible to discrete log - known fact or not?

The algorithm is very simple: 1. Choose a big random value x from some very broad range (say, {1,2,..,N^2}). 2. Pick a random element g (mod N). 3. Compute y = g^x (mod N). 4. Ask for the discrete log of y to the base g, and get back some answer x' such that y = g^x' (mod N). 5. Compute x-x'.

### Re: Factorization polynomially reducible to discrete log - known fact or not?

Charlie Kaufman wrote: I believe this has been known for a long time, though I have never seen the proof. I could imagine constructing one based on quadratic sieve. I believe that a proof that the discrete log problem is polynomially reducible to the factorization problem is much harder and

### RE: Factorization polynomially reducible to discrete log - known fact or not?

I believe this has been known for a long time, though I have never seen the proof. I could imagine constructing one based on quadratic sieve. I believe that a proof that the discrete log problem is polynomially reducible to the factorization problem is much harder and more recent (as in