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í
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
Musí tedy platit
Testujeme:
2 je svědkem, že 15 není prvočíslo.
Zkusme si ten samý příklad se zvoleným číslem 4
Volíme: a = 4
Musí tedy platit
Testujeme:
Číslo 4 tvrdí, že 15 je prvočíslo, což není pravda (což bychom možná zjistili při pokusu s jiným základem (například již ona zmíněná dvojka)). Označme tedy číslo 4 za Fermatova lháře.
Problémy Fermatova testu
Zásadním problémem tohoto testu je ono „možná je prvočíslem“, protože i když nám 100 po sobě jdoucích testů napoví, že to může být prvočíslo, tak neexistuje způsob, jak určit, jaká je pravděpodobnost, že máme skutečně v ruce prvočíslo. Důvodem, proč to nelze zjistit je existence tzv. Carmichaelových čísel, kterých existuje nekonečně mnoho a mají tu vlastnost, že je vždy Fermatův test vyhodnotí jako prvočísla, ačkoliv jimi nejsou.
