= Square-root oracle reduction for Rabin encryption
{c}
{title2=$\mathbb P(y\not\equiv\pm x\bmod N)=1/2$}
For $N=pq$ with distinct odd primes, choose a uniform unit $x$ and give only $x^2\bmod 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.
Back to article page
