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]