[proofplan] The forward direction follows from the [constructive square-root algorithm mod $p$](/theorems/1682) and the [Chinese Remainder Theorem](/theorems/???), which together decrypt in polynomial time given the primes. For the reverse direction we turn any square-root oracle into a factoring algorithm via a Monte-Carlo procedure: sample $x$ uniformly at random from $(\mathbb{Z}/N\mathbb{Z})^\times$, query the oracle on $c = x^2 \bmod N$, and compare its output $y$ with $\pm x$. Using [the four-solution structure](/theorems/1683), with probability exactly $1/2$ the oracle's output is neither $x$ nor $-x$, making $\gcd(N, x - y)$ a non-trivial factor of $N$. Independent retries drive the failure probability to $2^{-r}$, giving a Las Vegas factoring algorithm. [/proofplan]

[step:Decrypt in polynomial time given the factorisation $N = pq$]Assume $p, q$ are known. Because $p, q$ are odd primes the theorem [square root modulo a prime $p \equiv 3 \pmod 4$](/theorems/1682) (and, for the general case $p \equiv 1 \pmod 4$, the Tonelli-Shanks algorithm) allows us to compute integers $m_p, m_q$ with \begin{align*} m_p^2 \equiv c \pmod{p}, \qquad m_q^2 \equiv c \pmod{q}, \end{align*} in deterministic polynomial time. The Chinese Remainder Theorem then produces, in polynomial time, the unique residue $m \bmod N$ with $m \equiv m_p \pmod p$ and $m \equiv m_q \pmod q$; by the [count of square roots modulo a semiprime](/theorems/1683), the four sign combinations $(\pm m_p, \pm m_q)$ yield the full set of four square roots of $c$ modulo $N$. Hence decryption is polynomial-time given the factorisation.[/step]

[guided]The forward direction is the existence of an efficient decryption algorithm when $p$ and $q$ are known. The building blocks are: 1. **Per-prime square roots.** For a prime $p$ and a quadratic residue $c \bmod p$, computing a square root modulo $p$ is in deterministic polynomial time. When $p \equiv 3 \pmod 4$, theorem 1682 gives the explicit formula $m_p \equiv c^{(p+1)/4} \pmod p$. When $p \equiv 1 \pmod 4$, Tonelli-Shanks also runs in expected polynomial time (and is deterministic conditional on GRH). 2. **CRT lift.** Given $m_p, m_q$, the extended Euclidean algorithm computes integers $u, v$ with $u p + v q = 1$, and then $m := m_p v q + m_q u p \bmod N$ satisfies $m \equiv m_p \pmod p$ and $m \equiv m_q \pmod q$. This is polynomial in $\log N$. 3. **Completeness.** Theorem 1683 tells us that $c$ has exactly four square roots mod $N$ (when $\gcd(c, N) = 1$), and they are precisely the CRT lifts of $(\pm m_p, \pm m_q)$. So the algorithm finds all of them. The cost of each step is polynomial in $\log N$, so the whole decryption runs in polynomial time once $p, q$ are known.[/guided]

[step:Use a square-root oracle to split $N$ with probability $1/2$ per query]For the converse, suppose we are given an oracle $\mathcal{O}$ that, on input $c \in (\mathbb{Z}/N\mathbb{Z})^\times$ such that $c$ is a quadratic residue modulo $N$, returns some $y \in (\mathbb{Z}/N\mathbb{Z})^\times$ with $y^2 \equiv c \pmod N$. We construct a factoring procedure. Sample $x$ uniformly at random from $(\mathbb{Z}/N\mathbb{Z})^\times$ and compute $c := x^2 \bmod N$. Then $c$ is a quadratic residue (witnessed by $x$), so $\mathcal{O}(c)$ returns some $y$ with $y^2 \equiv x^2 \pmod N$. Then \begin{align*} 0 \equiv y^2 - x^2 = (y - x)(y + x) \pmod{N}, \end{align*} so $N \mid (y - x)(y + x)$. Consider the four square roots of $c$ modulo $N$, which by [the count of square roots modulo a semiprime](/theorems/1683) are exactly $\{x, -x, z, -z\}$ for some $z \not\equiv \pm x \pmod N$. Under the Chinese Remainder Theorem isomorphism $(\mathbb{Z}/N\mathbb{Z})^\times \cong (\mathbb{Z}/p\mathbb{Z})^\times \times (\mathbb{Z}/q\mathbb{Z})^\times$, these are the four sign pairs $(\pm x_p, \pm x_q)$ with $x_p = x \bmod p$, $x_q = x \bmod q$. If $y \equiv \pm x \pmod N$, the oracle's output is $\pm x$ itself and $\gcd(N, x - y) \in \{N, N\}$ or $\{1, N\}$, giving no factor. Otherwise $y$ agrees with $x$ in exactly one CRT coordinate and disagrees in the other: say $y \equiv x \pmod p$ and $y \equiv -x \pmod q$. Then $p \mid y - x$ but $q \nmid y - x$; thus $\gcd(N, y - x)$ equals $p$, a non-trivial factor of $N$. The symmetric sign pattern gives $\gcd(N, y - x) = q$.[/step]

