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

Millerův-Rabinův test prvočíselnosti je jedním z testů prvočíselnosti, tedy z algoritmů rozhodujících, zda je dané číslo prvočíslo. Je podobný Fermatovu testu prvočíselnosti a Solovayovu-Strassenovu testu prvočíselnosti. Původní verze vyvinutá Gary Lee Millerem byla deterministická, ovšem závisela na nedokázané zobecněné Riemannově hypotéze. Michael O. Rabin na jejím základě vyvinul verzi pravděpodobnostní, která na ničem nedokázaném nezávisí.

Princip

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 \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é. +more 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 : x^{2} \equiv 1\pmod{p}.

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

Jinými slovy, p dělí součin (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 2s·d, kde s a d jsou kladná celá čísla, přičemž d je liché. Můžeme ukázat, že pro každé a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^* platí buď: : a^{d} \equiv 1\pmod{n}

nebo : a^{2^r\cdot d} \equiv -1\pmod{n} pro nějaké 0 \le r \le s-1.

To je vidět z kombinace předchozího lemma a z Malé Fermatovy věty, která říká: : a^{n-1} \equiv 1\pmod{n}.

Postupným druhým odmocňováním an − 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 : a^{d} \not\equiv 1\pmod{n}

a : a^{2^rd} \not\equiv -1\pmod{n} pro všechna 0 \le r \le 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í. +more Je vybráno náhodné 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říklad

Předpokládejme, že chceme otestovat, zda je číslo n = 221 složené. Rozepíšeme n − 1 = 220 jako 22·55, tedy máme s = 2 a d = 55. +more Náhodně vybereme a 20·d mod n = 17455 mod 221 = 47 ≠ 1, n − 1 * a21·d mod n = 174110 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:

* a20·d mod n = 13755 mod 221 = 188 ≠ 1, n − 1 * a21·d mod n = 137110 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 a jeho časová náročnost

Algoritmus (zapsaný v pseudokódu) vypadá tedy takto: Vstup: n > 3, liché celé číslo k otestování na prvočíselnost Vstup: k, parametr určující spolehlivost testu Výstup: složené, je-li n složené, jinak pravděpodobně prvočíslo rozepiš n − 1 jako 2s·d, kde d je liché, postupným dělením n − 1 dvěma LOOP: 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 log3 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. +more 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 d 2^r je lichý násobek řádu a - tuto skutečnost lze využít pro nalezení dělitele. Pak totiž platí, že n dělí a^{d 2^r} - 1 = (a^{d 2^{r-1}} - 1) (a^{d 2^{r-1}} + 1), ale nedělí žádný z činitelů tohoto součinu. +more 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 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.

Spolehlivost testu

Čí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.

Odkazy

Reference

Externí odkazy

[url=http://www.algoritmy.net/article/73/Rabin-Milleruv-test]Millerův-Rabinův test na algoritmy.net[/url]

Kategorie:Testy prvočíselnosti