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.