Alice is living in Anchorage and Bob is living in Baltimore. A friend, not realizing that they are no longer together, leaves them a car in his will. How do they decide who gets the car? Bob phones Alice and says he’ll flip a coin. Alice chooses “Tails” but Bob says “Sorry, it was Heads.” So Bob gets the car.

For some reason, Alice suspects Bob might not have been honest. (Actually, he told the truth; as soon as she called tails, he pulled out his specially made two-headed penny so he wouldn’t have to lie.) She resolves that the next time this happens, she’ll use a different method. So she goes to her local cryptologist, who suggests the following method.

Alice chooses two large random primes $p$ and $q$, both congruent to 3 mod 4. She keeps them secret but sends the product $n=pq$ to Bob. Then Bob chooses a random integer $x$ and computes $y\equiv x^2(\mathrm{m}\mathrm{o}\mathrm{d}n)$. He keeps $x$ secret but sends $y$ to Alice. Alice knows that $y$ has a square root mod $n$ (if it doesn’t, her calculations will reveal this fact, in which case she accuses Bob of cheating), so she uses her knowledge of $p$ and $q$ to find the four square roots $\pm a\text{,}\pm b$ of $y(\mathrm{m}\mathrm{o}\mathrm{d}n)$ (see Section 3.9). One of these will be $x$, but she doesn’t know which one. She chooses one at random (this is the “flip”), say $b$, and sends it to Bob. If $b\equiv \pm x(\mathrm{m}\mathrm{o}\mathrm{d}n)$, Bob tells Alice that she wins. If $b\cancel{\equiv }\pm x(\text{mod}n)$, Bob wins.

But, asks Alice, how can I be sure Bob doesn’t cheat? If Alice sends $b$ to Bob and $x\equiv \pm a(\text{mod}n)$, then Bob knows all four square roots of $y(\text{mod}n)$, so he can factor $n$. In particular, $gcd(x-b\text{,}n)$ gives a nontrivial factor of $n$. Therefore, if it is computationally infeasible to factor $n$, the only way Bob could produce the factors $p$ and $q$ would be when his value of $x$ is not plus or minus the value of $b$ that Alice sends. If Alice sends Bob $\pm x$, Bob has no more information than he had when Alice sent him the number $n$. Therefore, he should not be able to produce $p$ and $q$ in this case. So Alice can check that Bob didn’t cheat by asking Bob for the factorization of $n$.

What if Alice tries to cheat by sending Bob a random number rather than a square root of $y$? This would surely prevent Bob from factoring $n$. Bob can guard against this by checking that the square of the number Alice sends is congruent to $y$.

Suppose Alice tries to deceive Bob by sending a product of three primes. Of course, Bob could ask Alice for the factorization of $n$ at the end of the game; if Alice produces two factors, they can be quickly checked for primality. But Bob shouldn’t worry about this possibility. When $n$ is the product of three distinct primes, there are eight square roots of $y$. Therefore, up to sign there are four choices of numbers for Alice to send. Each of the three wrong choices will allow Bob to find a nontrivial factor of $n$. So Alice would decrease her chances of winning to only one in four. Therefore, she should not try this.

There is one flaw in this procedure. Suppose Bob decides he wants to lose. He can then claim his value of $x$ was exactly the value that Alice sent him. Alice cannot dispute this since the only information she has is the square of Bob’s number, which is congruent to the square of her number. There are other procedures that can prevent Bob from trying to lose, but we will not discuss them here.

Finally, we should mention that it is not difficult to find primes $p$ and $q$ that are congruent to 3 mod 4. The density of primes congruent to 1 mod 4 is the same as the density of primes that are 3 mod 4. Therefore, find a random prime $p$. If it is not 3 mod 4, try another. This process should succeed quickly. We can find $q$ similarly.