First we need to establish a few results.

If p = 4p' + 3 is a prime then it is easy to solve the congruece x² = 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)² = x^4p'+4 = x² = 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² = a (mod pq), for this implies

/ x² = a (mod p)
\ x² = 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² = t² (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² 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² = 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² = y² (mod n) to factorise n and thereby prove to Alice that he has won.

• Alice and Bob
• phone
• number theory
• computer
• prime
• mod
• Euler's theorem
• Chinese remainder theorem
• product
• integer
• coprime
• concede
• prove

• congruece
• factorise