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]