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

Additional material

[ Editor: Randall Gee, who wrote the solution above, sent this
correction to its factoring paragraph and the following explanation of
the probabilistic primality test, which he had posted to rec.puzzles in
December 1993. ]

Now, we actually can do better than check everything less than the
number to be factored, but all known methods of factoring numbers
involves checking large amounts of numbers, and it takes a long time.
It is much more complicated than simply manipulating strings of digits.

How do we quickly determine if a number n is prime?  Well, one way to
determine if n is prime is to check all possible factors of n; if n has
no factors, it is prime.  But, as I explained before, this is a very
slow method.  But it's a start.

Viewed from the other way, we want to determine if n is composite.  To
show that it is composite, we simply exhibit one of its factors.  It's
a simple matter to see if numbers divide each other.  In this sense,
the factor of n acts as a "witness" to the compositeness of n.  The
only problem with this method is that there are very few witnesses, and
very many numbers which could be witnesses.  (Let's call them
"suspects".)

Ideally, we'd want to narrow down the list of suspects to a very small
list, one that we could search for witnesses very quickly.  At the
current moment, this is not possible.  So we'll try for the next best
thing: we want to make the number of witnesses very large.

Consider this: we want to see if n is composite.  Suppose we were to
pick our suspect randomly from the list of numbers less than n.  Say
that we also knew that if n is in fact composite, than at least 3/4 of
the suspects were in fact witnesses.  Then we run our test, and find
that our suspect is not a witness.  Then there are 2 possibilities:
either n is prime, or n is composite, and we just got unlucky, and
observed an event that had only a 1/4 probability of happening.

So, we pick another suspect randomly, and run our test again, and again
we find that our suspect is not a witness.  Then again, we have 2
possibilities: either n is prime, or n is composite, and we were fooled
twice, an event that has only a (1/4)^2=1/16 probability of happening.
So we pick another suspect, and we run our test, and again we find it's
not a witness....  Let's say we do this a couple hundred times, and
each time, we see that our suspect is not a witness.  Then we must
conclude that either n is prime, or we were fooled a couple of hundred
times, an event that has only a (1/4)^(couple of hundred)=(very low)
probability of happening.  In fact, it's more likely that there was an
undetected hardware failure that our test being fooled so many times in
a row.  So we say that we are very confident that n is a prime number.

Does such a test exist?  As you no doubt suspect, such a test does
exist.  It has its basis in Fermat's Little Theorem, which states that,
if p is a prime number, and 1 < a < p, then a^(p-1) (mod p) = 1.

What this means is that if you wanted to prove that n is composite,
then one way you could do this is to determine 2^(n-1) (mod p) and show
that it was not 1.  Then 2 would be a witness to the compositeness of
n.  [ Editor: "(mod p)" here should be "(mod n)". ]

"But wait!" you say.  "If n is very large, won't it take a very long
time to determine 2^(n-1), and won't 2^(n-1) have a very large number
of digits?"

Actually, it doesn't take very long to compute a^(p-1) (mod p).  There
are 2 tricks here: one is that we are dealing with numbers mod p, which
means that we don't have to worry about numbers larger than p.  Another
is that we can repeatedly square numbers find the desired power.  If n
is even, we compute a^n (mod p) as ( a^(n/2) (mod p) ) * ( a^(n/2) (mod
p) ), and if n is odd, we compute a^n (mod p) as ( a^(n-1) (mod p) ) *
( a (mod p) ).  So we can quickly determine a^(p-1) (mod p).

The problem here is that, although this test is fast, it doesn't always
work.  For most composite numbers, 2 is a witness to its compositeness
under this test, but there are rare numbers (called pseudoprimes) which
are composite, and for which 2 is not a witness.  A natural thing to do
is to test a bunch of suspects, but that fails too.  There are numbers
which have no witnesses under this test; these are called Carmichael
numbers, and they're even rarer.

But there are refinements to this test which always work; every
composite number has witnesses under this test, and at least 3/4 of all
suspects are witnesses.  The following algorithm is based on a result
by Rabin in 1976, and appears in Knuth's book.

        Let n, the number being checked for compositeness, be
        1+(2^k)*q, where q is odd.

        Let x be a random integer from 1 to n, exclusive.

        Set y to be x^q (mod n)

        For each j from 0 to j-1, inclusive, do:
        [ Editor: "j-1" should be "k-1". ]

                If j = 0 and y = 1, or if y = n-1,
                then x is not a witness to n's compositeness;
                end the test.

                If j > 0 and y = 1,
                then x is a witness to n's compositeness;
                n is composite; end the test.

                Otherwise, set y to be y^2 (mod n)

        We have run through all values of j;
        x is a witness of n's compositeness, n is composite; the test
        ends.

We can repeat this test as often as we want to gain the desired amount
of confidence in our result.

I don't want to give the impression that all methods for determining
primality are subject to a (very, very, very) small degree of
uncertainty though.  Not all methods for determining primality
practically are based on probabilistic methods.  If the Generalized
Riemann [Editor: "Reimann" in the original] Hypothesis is true, for example, than this test can be further
refined to yield a small set of suspects which could be quickly
checked.  This would be a fast, deterministic method for check for
primality.  There are other deterministic tests, which don't run in
polynomial time, as this test does, but run in "almost" polynomial
time.  But this is slower, and in practice, this probabilistic method
is the quickest.

-- Randall M! Gee <rmgee@soda.berkeley.edu>