= Solution
In the <Rabin cryptosystem>, the public key is $N=pq$, usually with distinct secret primes $p,q\equiv3\pmod4$. A message $m$ is encrypted as
$$
c\equiv m^2\pmod N.
$$
Knowing $p$ and $q$, the receiver finds the two square roots of $c$ modulo each prime and combines them by the Chinese remainder theorem, obtaining the four square roots modulo $N$; redundancy identifies the intended message.
Factoring $N$ plainly enables this decryption. Conversely, suppose an algorithm returns a square root of a chosen quadratic residue. Choose random invertible $x$, submit $x^2\bmod N$, and receive a root $y$. With probability at least $1/2$, $y\not\equiv\pm x\pmod N$; then
$$
\gcd(x-y,N)\quad\hbox{or}\quad\gcd(x+y,N)
$$
is a nontrivial factor. Thus decryption and factoring are equivalent up to a randomized polynomial-time reduction.
Back to article page
