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

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 majordomometzdowd.com

> 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.

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^*.

Peter

-- 
[Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI)  [ICQ]
134813278

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com