Alice and Bob are talking on the
phone. They want to play a game. One of them tosses a coin. Alice wins if it's heads, Bob if it's tails. The problem that arises is that the one who tosses the coin might be tempted to lie about the result in his/her own favour.
This is a situation we have all experienced, isn't it? Luckily
number theory has given us a way to replace mutual trust by
computers.
First we need to establish a few results.
If p = 4p' + 3 is a prime then it is easy to solve the congruece x2 = a (mod p). For assume that there is such an x. Then (using that x4p'+2 = 1 (mod p) by Euler's theorem)
(±ap'+1)2 = x4p'+4 = x2 = a (mod p)
so the solutions are ±ap'+1.
If p = 4p' + 3, q = 4q' + 3 are primes then it is also easy to solve the congruence x2 = a (mod pq), for this implies
/ x2 = a (mod p)
\ x2 = a (mod q)
<=>
/ x = ±ap'+1 (mod p)
\ x = ±aq'+1 (mod q)
which has four solutions ±s, ±t according to the Chinese remainder theorem.
If we know that n is a product of two primes and that s2 = t2 (mod n) then we can easily factorise n, using n | (s+t)(s-t). This would otherwise be difficult to do if n is large.
Now we can describe the protocol.
Alice chooses two large primes p = 4p' + 3, q = 4q' + 3. She multiplies them together and tells Bob the result n.
Bob then chooses an integer x, and checks that it is coprime to n. He then calculates the remainder of x2 when divided by n, and tells Alice the result r.
Alice now attempts to find the value of x. Since she knows the factorisation n = pq she can find the solutions ±x, ±y of x2 = r (mod n). She now chooses one of them, eg be tossing a coin, and tells it to Bob.
If Alice has picked x then Bob concedes. Otherwise he can use x2 = y2 (mod n) to factorise n and thereby prove to Alice that he has won.