# Find the prime factorization in the DLP

Suppose we have $g^x \equiv h \pmod N$ Where $N = pq$ and $p$, $q$ are distinct primes. Also $(p-1)/2$ and $(q-1)/2$ are primes.

If we know what $x$, $g$ and $h$ are, is it possible for us to know what $p$ and $q$ are? I'm trying to find out but I'm running into closed doors.
I tried the following:
$gcd(p-1 , q-1) = 2$
$g^{(p-1)(q-1)/2} \equiv 1 \pmod {pq}$
so $1 \equiv h^{(p-1)(q-1)/2} \pmod {pq}$

Any help is appreciated.

• For the question "If we know what $x$, $g$ and $h$ are, is it possible for us to know what $p$ and $q$ are?", I doubt there is a positive answer $\;$ However another interesting question is: "If we knew a method to find $x$ such that $g^x\equiv h\pmod N$ given $(g,h)$, would it be possible for us to know what $p$ and $q$ are?" – fgrieu Mar 5 '15 at 7:49

As a hint, suppose we pick a random $h$, and compute $g = h^3 \bmod N$. We then find the minimal value $x$ where $g^x \equiv h \pmod{N}$ (and, yes, such an $x$ will exist, assuming $p, q > 7$).

What can we deduce from such a value of $x$?

• For this to work, $x$ must be $-3 \pmod {\phi (N)}$ right? – mike russel Mar 4 '15 at 14:41
• @mikerussel: Actually, $3^{-1}$, not $-3$. – poncho Mar 4 '15 at 14:45
• Okay so how does this help us retrieve $p$ and $q$? – mike russel Mar 4 '15 at 14:45
• @mikerussel: What is $3x-1 \bmod {(p-1)(q-1)/2}$ with good probability? – poncho Mar 4 '15 at 14:59
• We know $x = 3^{-1}$ so $3x-1= 0$ So $(p-1)(q-1)/2$ divides $3x-1$. – mike russel Mar 4 '15 at 15:02

Just knowing any such triple would not help at all. Reason:

Choose $g$ and $x$ arbitrarily, calculate $h$. Now you got such a triple, but it shouldn't help you factorize $N$, unless you have another interesting property.

If on the other hand you can somehow calculate roots (given $x$ and $h$, and then find $g$), then you can break RSA: Choose $x=e$, and your root algorithm finds the plaintext to a ciphertext.

If you can find square roots (and there are always 4 of them with $n=pq$), then you can actually factorize $N$, the attack basically works like the chosen ciphertext attack on Rabins encryption scheme: Choose $a$, calculate $a^2$, apply your algorithm to $a^2$ to find a square root. Since it only has $a^2$ as input, it will result in one of the four square roots, but not necessarily the one you started with. If the result is not $a$ or $-a$, then you can factorize $N$.