Pravděpodobnostní test prvočíselnosti (rozcvička)

Pojďme si nejprve rozmyslet koncepci náhodných algoritmů, které přijmou vstup ‚n‘ a pokud je ‚n‘ prvočíslo, tak je výstupem „prvočíslo" s naprostou jistotou. a nikdy jej neoznačí jako složené. Pokud je ‚n‘ složené, je tu malá šance chyby ‚e‘, že jej označíme za prvočíslo. Jinak máme (1-e) pravděpodobnost, že jej správně označíme jako složené. Začneme jednoduše. Z části množiny přirozených čísel až do nějakého maxima vybereme číslo, a pojmenujeme ho ‚n‘, a vložíme ho do našeho stroje. S předchozími metodami postupného dělení jsme vždy iterovali přes všechny hodnoty od 1 do odmocniny z ‚n‘ a testovali, zda dané číslo dělí ‚n‘. Ideálně jsme takto testovali jen prvočísla pro úsporu času. Pokud ‚a‘ dělilo ‚n‘, pak víme, že ‚n‘ je složené, našli jsme svědka složenosti. Pokud ne, tak si nejsme jistí, a zvětšíme ‚a‘ a testujeme znovu. Pokud jsme vyčerpali všechny možné testy, pak můžeme tvrdit, že ‚n‘ je prvočíslo, pokud jsme nenašli dělitele. Teď ale buďme líní. Vybereme pouze několik náhodných čísel, a uděláme několik testů dělitelnosti, které představují náhodné otázky. Víme, že pokud je ‚n‘ složené, tak musí mít někde své dělitele, Má alespoň jednoho dělitele, a některá složená čísla jich mají mnoho. Takže vezmeme náhodné číslo ‚a‘ mezi 1 a odmocninou z ‚n‘ a to je vše. Pak zkusíme, zda ‚a‘ dělí ‚n‘. A jako předtím, pokud ‚a‘ dělí ‚n‘, tak víme jistě, že ‚n‘ je složené, našli jsme svědka složenosti. Pokud ne, tak moc nevíme, akorát že ‚n‘ může být prvočíslo. Tak pro jistotu vygenerujeme několik dalších náhodných čísel a dál zkoušíme. A třeba po 100 nebo 1000 iteracích můžeme zastavit a říct, že je to prvočíslo s určitou jistotou, například 99.9 %. To je podobné jako naše hra s podmíněnou pravděpodobností. Snažili jsme se uhádnout, jestli byla mince pravá nebo falešná oboustranná. Padnutí orla je jako nalezení dělitele. Je to svědek pravé mince. Když padne panna, tak chceme hodit znova a iterovat. Po 5 pannách jsme si asi na 90 % jistí, takže můžeme skončit a říct, že mince je falešná. Tady mám program, který porovnává metodu nalezení dělitele s tímto novým náhodným testem dělitelnosti. Používám zatím nejrychlejší program metodou nalezení dělitele, od uživatele Dino, odkaz je v hlavičce programu. Všimněte si proměnného počtu pokusů. To je počet náhodných odhadů, začneme třeba jen na 3. I s malým vstupem, pokud je to prvočíslo, pak je výstup algoritmu náhodného dělení vždy prvočíslo. Pokud je ale vstup složený, může udělat chybu a identifikovat jej jako prvočíslo. To můžeme ale opravit zvýšením počtu pokusů. Pravděpodobnost chyby se sníží a teď vidíme, že se výstupy víceméně rovnají. Pokud testuju velké vstupy, tak se chyba opět zvětšuje, takže podle toho musím zvýšit počet pokusů. Potom se vstupy opět rovnají. Ale s velkým vstupem potřebuji tisíce testů pro danou přesnost. Takže jsme vlastně nezmenšili počet kroků. Metoda postupného dělení je pořád lepší, protože rychlost zvětšování chyby je příliš velká. Jsme blízko, máme správný nápad. Potřebujeme jiný test. Chceme rovnici, která se jednoduše počítá a může být použita k důkazu, že je číslo složené. Musí mít na vstupu nejen číslo ‚n‘, ale také náhodné číslo ‚a‘, abychom mohli dělat podobný náhodný test.