<pre>
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.

<pre>
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.
</pre>

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."
</pre>
