[30314] in cryptography@c2.net mail archive
RE: Factorization polynomially reducible to discrete log - known
daemon@ATHENA.MIT.EDU (Charlie Kaufman)
Mon Jul 10 16:50:24 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: Charlie Kaufman <charliek@exchange.microsoft.com>
To: Ondrej Mikle <ondrej.mikle@gmail.com>,
"cryptography@metzdowd.com" <cryptography@metzdowd.com>
Date: Mon, 10 Jul 2006 13:41:13 -0700
In-Reply-To: <44B15745.5070208@gmail.com>
I believe this has been "known" for a long time, though I have never seen t=
he proof. I could imagine constructing one based on quadratic sieve.
I believe that a proof that the discrete log problem is polynomially reduci=
ble to the factorization problem is much harder and more recent (as in some=
time in the last 20 years). I've never seen that proof either.
--Charlie
-----Original Message-----
From: owner-cryptography@metzdowd.com [mailto:owner-cryptography@metzdowd.c=
om] 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=3Dp*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 majordomo@metzdowd.com
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
