Fermatův test prvočíselnosti

Naším cílem je definovat postup kterým můžeme potvrdit, že nějaké celé číslo je složené -- nebo prvočíslo s velmi vysokou přesností, kterou si stanovíme. Tento postup musí být efektivní takže by měl být rychle spočitatelný na jakémkoli stroji. I přes rostoucí velikost zadání kterým je naše celé číslo ,n' musí být stále rychlý. Doposud bylo zjištěno, že potřebujeme znát nějaké pravidlo, které platí pro všechny prvočísla a zároveň pro velmi málo složených čísel. V předchozím videu jsme vizualizovali Malou fermantovu větu. Ta nám poskytuje zajímavé pravidlo: mějme nějaké prvočíslo ,p' a nějaké jiné celé číslo ,a' které je o trochu menší než ,p' pak platí, že ,p' dělí ,a' na p-tou mínus ,a' Můžeme to zapsat jako a^p = a (mod p) což je forma, kterou budeme používat. Protože ,a' a ,p' nemá společné dělitele -- -- protože ,p' je prvočíslo -- můžeme využít pravidla neutrálního prvku což je často zapisováno jako a^(p-1) = 1 (mod p) Zapamatujte si, že tohle můžeme udělat jenom proto, že největší společný dělitel ,a' a ,p' je 1 Připravil jsem ukázku, takže nejdříve uvidíme rovnici v akci a zvykneme si na ní. Všimněme si, že pokud za ,p' dosadím prvočíslo, pak výsledkem je pokaždé 1 nezávisle na ,a' Ovšem pokud dosadím za ,p' složené číslo, pak výsledkem není obvykle 1. Pokaždé když výsledek rovnice není 1, dostaneme "svědka" složeného čísla. Ten je důkazem, že naše ,p' není prvočíslo. Toto je princip Fermatova testu. Předtím, než půjdeme hlouběji, ještě se vrátíme a vybudujeme systém pro tento test který používá pravidlo, které jsme právě viděli. Pro náš test zvolíme nějaké celé číslo nazvěme ho ,p' -- je vstup Poté zvolíme nějaké celé číslo ,a' menší než ,p'. Nyní se můžeme zeptat "Je největší společný dělitel ,a' a ,p' 1?" Pokud není -- pokud největší společný dělitel čísel ,a' a ,p' je větší než 1, pak mají společného dělitele a dokázali jsme, že ,p' je složené protože známe jeho dělitele. Můžeme zastavit a skončit test. Náš test zahlásí "složené číslo". Pokud "ano", pak se můžeme ptát dál. "Je a^(p-1) rovno 1?" Pokud ne, máme "svědka" že ,p' je složené. Můžeme zastavit a říct "No jo, končíme. ,p' je složené" Pokud ano -- pokud rovnice je rovna 1 -- pak by ,p' mělo být prvočíslo, že? Naprogramoval jsem tento postup na levé straně je Fermatův test a na pravé straně je jednoduchý test dělitelnosti, který tam je proto, protože víme, že je vždy správně. Na první pohled se zdá, že to funguje ovšem narazili jsme na problém Narazili jsme na číslo 511 a Fermatův test říká že je prvočíslo a test dělitelnosti říká, že je složené. Číslo 511 se zdá prvočíslem z pohledu Fermatova testu, ale doopravdy není. Nyní se vrátíme zpět k naší rovnici a podíváme se, co se stalo. Je to ukázka čísla, kterému říkáme "pseudo-prvočíslo". Je to složené číslo, ale existují nějaká ,a', pro která test vrátí 1. A to je špatně. Tyto ,a' která způsobí že pro složená čísla vrací test 1 nazýváme "lháři". Protože nám lžou o tom, že ,p' je prvočíslo. Všimneme si, že pokud zvolíme jiné ,a' najdeme mnoho svědků narozdíl od lhářů. Takže bychom se měli vrátit a použít co jsme zjistili v našem testu dělitelnosti, kde prostě budeme opakovat Fermatův test vícekrát a pokaždé pro jiné ,a' a snad pokaždé nezvolíme lháře. Bylo dokázáno, že počet lhářů musí dělit počet všech čísel, ze kterých vybíráme. Což znamená, že nejvýše polovina všech výběrů nebo polovina všech čísel, ze kterých vybíráme můžou být lháři. Protože vybíráme náhodně šance nalezení svědka -- což je to co chceme -- je pokaždé alespoň jedna polovina. Po ,t' opakování pravděpodobnost, že jsme nenašli svědka se složeným číslem je maximálně 1 / (2^t) Takže po 20 pokusech pravděpodobnost chybného určení prvočísla je pouze jedna ku milionu. Takže v případě že jsme opravdu velcí smolaři při náhodném vybírání ,a' můžeme neustále vybírat lháře. Pokud tohle vstřebáme, tak získáme velmi důležité porozumění. A nyní se podíváme na náš test v akci s větším počtem pokusů. Zdá se, že funguje perfektně. Všimneme si, že v nehorším případě, a my víme kdy to je, když zadáme prvočíslo algoritmus poběží nejdéle. Fermatův test je mnohem více efektivní než test dělitelnosti hlavně kvůli počtu kroků které se nezvyšuje s velikostí vstupu. To je hlavní rozdíl. Nastavíme pouze počet pokusů a je to. Nikdy se nemusíme strachovat, že náš algoritmus provede miliony a miliony kroků jako jsme prováděli předtím. Tohle je podle mě ztělesnění aplikované matematiky. Používáme pravidlo, které někdo objevil a tím ušetříme neskutečné množství výpočetního času. Nicméně, je tu jeden malý kaz -- nebo chyba -- v celém systému. Dokážete ji najít?