| | |
Claim: If $n = pq$, where $p$ and $q$ are primes congruent to $3\pmod{4}$, and $y$ is a number relatively prime to $n$ which has a square root $\pmod{n}$, then finding distinct solutions $x \equiv \pm a, \pm b$ to $x^2 \equiv y\pmod{n}$ is equivalent to factoring $n$.
Proof:
Clearly, if $x = \pm a, \pm b$ are the distinct four values of $x$ that solve $x^2 \equiv y\pmod{n}$, then $a^2 \equiv b^2\pmod{n}$.
This means that $pq \mid b^2 - a^2$. Consequently, since $p$ and $q$ are both prime, $p \mid b^2 - a^2$ and $q \mid b^2 - a^2$. Equivalently, $p \mid (b-a)(b+a)$ and $q \mid (b-a)(b+a)$.
As such, since $p$ is prime, we know $p \mid (b-a)$ or $p \mid (b+a)$. Similarly, since $q$ is prime, we know $q \mid (b-a)$ or $q \mid (b+a)$.
Importantly, $p$ and $q$ can't both divide $(b-a)$. Nor can they both divide $(b+a)$.To see this, note that if $p \mid (b-a)$ and $q \mid (b-a)$, then $pq \mid (b-a)$, so $a \equiv b \pmod{n}$, which violates the distinctness of $a$ and $b\pmod{n}$.
Similarly, if $p \mid (b+a)$ and $q \mid (b+a)$, then $pq \mid (b+a)$, so $-a \equiv b \pmod{n}$, which violates the distinctness of $-a$ and $b\pmod{n}$.
Consequently, one of two scenarios occurs:Once either $p$ or $q$ is known, the other is easy to find upon division into $n$.
As calculating the $gcd$ is fast, we have found a quick way to factor $n$ into $p$ and $q$.
On the flip side, if we know how to factor $n$ into the product of $p$ and $q$, then knowing $x^2 \equiv y\pmod{n}$ tells us $$x^2 \equiv y\pmod{p} \quad \textrm{ and } \quad x^2 \equiv y\pmod{q}$$ We can solve these individually since the moduli are primes congruent to $3\pmod{4}$, and then put the resulting congruences back together again using the Chinese Remainder Theorem to find $\pm a, \pm b$. (see exercises)