Fermatův test prvočíselnosti

Fermatův test prvočíselnosti vychází z malé Fermatovy věty, tedy že pro každé prvočíslo platí

{ a^{p-1} \\equiv 1 \\bmod p}

Pokud rovnost pro testovené číslo p neplatí, tak určitě není prvočíslem, pokud platí, tak dané číslo MOŽNÁ prvočíslem je.


Příklad

Testujeme: 15
Volíme: a = 2
Předpokládáme:
 {2^{14} \\equiv 1 \\bmod 15}

Testujeme:
 2^{14} = 2^{4} \\cdot 2^{4} \\cdot 2^{4} \\cdot 2^{2} = 16 \\cdot 16 \\cdot 16 \\cdot 4 = 1 \\cdot 1 \\cdot 1 \\cdot 4 = 4 \\; v \\; Z_{15}

Číslo 2 je svědkem, že 15 není prvočíslo.

Příklad 2

Testujeme: 15
Volíme: a = 4
Předpokládáme:
{4^{14} \\equiv 1 \\bmod 15}

Testujeme:
 4^{14} = (4^2)^7 = 16^7 = 1^7 = 1 \\; v \\; Z_{15}

Číslo 4 tvrdí, že 15 je prvočíslo, což není pravda (jak jsme již zjistili v předchozím příkladu). Označme tedy číslo 4 za Fermatova lháře.

Nedostatky Fermatova testu

Zásadním nedostatkem Fermatova test je existence tzv. Carmichaelových čísel. Carmichaelova čísla jsou Fermatova pseudoprvočísla, což znamená, že jsou složená, ale vyhoví vždy Fermatovu testu bez ohledu na zvolenou bázi. Z toho také vyplývá, že pro Fermatův test nelze určit pravděpodobnost, že je dané číslo prvočíslem, pokud víme, že již prošlo k iteracemi testu.

Z tohoto důvodu není Fermatův test v praxi příliš rozšířený a používají se jiné testy, které zmíněnými nedostatky netrpí - například Rabin-Millerův, Solovay-Strassenův nebo Lehmannův test.


www.EuAutodily.cz SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?