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

[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 majordomo at metzdowd.com