Square-root oracle reduction for Rabin encryption ($\mathbb{P}(y\not\equiv \pm x\mathrm{mod}N)=1/2$)

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.