Rabin-Millerův test prvočíselnosti

Rabin-Millerův test (Miller-Rabinův test) je test prvočíselnosti - určuje, zda-li je číslo prvočíslem nebo ne. Ačkoliv byl tento test ve své původní verzi vymyšlené Gary Lee Millerem deterministický, tak závisel na nedokázané Riemannově domněnce. Test byl později upraven Michaelem O. Rabinem do své pravděpodobnostní verze. Rabin-Millerův test stanoví, zda je číslo prvočíslem s pravděpodobností $1 - {1/4^{k}}$ , kde k je počet iterací testu.

Princip

Z malé Fermatovy věty víme, že pro každé prvočíslo p nesoudělné s číslem a platí

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

Pro p-1 platí

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

kde m je liché číslo

Proto

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

Tento vztah můžeme rozepisovat pomocí vzorce $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)$

Pokud je a prvočíslo, pak p dělí $a^{p-1} - 1$ a musí tedy dělit i rozepsaný výraz. Proto musí platit jedna z následujících rovností.

$\\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$

Pokud platí alespoň jeden výraz, víme, že p není složené s pravděpodobností alespoň 75%. Pokud neplatí ani jeden výraz, máme jistotu, že p není prvočíslo.

Příklad

Testujeme: 21
Volíme: a = 5

Z $a^{(p-1)/2}$ plyne, že nejvyšším testovaným exponentem bude 10, protože (21 - 1)/2 = 10 , abychom zjistili nejmenší exponent, tak 10 dělíme dvěma tak dlouho, dokud to jde. V tomto případě je zřejmé, že se jedná o číslo 5.
Proto

$\\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$

Nyní víme, že 21 NENÍ prvočíslo.

Princip

Příklad

Doporučujeme