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

2006-07-12 Thread David Wagner
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).

Re: Factorization polynomially reducible to discrete log - known

2006-07-12 Thread Peter Kosinar
Not exactly. Consider N = 3*7 = 21, phi(N) = 12, g = 4, x = 2, x' = 5. You'll only get a multiple of phi(N) if g was a generator of the multiplicative group Z_N^*. When N is a large RSA modulus, there is a non-trivial probability that g will be a generator (or that g will be such that x-x' lets

Re: Factorization polynomially reducible to discrete log - known

2006-07-12 Thread Ondrej Mikle
David Wagner wrote: 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

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
(as in sometime in the last 20 years). I've never seen that proof either. --Charlie -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Ondrej Mikle Sent: Sunday, July 09, 2006 12:22 PM To: cryptography@metzdowd.com Subject: Factorization polynomially reducible

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