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 je svědkem, že 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 tvrdí, že je prvočíslo, což není pravda (jak jsme již zjistili v předchozím příkladu). Označme tedy číslo 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 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.

Příklad

Příklad 2

Nedostatky Fermatova testu

Doporučujeme