David Wagner wrote:

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 themultiplicative 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.

`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]