Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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$.
