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.


OK, I had the proof checked. I put it here:

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." (

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.

  O. Mikle

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

Reply via email to