# 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

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

*Written for Swift Algorithm Club by Sahn Cha, @scha00*

*Code updated by*

**Simon C. Krüger**.