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]