Miller-Rabin Primality Test

In 1976, Gray Miller introduced an algorithm, through his ph.d thesis1, which determines a primality of the given number. The original algorithm was deterministic under the Extended Reimann Hypothesis, which is yet to be proven. After four years, Michael O. Rabin improved the algorithm2 by using probabilistic approach and it no longer assumes the unproven hypothesis.

Probabilistic

The result of the test is simply a boolean. However, true does not implicate the number is prime. In fact, it means the number is probably prime. But false does mean the number is composite.

In order to increase the accuracy of the test, it needs to be iterated few times. If it returns true in every single iteration, then we can say with confidence that the number is pro……bably prime.

Algorithm

Let n be the given number, and write n-1 as 2^s·d, where d is odd. And choose a random number a within the range from 2 to n - 1.

Now make a sequence, in modulo n, as following:

a^d, a^(2·d), a^(4·d), … , a^((2^(s-1))·d), a^((2^s)·d) = a^(n-1)

And we say the number n passes the test, probably prime, if 1) a^d is congruence to 1 in modulo n, or 2) a^((2^k)·d) is congruence to -1 for some k = 1, 2, ..., s-1.

Pseudo Code

The following pseudo code is excerpted from Wikipedia3:

Usage

checkWithMillerRabin(7)                      // test if 7 is prime. (default iteration = 1)
checkWithMillerRabin(7, accuracy: 10)       // test if 7 is prime && iterate 10 times.

Reference

1. G. L. Miller, “Riemann’s Hypothesis and Tests for Primality”. J. Comput. System Sci. 13 (1976), 300-317.
2. M. O. Rabin, “Probabilistic algorithm for testing primality”. Journal of Number Theory. 12 (1980), 128-138.
3. Miller–Rabin primality test - Wikipedia, the free encyclopedia

Written for Swift Algorithm Club by Sahn Cha, @scha00 Code updated by Simon C. Krüger.