Q: How can a toss be called over the phone (without requiring trust)?

A: A flips a coin. If the result is heads, A multiplies 2 prime numbers containing about 90 digits; if the result is tails, A multiplies 3 prime numbers containing about 60 digits. A tells B the result of the multiplication. B now calls either heads or tails and tells A. A then supplies B with the original numbers to verify the flip.

Consider what is involved in multiplying 90 digit numbers. Using the method of long multiplication that we all learned in grade school, you have maybe 90 or so strings of 90 characters (or "digits") each. That's no problem for a computer to deal with. The magnitude of the number represented isn't much of a factor; we're only manipulating the string of digits.

Factoring is currently an area of very intensive research, done formerly by number-theoretists and "taken over" in the 80's by cryptologists.

There are some very old algorithms, much more efficient then the O(n) method of running through all x<n.

1. O(n^(1/2)): You actually need to check only the x<=sqrt(n). 2. O(n^(1/3)): Due to Euler (1750). 3. O(n^(1/4)): The "rho" method. 4. O(exp((log(n)^(1/2)*(log(log(n)))^(1/2)))) - origined at 1940 (?) 5. O(.............1/3.................2/3...) - Lenstra, 1992.

However, even with these methods, it is currently beyond the state of the art to factor 180-digit numbers.

Where does A find a list of 60- and 90- digit prime numbers? Well, that's not too hard to come by. The simplest method to find a few prime numbers is simply to choose a 90-digit number (or 60-digit number, as the case warrants) randomly, and check to see if it is prime. You won't have to wait too long before you stumble across a prime number.

"But wait!" you cry. "I thought you just said it was incredibly difficult to factor large numbers. If that's the case, then how are you going to know if the number you randomly choose is prime?" A good question. Here we enter into the strange and wacky world of number theory. It turns out (and I won't explain how unless someone asks) there are "probabilistic" algorithms, which depend on us choosing numbers at random. There are probablistic algorithms that when given a prime number, will quickly tell us that it is a prime number, and when given a composite number, will either tell us that it is a composite number (with very, very high probability) or will tell us that it is a prime number (with very, very low probability.) What's the use of an algorithm that only returns the right answer "with very, very high probability?" Well, we can make this probability as high as we want, just by running the algorithm longer. In fact, it is within our technological abilities to quickly run this algorithm for 90-digit numbers so that the probability of it giving a wrong answer is less than the probability of a cosmic ray striking a vital part of the computer at some vital time and causing the computer to spit out the wrong answer anyway. That's what I mean by "very, very high."