In a solution to the problem of finding $q$ in

$$ c_1^{e_2}\cdot 5^{e_1e_2} - c_2^{e_1}\cdot 2^{e_1e_2} = q^{e_1e_2} \bmod n $$

it is given as:

$$ q = \gcd\big(c_1^{e_2}\cdot 5^{e_1e_2} - c_2^{e_1}\cdot 2^{e_1e_2}, n\big) $$

How can $q$ be found like that?

  • $\begingroup$ Without any clue about how $c_1$ and $c_2$ have been computed, it's hard to tell. Dumping homework here is not a good idea anyway. $\endgroup$ – fgrieu Apr 12 '20 at 9:55
  • $\begingroup$ @fgrieu updated with a link to the post, $c_1$ and $c_2$ are there. The post is very short $\endgroup$ – tasera Apr 12 '20 at 9:57

The way $c_1$ and $c_2$ have been obtained, algebra has shown that the quantity $z={c_1}^{e_2}\,5^{e_1\,e_2}-{c_2}^{e_1}\,2^{e_1\,e_2}$ is such that $z\equiv q^{e_1\,e_2}\pmod n$, where $n$ is an RSA modulus with $q$ one of the prime factors of $n$, $e_1$ and $e_2$ are RSA exponents valid for the modulus $n$.

From $n=p\,q$, we know that $q$ divides $n$.

From $z\equiv q^{e_1\,e_2}\pmod n$, and since $q$ divides $n$, we know that $z\equiv q^{e_1\,e_2}\pmod q$. Since neither $e_1$ nor $e_2$ are zero, it holds $q^{e_1\,e_2}\equiv0\pmod q$. Therefore, $z\equiv0\pmod q$, that is $q$ divides $z$.

Hence, $q$ is a common divisor of $n$ and $z$. With $n=p\,q$ with $p$ prime, it follows that one of the following holds:

  • $z=0$
  • $\gcd(z,n)$ is $q$
  • $\gcd(z,n)$ is $n$.

The way $z$ was constructed gives no particular reason to believe that $p$ divides $z$, and that's highly unlikely for a random integer. It follows that $\gcd(z,n)=q$ is the only likely possibility in the above three.

The quantity ${c_1}^{e_2}\,5^{e_1\,e_2}-{c_2}^{e_1}\,2^{e_1\,e_2}\bmod n$ can efficiently be computed from givens, and that allows to compute $\gcd(z,n)$ (since the first step of that can be to reduce $z$ modulo $n$), and thus allows to compute $q$.

  • $\begingroup$ I'm sure I'm missing some math here. Could you explain why "it follows that one of the following holds"? $\endgroup$ – tasera Apr 15 '20 at 12:55
  • $\begingroup$ @tasera: We proved that $q$ divides $z$. It is known that $n=p\,q$ with $p$ and $q$ primes. $z=0$ is a possibility matching the above. Otherwise, for $z\ne0$, we can define and compute $g=\gcd(z,n)$. Since $g$ divides $n$ by definition of $\gcd$, it is one of $1$, $p$, $q$, or $n$. Since $q$ divides $n$ and $z$, and $1<q$, we can't have $g=1$. If we had $g=p$, and $p\ne q$, both $p$ and $q$ would divides $z$, hence $n$ would divides $z$, hence $g\ge n$, thus $g\ne p$. That leaves $q$ and $n$ as the only possibilities for $g$. Thus one of $z=0$, $g=q$, $g=n$ holds, as stated in the answer. $\endgroup$ – fgrieu Apr 15 '20 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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