Rabin-Miller method:
Here is an algorithm for determining if n is prime:
(a) Represent n-1 as n-1 = 2km, 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
![](https://book.transtutors.com/qimg/5cef0826-0f29-4638-9777-d7b34c358ba6.png)
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
![](https://book.transtutors.com/qimg/843d858b-5ada-49c0-b88a-878dc6d908ba.png)
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.