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 x^{2} = a (mod p). For assume that there is such an x. Then (using that x^{4p'+2} = 1 (mod p) by Euler's theorem)

(±a^{p'+1})^{2} = x^{4p'+4} = x^{2} = a (mod p)
so the solutions are ±a^{p'+1}.

If p = 4p' + 3, q = 4q' + 3 are primes then it is also easy to solve the congruence x^{2} = a (mod pq), for this implies

/ x^{2} = a (mod p)

\ x^{2} = a (mod q)

<=>

/ x = ±a^{p'+1} (mod p)

\ x = ±a^{q'+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 s^{2} = t^{2} (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 x^{2} 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 x^{2} = 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 x^{2} = y^{2} (mod n) to factorise n and thereby prove to Alice that he has won.