Flipping a Coin by E-Mail

Each player secretly picks either

• two 150 digit prime numbers, or
• three 100 digit prime numbers

Then, each player sends the result (each a 300 digit number) to the other player via e-mail.

Notice that even with a very powerful computer, the receiving player can not factor the player's 300 digit number, nor even determine how many factors it has.

When both e-mails have been received, each player then announces to the other the factors which were multiplied to form the product. It is "easy" to check that the factors do indeed multiply to form the announced product, and that the factors are really prime (using a probabilitic primality test available in Maple or Mathematica, for example).

• If one number is the product of two prime factors and the other is the product of three prime factors, say the result is "tails."
• Otherwise (if both numbers have the same number of factors), say the result is "heads."