Re: Factorization polynomially reducible to discrete log - known fact or not?

2006-07-12 Thread Peter Kosinar

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.


Not exactly. Consider N = 3*7 = 21, phi(N) = 12, g = 4, x = 2, x' = 5. 
You'll only get a multiple of phi(N) if g was a generator of the 
multiplicative group Z_N^*.


Peter

--
[Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI)  [ICQ] 134813278

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


Re: Factorization polynomially reducible to discrete log - known

2006-07-12 Thread Peter Kosinar

Not exactly. Consider N = 3*7 = 21, phi(N) = 12, g = 4, x = 2, x' = 5.
You'll only get a multiple of phi(N) if g was a generator of the
multiplicative group Z_N^*.


When N is a large RSA modulus, there is a non-trivial probability that g
will be a generator (or that g will be such that x-x' lets you factor N).
The above is good enough for a polytime reduction.


You're absolutely right, although the probability actually does not depend 
on the size of the modulus (in fact, the provable lower bound on this 
probability goes down with size of the modulus), as it depends only on the 
factorization of phi(N) which, in turn, might depend on the process used 
to choose the factors of the modulus (e.g. sometimes-suggested approach of 
using Sophie-Germain primes creates abundance of generators; whereas some 
primorial-like construction might decrease it).


Peter

--
[Name] Peter Kosinar   [Quote] 2B | ~2B = exp(i*PI)   [ICQ] 134813278


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