How to Flip a Coin by Phone

Which player gets to go first? Who washes the dishes and who dries them? Sometimes it’s useful to settle disputes between two sides using a coin toss. It’s easy to do. One person guesses the result of the coin toss out loud, and another person tosses the coin. If the first person is right, they win, and if not, the other person wins. Without a fake coin or some serious sleight of hand, cheating is impossible.

However, this doesn’t work if the two people are in different places, and talking over the phone. This could happen if they want to make a decision ahead of time, like who should cook dinner and who should bring dessert. Or in a divorce settlement, where two people can’t bear to speak face to face. Luckily, a little maths can help out.

First things first, we need to know about simple number systems which are a little different from the ordinary one. Imagine breaking off a bit of the number line, and bending it into a circle so that it wrapped around. With this ‘number circle’, if you keep adding one to a number, you eventually get back to where you started. This is called modular arithmetic, and it’s just like adding together numbers on an analogue clock face. When we work with a clock, we ‘loop around’ back to zero when we reach 12, and this is called working modulo 12.

clockface1

Another way of thinking about this is that all numbers which are exactly 12 apart are treated the same. For example, 3 multiplied by 5 is equal to 15, which is the same as 3 modulo 12. Or 4 squared is equal to 16 which is the same as 4 modulo 12. We can even solve simple equations like x + 5 = 3 (modulo 12). We can sometimes take square roots (a previous sentence shows that the square root of 4 modulo 12 is 4) but not all numbers have a square root.

We need two more ingredients. Our first key fact is that if we work modulo a certain type of prime number, then there is an extremely easy method for calculating square roots. The second key fact is that if we have a simple equation like x = a (modulo N), where N = p*q, a product of two different prime numbers, there is a way to change this into two simple equations modulo p and modulo q. If we solve these two equations, we can reverse the process and find a solution to the original equation modulo N. This is possible due to a piece of maths called the Chinese Remainder Theorem.

The whole point of this is that if you know p and q, there is an easy method for calculating square roots modulo N, but if you don’t know p and q, this problem is considered to be extremely difficult for large values, and no efficient method for solving it is known. Most numbers modulo N have 4 different square roots, x, y, -x and -y.

Now we’re ready. Let’s call our two characters Adam and Bella. Here’s what happens (as in this example):

  1. Adam chooses prime numbers p and q, and multiplies them together to get N. He tells Bella N over the phone. Adam chooses p and q to be extremely large so that Bella cannot feasibly find them from N.
  2. Bella chooses x between 0 and N, so that x and N have a highest common factor of 1 (this is for technical reasons, to ensure 4 square roots). She calculates the value of x squared modulo N, which we call b. She tells Adam b.
  3. Adam calculates the four square roots of b modulo N. These are x, y, -x and -y. He chooses one of the pairs {x,-x} or {y,-y}, and tells it to Bella.
  4. If Adam chooses {y,-y}, Bella wins, and she proves it easily by telling Adam x, which she would not have been able to find unless she chose it in step 2, since she does not know p and q.
  5. If Adam chooses {x,-x}, then he wins. Bella cannot find y, so she cannot trick Adam by telling him y.

In Step 2, when Bella tells Adam the value of b, she has committed to her choice, x. The only other values which give b when you square them modulo N are -x, y and -y. Changing to -x has no effect, and Bella does not know the value of y, so it is extremely unlikely that she will successfully trick Adam by changing her value in step 4 or 5. So this step is similar to ‘calling’ the outcome before a coin toss; you pick an outcome and commit to it.

Note that in step 3, Adam has no motivation for picking a particular pair, because he has no information about whether Bella is more likely to have chosen the x pair or the y pair. In fact, as fair as he can tell, either pair is equally likely. So Adam and Bella each have a 50% chance of winning, just like a coin toss.  Therefore this step corresponds to the physical flipping of the coin.

coin-flip3

Once you get past the mathematics required, this really isn’t so different from a real-world coin-toss. It has all of the essential features, but is more powerful as it can be carried out from a distance, using numbers and their properties to replace what is usually done by sight. And without some serious mathematical sleight of hand, cheating is impossible.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s