Factoring product of two primes from solutions of congruence The algorithm purposed to play a fair game of heads or tails over the phone given here claims that knowing the four solutions to 
$$ x^2 \equiv a^2 \pmod n$$ would allow us to factor $n$ where $n$ is a product of two unknown primes $p,q$ and $\gcd(a, n) = 1$. However, I am not seeing why this would be true. Can someone please explain? 
 A: Let $a_p$ be a square root of $a$ modulo $p$, and let $a_q$ be a square root of $a$ modulo $q$. The four square roots are given by numbers $x,y,z,w$ such that:


*

*$x \equiv a_p \pmod{p}$ and $x \equiv a_q \pmod{q}$.

*$y \equiv a_p \pmod{p}$ and $y \equiv -a_q \pmod{q}$.

*$z \equiv -a_p \pmod{p}$ and $z \equiv a_q \pmod{q}$.

*$w \equiv -a_p \pmod{p}$ and $w \equiv -a_q \pmod{q}$.


If you look at $x-y$, for example, then you find that $x-y \equiv 0 \pmod{p}$ and $x-y \equiv 2a_q \pmod{q}$. This means that $x-y$ is divisible by $p$ but not by $q$, and so $\mathrm{gcd}(x-y,n) = p$.
A: The four solutions are of the shape $x\equiv \pm b\pmod{pq}$ and $x\equiv \pm c\pmod{pq}$.  
There are only two solutions modulo $p$. So $b\equiv \pm c\pmod{p}$. It follows that either $b-c\equiv 0\pmod{p}$ or $b+c\equiv 0\pmod{p}$. 
Thus one of $\gcd(m,b-c)$ or $\gcd(m,b+c)$ is equal to $p$, and the other is equal to $q$. The gcd can be computed cheaply using the Euclidean algorithm.
A: Hint $\ $ We can split $\rm n>1\,$ into nontrivial factors by a quick gcd calculation if we are given a nonzero polynomial having more roots $\,r_i\,$ mod $\rm\, n\,$ than its degree. Namely, one of $\,\gcd(n,\,r_i-r_j),\ i\neq j\,$ yields a proper factor of $\,n.\,$ See here for details.
