[30620] in cryptography@c2.net mail archive
Re: Factorization polynomially reducible to discrete log - known fact or not?
daemon@ATHENA.MIT.EDU (Max A.)
Wed Jul 12 09:48:50 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 12 Jul 2006 04:18:03 -0700
From: "Max A." <maxale@gmail.com>
To: "Ondrej Mikle" <ondrej.mikle@gmail.com>
Cc: cryptography@metzdowd.com
In-Reply-To: <44B15745.5070208@gmail.com>
On 7/9/06, Ondrej Mikle <ondrej.mikle@gmail.com> 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? I searched for such proof, but only found that the two problems
> are believed to be equivalent (i.e. no proof).
Take a look at this paper: http://portal.acm.org/citation.cfm?id=894497
Eric Bach "Discrete Logarithms and Factoring"
ABSTRACT: "This note discusses the relationship between the two
problems of the title. We present probabilistic polynomial-time
reduction that show: 1) To factor n, it suffices to be able to compute
discrete logarithms modulo n. 2) To compute a discrete logarithm
modulo a prime power p^E, it suffices to know It mod p. 3) To compute
a discrete logarithm modulo any n, it suffices to be able to factor
and compute discrete logarithms modulo primes. To summarize: solving
the discrete logarithm problem for a composite modulus is exactly as
hard as factoring and solving it modulo primes."
Max
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
