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 more recent (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 to discrete log - known fact or 
not?

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 some error in the proof, so it needs to be checked by
someone yet. I'd like to know if it is already known (in that case there
would be no reason to bother with it).

Thanks
   O. Mikle

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Reply via email to