share:truealiases:- Rabin-Miller
- Test prvočíselnosti
- prvočíselnost
Rabin-Miller (test prvočíselnosti)
Podstata: Pravděpodobnost průchodu složeného čísla (neprvočísla) testem prvočíselnosti klesá rychleji než u jiných testů
O hodnot lze tvrdit, že mohou vystupovat v roli svědků
Znamená to, že složené číslo nepronikne testy častěji než s pravděpodobností
Princip
Probabilistický (pravděpodobnostní) test prvočíselnosti
Umí prohlásit jen, že číslo je 100% složené, nebo pravděpodobně prvočíslo, nemáme jistotu
Najít velká prvočísla deterministicky (se 100% jistotou, např. Eratosthenovým sítem nebo zkoušením dělitelnosti) je pro počítač výpočetně velmi náročné
Vygeneruje se náhodné liché číslo o požadované délce
Protože je liché, pak je sudé, lze rozložit na , kde nějaké
Spustí se na něj Rabin-Millerův test
Zvolíme "svědka" z rozmezí
Spočítáme
Ověříme podmínky testu
Pokud test řekne, že číslo je složené, okamžitě ho zahodíme. Pokud testem projde, opakujeme s jiným
Po opakovaných testech je žé, prohlásíme za pravděpodobně prvočíslo
(Po 40 testech je šance na chybu menší než , považováno za naprosto bezpečné)