Suppose you have a random algorithm $S(y, n)$ that can, with cost $C$ and success probability $\varepsilon$, compute a square root of a random quadratic residue $y$ modulo a product $n = pq$ of random primes.  (For example, this algorithm can be derived from a Rabin signature forger in the random oracle model.)  Can you use $S$ as a subroutine in a random algorithm $F(n)$ to factor $n$?  Yes!

Define the algorithm $F(n)$ as follows:

1. Pick $0 \leq x < n$ uniformly at random.
2. Compute $y = x^2 \bmod n$.
3. Compute $\xi = S(y, n)$.
4. If $x \pm \xi \equiv 0 \pmod n$, fail; otherwise return $\gcd(x \pm \xi, n)$.

The cost of this algorithm is one random choice between $n$ possibilities, one squaring modulo $n$, $C$ (the cost of $S$), and one gcd with $n$—so this algorithm costs little more than any algorithm to compute square roots.  What's the success probability?

Step 1 always succeeds.  Step 2 always succeeds.  Step 3 succeeds with probability $\varepsilon$.  Step 4 is the interesting step.

 - Every quadratic residue, like $y$, has up to _four_ distinct square roots modulo $n$: two square roots modulo $p$, and two square roots modulo $q$.  If we can find two distinct roots $x$ and $\xi$ of $y$—distinct by more than just sign—then since $x^2 \equiv y \pmod n$ and $\xi^2 \equiv y \pmod n$, we have $x^2 \equiv \xi^2 \pmod n$ with the nontrivial _integer_ equation $$k n = x^2 - \xi^2 = (x + \xi) (x - \xi)$$ for some $k$.  And further, we know that $n$ cannot divide $x \pm \xi$ since $x \pm \xi \not\equiv 0 \pmod n$.  Thus $$n \mid (x + \xi) (x - \xi), \quad \text{but} \quad n \nmid x \pm \xi.$$  Consequently, since integers have unique factorization, $n = pq$ must share _some but not all_ factors with $x \pm \xi$, so $\gcd(x \pm \xi, n)$ returns a nontrivial factor in the case that $x \pm \xi \not\equiv 0 \pmod n$.

There's about a 1/2 chance that $S$ returns $\pm x$ so that $x \pm \xi \equiv 0 \pmod n$: $S$ can't know _which_ of the four square roots $x$ of $y$ we began with even if it wanted to thwart us.  So step 4 succeeds with probability about 1/2, and the algorithm succeeds with probability about $\varepsilon/2$.  If we retry until success, the expected number of trials to factor $n$ is about 2.

---

This proof was published by Michael Rabin in 1979 in a technical report on a [proposal for a public-key signature scheme][rabin1979sigs] to justify its security in relation to factoring.  Unlike the trivially breakable [RSA proposal][rsa1978digsigpubkey] ([paywall-free](https://people.csail.mit.edu/rivest/Rsapaper.pdf)) that preceded it, Rabin's signature scheme was the first signature scheme in history that still stands under modern scrutiny, provided suitable parameter sizes are chosen, through the use of hashing not merely as a method to compress large messages but as an integral part of security to destroy the structure of messages.  Today, textbooks and Wikipedia consistently misrepresent Rabin's cryptosystem as a broken encryption scheme or as a broken hashless signature scheme, as if almost nobody has ever bothered to read the paper.

Whether Rabin was the _first_ to publish a proof that square roots enable factoring, I don't know—Fermat wrote [a letter to Mersenne in about 1643][fermat1643sqdiff] observing that finding a way to write $n$ as a difference of squares leads to factorization, so it seems likely that a number theorist before Rabin would have come upon the same incremental refinement that a modular square root _algorithm_ leads to a factoring _algorithm_.  But, then again, until the development of public-key cryptography in the 1970s, perhaps there would have been little interest in that observation without a square root algorithm in the first place, which obviously we didn't have then and still don't have now!

The same technique, alas, does not work to show that the RSA problem—inverting $x \mapsto x^e \bmod n$ when $\gcd(e, \phi(n)) = 1$—can't be much easier than factoring, because there is at most one $e^{\mathit{th}}$ root: by Bézout's identity, there exists some $d$ and $k$ such that $d e - k \phi(n) = \gcd(e, \phi(n)) = 1$, or $e d = 1 + k \phi(n)$, and so if $y \equiv x^e \pmod n$, then $$y^d \equiv (x^e)^d \equiv x^{ed} \equiv x^{1 + k\phi(n)} \equiv x \cdot (x^{\phi(n)})^k \equiv x \pmod n,$$ by Euler's theorem; consequently $x \mapsto x^e \bmod n$ is a bijection.

   [rabin1979sigs]: http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf "Michael C. Rabin, ‘Digitalized Signatures and Public Key Functions as Intractable as Factorization’, MIT LCS Tech Report, TR-212, 1979."
   [rsa1978digsigpubkey]: https://dl.acm.org/citation.cfm?doid=359340.359342 "R.L. Rivest, A. Shamir, and L. Adleman, ‘A Method for Obtaining Digital Signatures and Public-Key Cryptosystems’, Communications of the ACM 21(2), 120–126, February 1978."
   [fermat1643sqdiff]: https://archive.org/details/oeuvresdefermat00fermgoog/page/n275 "Pierre de Fermat, Letter LVII, fragment of a letter to Marin Mersenne of about 1643, Œuvres de Fermat, vol. 2, pp. 256–258."