[guided]The strategy: we do not need the oracle to tell us a specific square root; we need it to tell us a "different" one. By [the count of square roots modulo a semiprime](/theorems/1683), every quadratic residue $c$ modulo $N$ has exactly four square roots, and they split into two pairs $\{x, -x\}$ and $\{z, -z\}$. The pairs $\{x, -x\}$ and $\{z, -z\}$ differ at exactly one of the two primes $p, q$ under the CRT decomposition. Two of the four square roots reveal no information: the output $\pm x$ is something we already know. But the other two, $\pm z$, are related to $x$ by disagreement at exactly one prime. Concretely, $z - x$ is divisible by exactly one of $p, q$, so $\gcd(N, z - x)$ is that prime. This is a non-trivial factor. Why do we sample $x$ uniformly at random? Because the oracle might be adversarial — it might even be designed to thwart our reduction. But conditional on the random variable $c = x^2 \bmod N$, the a posteriori distribution of $x$ over the four square roots of $c$ is uniform: given any sign vector $(\pm, \pm)$ in the CRT decomposition, the corresponding residue is equally likely to have been our original $x$. The oracle sees only $c$ (not $x$), so its output $y$ depends only on $c$. Therefore the event "$y \equiv \pm x \pmod N$" has conditional probability exactly $2/4 = 1/2$, and the event "$y \not\equiv \pm x \pmod N$" has conditional probability $1/2$. In the latter case, we factor. Why does $\gcd(N, y - x)$ equal $p$ or $q$? Because $N \mid (y - x)(y + x)$ but $N \nmid (y - x)$ (since $y \not\equiv x \pmod N$) and $N \nmid (y + x)$ (since $y \not\equiv -x \pmod N$). The prime factorisation $N = pq$ forces each of $p, q$ to divide exactly one of the factors $y - x, y + x$. Therefore $\gcd(N, y - x) \in \{p, q\}$ — neither $1$ nor $N$.[/guided]

[step:Prove the single-trial success probability is exactly $1/2$]Fix any oracle strategy $\mathcal{O}$. For $x$ sampled uniformly from $(\mathbb{Z}/N\mathbb{Z})^\times$, let $c = x^2 \bmod N$ and $y = \mathcal{O}(c)$. We show \begin{align*} \mathbb{P}\left[y \not\equiv \pm x \pmod N\right] = \tfrac{1}{2}. \end{align*} The map $x \mapsto x^2 \bmod N$ is a 4-to-1 surjection from $(\mathbb{Z}/N\mathbb{Z})^\times$ onto the set $\mathrm{QR}_N^* \subseteq (\mathbb{Z}/N\mathbb{Z})^\times$ of quadratic residues, by [the count of square roots modulo a semiprime](/theorems/1683). Thus $c$ has distribution uniform on $\mathrm{QR}_N^*$, and conditional on the value of $c$, the random variable $x$ is uniform over the four square roots $\{x, -x, z, -z\}$ of $c$. Since $\mathcal{O}(c) = y$ depends only on $c$ (not on which of the four preimages was the "true" $x$), the event $\{y \equiv \pm x \pmod N\}$ conditional on $c$ is determined by whether $x \in \{y, -y\}$, which has probability $2/4 = 1/2$. Averaging over $c$ preserves this probability. Thus each oracle query yields a non-trivial factor with probability exactly $1/2$.[/step]

[guided]The probabilistic analysis rests on the symmetry: the oracle cannot distinguish between the four preimages of $c$, because it is fed only $c$. Formally, the conditional distribution of $x$ given $c$ is uniform on the four square roots $\{x, -x, z, -z\}$, and the oracle's output $y$ is measurable with respect to $c$, so it is fixed once we condition on $c$. The event "no factoring" is $y \in \{x, -x\}$, which is a "$2$ out of $4$" event on the conditional distribution — probability exactly $1/2$. The event "success" is $y \in \{z, -z\}$, also probability $1/2$. This is an information-theoretic argument: the oracle simply does not have the information to pick the same side as our sampled $x$ with probability better than $1/2$. An adversarial oracle can try any strategy, but the symmetry caps its avoidance probability at $1/2$.[/guided]

[step:Amplify success probability via independent repetitions]Repeat the single-trial procedure with freshly independent samples $x^{(1)}, x^{(2)}, \ldots, x^{(r)}$. Each trial independently yields a non-trivial factor of $N$ with probability $1/2$ by the previous step. The probability that all $r$ trials fail to produce a factor is $(1/2)^r = 2^{-r}$. Hence for any desired failure probability $\varepsilon > 0$, choosing $r = \lceil \log_2(1/\varepsilon) \rceil$ suffices, and the total run time is $r$ times the cost of a single query plus gcd computation — polynomial in $\log N$ for polynomial $r$.[/step]

[guided]Independence is the key to amplification. The samples $x^{(1)}, \ldots, x^{(r)}$ are drawn independently and uniformly, so the events "$r$-th trial fails" are mutually independent. The product formula for independent events gives $\mathbb{P}[\text{all fail}] = \prod_{i=1}^{r} \mathbb{P}[i\text{-th fails}] = (1/2)^r$. To achieve $\mathbb{P}[\text{failure}] \le \varepsilon$, take $r \ge \log_2(1/\varepsilon)$. For $\varepsilon = 2^{-100}$ this is just $100$ trials — negligible compared to other cryptographic costs. This is the standard amplification principle for Monte Carlo algorithms. The overall algorithm is Las Vegas: we keep sampling until gcd returns a non-trivial divisor, and we always detect success (by checking $1 < \gcd(N, y - x) < N$). The expected number of trials is $2$.[/guided]

[step:Conclude the equivalence] The forward direction (factorisation $\Rightarrow$ decryption) is polynomial-time deterministic. The reverse direction (square-root oracle $\Rightarrow$ factorisation) is an expected-polynomial-time randomised reduction with failure probability $2^{-r}$ after $r$ trials. Hence breaking the Rabin cryptosystem — in the sense of being able to square-root modulo $N$ — is computationally equivalent to factoring $N$. [/step]