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.

{ zpětná vazba }

Tweet	Delicious
Sdílet

Hodnocení (6): 3,83

Přečtěte si také

Fermatův test

Lehmannův test

Diskuse

Pavel Mička17.9.2010

Díky, máš pravdu, chybělo tam ono mod p

Petr17.9.2010

Myslím, že třetí vzoreček by měl končit stejně jako na prvním řádku. a^((2^b)*m) by se jinak rovnalo jedné což by platilo jen pro a = 1 a celý vzoreček by nevypovídal nic o prvočíselnosti