Computing square roots implies factoring $n = pq$

Question

I'm proving that computing square roots in $\mathbb{Z}_{pq}$ implies factoring $n = pq$ with $p,q$ primes. The solution give you an algorithm:

repeat
1. pick y from {1,...,n-1}
2. x = y^2 mod n
3. y' = random square root of x
until y' != y and y' != - y mod n

Basically the algorithm calculates the four square roots of some number x and then takes $p = gcd(y'-y,n)$. But I'm stuck at this point. Why can we guarantee that $p = gcd(y'-y,n)$?

What my note say is that $y − y'$ is zero modulo one of the two factors but not modulo the other.

Answer 1

Let $p$ and $q$ be distinct primes.

Suppose you have found two numbers $a, b$ such that $$\tag{formula} a^{2} \equiv b^{2} \pmod{n}, $$ but $$\tag{assumption} a \not\equiv \pm b \pmod{n}. $$ The first equation tells you that $$ n \mid a^{2} - b^{2} = (a - b) (a + b). $$ Consider $d = \gcd(n, a - b)$. As a divisor of $n$, it could be $1, p, q, n$. If it is $p, q$ we have factored $n$. So can we exclude it is $1$ or $n$?

If $\gcd(n, a - b) = n$, then $n \mid a - b$, so $a \equiv b \pmod{n}$, against (assumption).

If $\gcd(n, a - b) = 1$, then (formula) yields $n \mid a + b$, so $a \equiv -b \pmod{n}$, against (assumption).

Answer 2

It's not actually guaranteed to work out. However, there are four square roots of x, and two of them will produce a factor. One can see this by applying the Chinese Remainder Theorem.

Answer 3

Normally, we take $p \neq q$ so that they are relatively prime.

Notice you have $(y')^2 \cong y^2 \cong x \pmod{n}$. But this means $$ (y'-y)(y'+y) \cong (y')^2 - y^2 \cong x - x \cong 0 \pmod{n}. $$

So $y'-y$ is a factor of a multiple of $n$, call it $kn$. If you are a little lucky, the $\gcd(|y'-y|,n)$ gives a nontrivial factor of $n$. If you are unlucky, $y'-y$ only divides $k$, giving no information about $n$. (Of course, one might try the other factor above, $y'+y$, in the unlucky case.)

Note that $y$ and $y'$ are in the interval $[1,n-1]$, so $y' - y$ is in the interval $[1-(n-1), (n-1)-1] = [2-n,n-2]$, so can never be as large as $n$. The factors of $n$ are $\{1,p,q,n\}$, and the $\gcd$ can only give you $1, p, q$ (because as just observed, it cannot give you $n$). The nontrivial factors are $p$ and $q$. So if you've been a little lucky, your $\gcd$ gave you $p$ or $q$.

Say $\gcd(|y'-y|,n) = p$, then $p$ divides $y'-y$ and $y'-y \cong 0 \pmod{p}$. Since $p$ and $q$ are relatively prime, $y' - y \not\cong 0 \pmod{q}$. The same two sentences hold with $p$ and $q$ swapped.

Answer 4

Hint $\ $ It is a special case of the following

Theorem $\;$ One may factor $\rm m>1\:$ given a polynomial with more roots mod $\rm\: m\:$ than its degree, viz. suppose that, mod $\rm m,\;$ a polynomial $\rm\: f(x)\ne 0\:$ has degree $\rm\:n\:$ but has $\rm\:n\!+\!1 \:$ distinct roots $\rm\:r_{\,i}.\:$ Then one of $\rm\;gcd(m,\:r_{\:i} - r_{\:j}),\; i\ne j \:$ must yield a nontrivial factor of $\rm\:m.\;$ For if that failed, then all of the gcds must be $1, \:$not $\rm\;m, \;$ since $\rm\; i\ne j\,\Rightarrow\, r_{\:i} \not\equiv r_{\:j}\ (mod\ m). \,$ Induction using Factor Theorem yields $\rm\;f(x) = (x-r_1)\cdots(x-r_{n+1})\; g(x),\;\; g(x) \ne 0 \;\;$ contra $\rm\;\:\deg\: f = n. \,$