Cesko.wiki Test prvočíselnosti
Author
Albert FloresTest prvočíselnosti je v matematice postup pro ověření, zda je dané číslo prvočíslo, tedy zda je dělitelné pouze jedničkou a samo sebou. Existuje několik různých metod testování prvočíselnosti, které se liší přesností a časovou náročností. Mezi nejznámější metody patří například Eratosthenovo síto, které je založeno na principu vyškrtnutí všech násobků čísla, a test Fermatova malého věty, který využívá známého matematického tvrzení. Test prvočíselnosti je důležitý v různých oblastech matematiky a informatiky, například při generování bezpečných klíčů pro šifrování.
Mersennova prvočísla Test prvočíselnosti je algoritmus z oboru teorie čísel, kterým lze určit, zda je zadané přirozené číslo prvočíslem. Obvykle přitom tuto otázku zodpoví, aniž by přímo našel prvočíselný rozklad (to je považováno za podstatně náročnější úlohu), a často se jedná o pravděpodobnostní algoritmy či algoritmy použitelné jen na určitý druh čísel.
Kromě algoritmů, které v případě úspěchu prokáží, že je číslo prvočíslem, jsou také algoritmy, které v případě úspěchu prokáží, že se jedná o složené číslo - takové se někdy označují testy složenosti a jejich zřejmě nejznámějším příkladem je oblíbený Millerův-Rabinův test prvočíselnosti.
Testování prvočíselnosti je obecně možné v polynomiálním čase, což bylo prokázáno objevením algoritmu AKS v roce 2002. Jedná se ovšem o asymptotickou složitost, při praktickém použití svou rychlostí silně zaostává a jsou často upřednostňovány jiné algoritmy, byť třeba pravděpodobnostní.
Jednoduché algoritmy
Zkusmé dělení
Koncepčně nejjednodušším algoritmem testujícím prvočíselnost je zkusmé dělení, které postupně zkouší dělit testované číslo možnými děliteli. V závislosti na propracovanosti implementace se může jednat o zkusmé dělení všemi přirozenými čísly menšími než číslo samo, nebo o optimalizované varianty, kdy se zkouší dělit například pouze dvojkou a pak lichými čísly, nebo pouze prvočísly menšími než odmocnina testovaného čísla.
Tento algoritmus má v každém případě asymptoticky exponenciální složitost (je klasickým příkladem algoritmu s pseudopolynomickou časovou složitostí).
Pro otestování prvočíselnosti malého čísla řádově do milionu ale může být jeho optimalizovaná varianta řešením nejrychlejším.
Algoritmy hledání prvočísel
Jako test prvočíselnosti je možné použít i algoritmy, jejichž úkolem je najít všechna prvočísla od 2 do zadaného čísla. Klasickým příkladem je Eratosthenovo síto. +more Asymptoticky ale má exponenciální časovou složitost a navíc má i vyšší paměťovou náročnost a je celkově poměrně pomalé, neboť řeší daleko obsáhlejší úlohu a pro cílené testování prvočíselnosti náhodných velkých čísel se tedy nehodí.
To platí i pro jeho moderní optimalizované varianty a odnože, například Atkinovo síto.
Obecné pravděpodobnostní algoritmy
Fermatův test
Fermatův test je založen na Malé Fermatově větě, tedy na pravidle, že pro prvočíselné p platí :a^{p-1}\equiv 1 \mod p pro všechna 0. Pokud se podaří nalézt a, pro které rovnost neplatí, pak p nemůže být prvočíslo. +more I v případě složeného čísla ale rovnost může platit pro některá a (složené číslo se pak vzhledem k a označuje za Fermatovo pseudoprvočíslo), dokonce existuje nekonečně mnoho takzvaných Carmichaelových čísel, která se pro všechna a chovají vzhledem tomuto testu jako prvočíslo a rovnici splňují. Fermatův test je tedy pravděpodobnostním testem složenosti.
Solovayův-Strassenův test
Solovayův-Strassenův test využívá Eulerovu větu a Jacobiho symbol a to tak, že ověřuje platnost rovnice :a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p, kterou všechna prvočísla p splňují pro všechna 0. Pokud test najde a, které rovnici nesplňuje, našel důkaz, že p je složené číslo. +more Ovšem i pro složené číslo může být rovnost splněna - říká se mu pak Eulerovo pseudoprvočíslo. Jedná se tedy o pravděpodobnostní test složenosti.
Millerův-Rabinův test
Millerův-Rabinův test podobně jako Fermatův a Solovayův-Strassenův test hledá svědka složenosti, tedy nějaké a, které nesplní rovnice, které by pro prvočíslo platily. V případě Millerova-Rabinova testu je potřeba najít a, ž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
kde 2^sd=n-1 a d je liché. I Millerův-Rabinův test je pravděpodobnostním testem složenosti.
Specializované algoritmy
Některé algoritmy jsou určeny jen pro čísla určitého tvaru.
Pépinův test
Pépinův test je určen k testování Fermatových čísel. Jedná se o deterministický test, který běží v polynomiálním čase a je jím možno prokázat, že dané číslo je prvočíslem.
Lucasův-Lehmerův test
Lucasův-Lehmerův test je určen k testování Mersennových čísel.