Rabin-Miller primality test

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 $1-1/4^{k}$ , 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:

${a^{p-1} - 1 \\equiv 0 \\bmod p}$

Also for p-1 it holds that

$p-1 = 2^{b} \\cdot m$

where is an odd number.

Hence

$a^{2^{b} \\cdot m} - 1 = 0 \\bmod p$

We can expand this equation using the formula $A^{2} - B^{2} = (A-B) \\cdot (A+B)$

$a^{2^{b} \\cdot m} - 1 = (a^{2^{b-1} \\cdot m} - 1) \\cdot (a^{2^{b-1} \\cdot m} + 1) = (a^{2^{b-2} \\cdot m} - 1) \\cdot (a^{2^{b-2} \\cdot m} + 1) \\cdot (a^{2^{b-1} \\cdot m} + 1)$
$= (a^{m} - 1) \\cdot (a^{m} + 1) \\cdot (a^{2m} + 1) \\cdots (a^{2^{b-3} \\cdot m} + 1) \\cdot (a^{2^{b-2} \\cdot m} + 1) \\cdot (a^{2^{b-1} \\cdot m} + 1)$

If is a prime, then divides $a^{p-1} - 1$ , and must also divide the given expression. Hence at least one of the following equations must hold:

$\\vert a^{m} \\vert _{p} = 1$
$\\vert a^{m} \\vert _{p} = -1$
$\\vert a^{2m} \\vert _{p} = -1$
.
.
.
$\\vert a^{(p-1)/2} \\vert _{p} = -1$

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

Example

Test: 21
We choose: a = 5

From $a^{p-1} - 1$ it arises, that the highest tested exponent will be 10, because (21-1)/2 = 10 . 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.

$\\vert a^{5} \\vert _{21} = \\vert 5^{5} \\vert _{21} = 17 \\neq 1$
$\\vert a^{5} \\vert _{21} = \\vert 5^{5} \\vert _{21} = 17 \\neq -1$
$\\vert a^{10} \\vert _{21} = \\vert 5^{10} \\vert _{21} = \\vert (5^{5})^{2} \\vert _{21} = \\vert 17^{2} \\vert _{21} = 16 \\neq -1$

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

Description

Example

Doporučujeme