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 [EMAIL PROTECTED]
Re: Factorization polynomially reducible to discrete log - known fact or not?
On 7/9/06, Ondrej Mikle [EMAIL PROTECTED] 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 [EMAIL PROTECTED]
Re: Factorization polynomially reducible to discrete log - known fact or not?
Charlie Kaufman wrote: 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 OK, I had the proof checked. I put it here: http://www.ms.mff.cuni.cz/~miklo1am/Factorization_to_DLog.pdf Warning: it may be not what you'd expect. First of all, it reduces the factorization to a discrete log in a group of unknown order (or put in another words: you'd need to factorize to learn the group order). It has been proven by V. Shoup that when group operation and the inverse are the only operations that can be done with group elements, then the best algorithm can be O(sqrt(n)), where n is the number of elements. I guess then the group of Z_N* (where N=pq) of unknown order qualifies for this if we don't want to use factorization (actually you can't compute inverse group operation here). In the light of this fact, is this proof of any use? Even if the proof is not useful, is the generator picking lemma (lemma 2) anything new? It states basically this: In any cyclic group of order n there is at least 1/log2(n) probability of picking a generator randomly and thus generator can be found in polynomial time with overwhelming probability of success. The only facts close to this lemma I found were: 1) Product phi(p_i)/p_i for consecutive primes p_i approaches zero as more and factors are added to the product (phi is Euler phi function). The lemma states a lower bound for the product. 2) If the generalized Riemann hypothesis is true, then for every prime number p, there exists a primitive root modulo p that is less than 70 (ln(p))^2. (http://en.wikipedia.org/wiki/Primitive_root_modulo_n) Charlie: Thanks for answering my second question which I have not asked yet :-) (the reduction in opposite direction). I'm also working on the opposite reduction, but I'm at best halfway through (and not sure if I am able to finish it). Last question: Joseph Ashwood mentioned someone who claimed to have algorithm for factorization and had only the reduction to DLP. Anyone knows where I could find the algorithm? Or maybe name of the person, so I could search the web. Thanks O. Mikle - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Factorization polynomially reducible to discrete log - known fact or not?
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]
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]
