Rabin-Miller test (*Miller-Rabin test*) is a primality test – determines whether the given number is a prime or not. However this test, constructed by *Gary Lee Miller*, was originally deterministic, it depended upon unproven Riemann hypothesis. To deal with this issue, the test was later redesigned to its probabilistic version by *Michael O. Rabin*. The Rabin-Miller test states if the given number is prime with probability , where is number of performed iterations of the test.

## Description

Ferma's little theorem states that for every prime and number , which is not divisible by , holds:

Also for p-1 it holds that

where is an odd number.

Hence

We can expand this equation using the formula

If is a prime, then divides , and must also divide the given expression. Hence at least one of the following equations must hold:

.

.

.

If at least one equation holds, we know with probability at least that the number is a prime. If none of the equations holds, we know for sure that the number is not a prime.

## Example

We choose: a = 5

From it arises, that the highest tested exponent will be 10, because . To get the least exponent we divide 10 by 2 as long as possible. In this case it is obvious that least exponent () is equal to 5.

Now we know for sure that 21 is not a prime number.