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 k is number of performed iterations of the test.

Description

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

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

Also for p-1 it holds that

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

where m 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 a is a prime, then p 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 (m) 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.


www.EuAutodily.cz SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?