Choose a random number, p, to test. Calculate b, where b is the number of times 2 divides p-1. Then calculate m, such that p = 1 + 2^b*m.

Choose a random number, a, such that a is less than p.
Set j = 0, and set z = a^m mod p.
If z = 1, or if z = p - 1, then p passes the test and may be prime.
If j > 0 and z = 1, then p is not prime.
Set j = j +1. If j < b and z <> z2 mod p go back to step 4. If z = p - 1, then p passes the test and may be prime.
If j = b and z <> p -1, then p is not prime.

The odds of a composite passing decreases faster with this test than with previous ones. Three-quarters of the possible values of a are guaranteed to be witnesses. This means that a composite number will slip through t tests no more than ¼t of the time, where t is the number of iterations. Actually, these numbers are very pessimistic. For most random numbers, something like 99.9 percent of the possible a values are witnesses.

b r a y d e n . o r g / Software

Prime Numbers

Links

Rabin-Miller Test