Computing square roots implies factoring $n = pq$ 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.
 A: 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. \,$
A: 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).
A: 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.
A: 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.
