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 [EMAIL PROTECTED]
