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

2006-07-12 Thread David Wagner
Ondrej Mikle 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? Be careful: when most people talk about the assumption that the discrete log problem being hard, they usually are

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

2006-07-12 Thread Max A.
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?

2006-07-12 Thread Peter Kosinar
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?

2006-07-11 Thread Ondrej Mikle
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?

2006-07-10 Thread Charlie Kaufman
to discrete log - known fact or not? Hello. 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

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

2006-07-09 Thread Ondrej Mikle
Hello. 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). I still might have