Millerův–Rabinův test prvočíselnosti

Stejně jako Fermatův a Solovayův-Strassenův test, i Millerův-Rabinův test je založen na existenci rovností, které jsou splněny pro prvočísla, ale obecně neplatí. Platnost těchto rovností je zkoušena na testovaném čísle.

Především platí lemma o odmocninách z jedné v konečném tělese ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ , kde p je prvočíslo větší než dva. Jistě platí, že umocnění 1 a −1 na druhou modulo p dávají 1, a dále platí, že jsou to jediné dvě druhé odmocniny z jedné. To je jednak důsledek obecnější skutečnosti, že polynom v tělese má nanejvýš tolik různých kořenů, kolik je jeho stupeň, jednak to lze dokázat i přímo. Předpokládejme, že x je druhá odmocnina z 1 modulo p. Potom

${\displaystyle x^{2}\equiv 1{\pmod {p}}}$

${\displaystyle \left(x-1\right)\left(x+1\right)\equiv 0{\pmod {p}}.}$

Jinými slovy, p dělí součin ${\displaystyle (x-1)(x+1)}$ . Tedy dělí jeden z činitelů, proto je x kongruentní modulo p buď 1 nebo −1.

Je-li n liché prvočíslo, pak n−1 je sudé a můžeme je rozepsat jako 2^s·d, kde s a d jsou kladná celá čísla, přičemž d je liché. Můžeme ukázat, že pro každé ${\displaystyle a\in \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}}$ platí buď:

${\displaystyle a^{d}\equiv 1{\pmod {n}}}$

nebo

${\displaystyle a^{2^{r}\cdot d}\equiv -1{\pmod {n}}}$ pro nějaké ${\displaystyle 0\leq r\leq s-1.}$

To je vidět z kombinace předchozího lemma a z Malé Fermatovy věty, která říká:

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}.}$

Postupným druhým odmocňováním a^{n − 1} můžeme dostávat buď stále 1, nebo časem připadneme na −1.

Millerův-Rabinův prvočíselný test je založen na snaze najít a takové, že

${\displaystyle a^{d}\not \equiv 1{\pmod {n}}}$

a

${\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}$ pro všechna ${\displaystyle 0\leq r\leq s-1,}$

tedy takové a, které by bylo svědkem složenosti čísla n.

Pro každé liché složené číslo existuje mnoho svědků a, ale není znám žádný jednoduchý způsob, jak je nalézt. Proto je tento test používán jako pravděpodobnostní. Je vybráno náhodné ${\displaystyle a\in \left(\mathbb {Z} /n\mathbb {Z} \right)}$ a je zkontrolováno, zda není svědkem složenosti čísla n. Pro zvýšení pravděpodobnosti je možné test několikrát zopakovat s různými náhodně vybranými a.

Předpokládejme, že chceme otestovat, zda je číslo n = 221 složené. Rozepíšeme n − 1 = 220 jako 2²·55, tedy máme s = 2 a d = 55. Náhodně vybereme a < n, například 174 a počítáme:

• a^20·d mod n = 174⁵⁵ mod 221 = 47 ≠ 1, n − 1
• a^21·d mod n = 174¹¹⁰ mod 221 = 220 = n − 1.

Protože 220 ≡ −1 mod n vidíme, že buď je 221 prvočíslo, nebo jsme měli při výběru a smůlu. Zkusíme jiné a, tentokrát 137:

• a^20·d mod n = 137⁵⁵ mod 221 = 188 ≠ 1, n − 1
• a^21·d mod n = 137¹¹⁰ mod 221 = 205 ≠ n − 1.

Tedy 137 je svědek složenosti čísla 221 a 174 byl skutečně lhář. Nyní víme, že 221 je číslo složené (ovšem o jeho dělitelích nevíme nic víc než to, že existují).

Algoritmus (zapsaný v pseudokódu) vypadá tedy takto:

Vstup: n > 3, liché celé číslo k otestování na prvočíselnostVstup: k, parametr určující spolehlivost testuVýstup: složené, je-li n složené, jinak pravděpodobně prvočíslorozepiš n − 1 jako 2s·d, kde d je liché, postupným dělením n − 1 dvěmaLOOP: opakuj k krát:   vyber náhodné a v rozsahu [2, n − 2]   x ← ad mod n   pokud x = 1 nebo x = n − 1 pak začni novou iteraci LOOP   pro r = 1 .. s − 1      x ← x2 mod n      pokud x = 1 pak vrať složené      pokud x = n − 1 pak začni novou iteraci LOOP   vrať složenévrať pravděpodobně prvočíslo

Protože modulární umocňování je díky algoritmu mocnění pomocí čtverců velmi rychlé, je časová složitost algoritmu pouze O(k log³ n), kde k je počet různých hodnot a, které budeme zkoušet. Jedná se tedy o poměrně efektivní polynomiální algoritmus. Ještě lepšího času lze dosáhnout, pokud je násobení implementováno pomocí rychlé Fourierovy transformace a modulo implementováno pomocí Barrettovy redukce.

V situaci, kdy algoritmus vrátí výsledek složené z důvodu, že x=1, navíc víme, že ${\displaystyle d2^{r}}$ je lichý násobek řádu a — tuto skutečnost lze využít pro nalezení dělitele. Pak totiž platí, že n dělí ${\displaystyle a^{d2^{r}}-1=(a^{d2^{r-1}}-1)(a^{d2^{r-1}}+1)}$ , ale nedělí žádný z činitelů tohoto součinu. Proto lze dělitele získat hledáním největšího společného dělitele n a jednoho ze zmíněných činitelů. Pokud ovšem Millerův-Rabinův test skončí v situaci, kdy ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$ (tedy n není vzhledem k a pseudoprvočíslo), pak žádný postup na nalezení dělitele neznáme. Obecně tedy Millerův-Rabinův test nelze použít na nalezení prvočíselného rozkladu.

Čím více otestujeme různých a, tím větší je pravděpodobnost, že výsledek testu platí. Dá se dokázat, že pro libovolné složené n jsou alespoň ¾ z možných a svědky složenosti.^[2][3]

V tomto článku byl použit překlad textu z článku Miller–Rabin primality test na anglické Wikipedii.

• Millerův-Rabinův test na algoritmy.net