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