Let be a primitive root for the prime . This means that the numbers yield all of the nonzero congruence classes mod .
Let be fixed and suppose has a solution . Show that must be even. (Hint: Write for some . Now use the fact that if and only if .) This shows that the nonzero squares mod are exactly , and therefore are the quadratic nonresidues mod .
Using the definition of primitive root, show that .
Use Exercise 15 in Chapter 3 to show that .
Let . Show that if is a quadratic residue and if is a quadratic nonresidue mod .
In the coin flipping protocol with , suppose Bob sends a number such that neither nor has a square root mod .
Show that cannot be a square both mod and mod . Similarly, cannot be a square mod both primes.
Suppose is not a square mod . Show that is a square mod .
Show that is a square mod one of the primes and is a square mod the other.
Benevolent Alice decides to correct Bob’s “mistake.” Suppose is a square mod and is a square mod . Alice calculates a number such that and and sends to Bob (there are two pairs of choices for ). Show how Bob can use this information to factor and hence claim victory.
Let be an odd prime. Show that if , then .
Let be an odd prime. Suppose and . Show that (Hint: Look at the proof of the Basic Principle in Section 9.3.)
Suppose Alice cheats when flipping coins by choosing . Show that Bob always loses in the sense that Alice always returns . Therefore, it is wise for Bob to ask for the two primes at the end of the game.