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$.

For $N=pq$ with distinct odd primes, choose a uniform unit $x$ and give only $x^2\mathrm{mod}N$ to an oracle returning any square root $y$. Conditional on this square, $x$ is uniform among four roots and independent of the oracle's choice. With probability one half, $y$ is not $\pm x$, and $\gcd (x-y,N)$ is a nontrivial factor. Thus full inversion of the squaring map yields randomized integer factorization; this reduction does not equate arbitrary partial leakage with full inversion.

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.