  ## Finding Certain Roots is Equivalent to Factoring

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:
• One possibility is that $p \mid (a-b)$ and $q \not\mid (a-b)$. However, this means that $gcd(a-b,n) = p$.
• The other possibility is that $p \not\mid (a-b)$ and $q \mid (a-b)$. However, this means that $gcd(a-b,n) = q$.

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)