Factorization from distinct square roots modulo a semiprime

If $N=pq$ and $x^2\equiv y^2(\mathrm{mod}N)$ while $x\not\equiv \pm y(\mathrm{mod}N)$, thenand $\gcd (x-y,N)$ is a nontrivial factor of $N$.

If a purported authentication service returns a square root of every chosen square modulo a Rabin modulus, a verifier who knows one root obtains a different root with substantial probability and can factor the modulus. Repeating the challenge therefore reveals the private key.