David Wagner wrote:
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^*.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.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.
Actually, you can never get a generator of Z_N^* unless p=q, because when p != q, it is not a cyclic group (this error was in my proof, too). Though with great probability you get an element of high order. It is enough doing lcm() to get the phi(N) and it will run in polynomial time.
I noted the fact IFP(N) to DLOG in Z_N^* is really mentioned in Handbook of Applied Crypto, but without proof or algorithm, just two lines (I guess that's why I missed/didn't remember it).
--------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
