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.
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.
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.
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.