Rabin-Miller method:

Here is an algorithm for determining if n is prime:

(a) Represent n-1 as n-1 = 2^km, where m is odd. (That is, m is what remains when all factors of 2 are taken out of n - 1.)

(b) Select a random number a, 1

(c) Compute

If b = 1 or - 1 (-1 = n - 1), declare PRIME and end.

(d) Repeat k - 1 times or until end: Define a new b by

If b = -1, declare PRIME and end. If the algorithm ends without declaring PRIME, then n is definitely not prime.

If n is prime, the algorithm will declare PRIME. However, for general n, if PRIME is declared, there is a 1/4 probability that n is not actually prime. Apply a single cycle of the method to n = 5,009 using a = 3.