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.

  • $\begingroup$ 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?" $\endgroup$
    – fgrieu
    Mar 5, 2015 at 7:49

2 Answers 2


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$?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.