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

David Wagner daw at cs.berkeley.edu
Tue Jul 11 20:35:00 EDT 2006


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 referring to the
hardness of discrete logs modulo a large prime.  In contrast, you
seem to be talking about the hardness of discrete logs modulo an
RSA modulus.  Those two things are not the same.

It is well-known that if you can solve discrete logs modulo a RSA
modulus N in polytime, then you can factor N in polytime.  This is
a standard result that is well-known to anyone who studies this field.
If you've re-discovered this result, you haven't got anything new.

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'.  Note that x-x' is a multiple of phi(N), and
   it is highly likely that x-x' is non-zero.  It is well-known
   that given a non-zero multiple of phi(N), you can factor N in
   polynomial time.

There is no known proof that if you can factor N in polytime, you
can solve discrete logs modulo N in polynomial time.  (In practice,
if N is a 2048-bit RSA modulus that is a product of two 1024-bit
primes, if you can factor N, you can solve discrete logs modulo N
more efficiently by solving two discrete log problems modulo 1024-bit
prime numbers and then applying the Chinese remainder theorem.  But
the latter is still asymptotically superpolynomial.)

There is no known proof that if you can solve discrete logs modulo
a prime p in polytime, then you can factor a RSA modulus N in polytime.

There is no known proof that if you can factor a RSA modulus N in
polytime, then you can solve discrete logs modulo a prime p in polytime.

If you can solve any of the latter three problems, then you've got
something new, and many cryptographers will be interested.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list