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

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'.

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

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