# Re: Factorization polynomially reducible to discrete log - known

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

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