Fermatův test prvočíselnosti se používá k určení, zda je dané číslo prvočíslo nebo číslo složené. Patří mezi pravděpodobnostní testy prvočíselnosti a je založený na malé Fermatově větě.

Fermatův test nepatří mezi typické pravděpodobnostní testy. Jednoznačně nerozliší prvočísla od čísel složených (to jsou tzv. Carmichaelova čísla), proto je často označován jako test složenosti.^[1]

Na základě malé Fermatovy věty, je-li ${\displaystyle n}$ prvočíslo a ${\displaystyle a}$ není jeho násobek platí ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$, nebo lze také říci, že ${\displaystyle a^{n-1}-1}$ je dělitelné číslem ${\displaystyle n}$. Po použití obrácené implikace tohoto tvrzení je zřejmé, že existuje-li ${\displaystyle a\in \{1,2,...,n-1\}}$ takové, že ${\displaystyle n}$ nedělí ${\displaystyle a^{n-1}-1}$, pak musí být ${\displaystyle n}$ číslo složené.^[2]

Příklad: Při zvolení ${\displaystyle a=2;n=9}$; ${\displaystyle 2^{8}-1=255}$, číslo ${\displaystyle 9}$ není dělitelem čísla ${\displaystyle 255}$ nebo

${\displaystyle a=2;n=21}$; ${\displaystyle 2^{20}-1=1048575}$, také ${\displaystyle 21}$ nedělí číslo ${\displaystyle 1048575}$. Fermatův test potvrdil složenost čísla pro ${\displaystyle a=2}$.

Pro složené číslo ${\displaystyle n}$ a přirozené číslo ${\displaystyle a}$, platí:

• ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$ – číslo ${\displaystyle a}$ se nazývá Fermatův svědek složenosti čísla ${\displaystyle n}$
• ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$ – číslo ${\displaystyle n}$ se nazývá pseudoprvočíslo vzhledem k bázi ${\displaystyle a}$.^[2][1]

Je-li ${\displaystyle n}$ prvočíslo ${\displaystyle \Rightarrow }$ ${\displaystyle {\bigl (}\forall a\in \{1,2,...,n-1\}:a^{n-1}\equiv 1{\pmod {n}})}$ nebo ${\displaystyle \exists a\in \{1,2,...,n-1\}:a^{n-1}\not \equiv 1{\pmod {n}}\Rightarrow n}$ není prvočíslo

Zadání1: ${\displaystyle n=5}$ a platí pro ${\displaystyle a=1;1^{5-1}=1^{4}=1}$, ${\displaystyle a=2;2^{5-1}=2^{4}=16}$ atd.

${\displaystyle 1^{4}\equiv 1{\pmod {5}}}$

${\displaystyle 16=2^{4}\equiv 1{\pmod {5}}}$

${\displaystyle 81=3^{4}\equiv 1{\pmod {5}}}$

${\displaystyle 4^{4}\equiv 1{\pmod {5}}}$ ${\displaystyle \Rightarrow }$ ${\displaystyle n=5}$ je prvočíslo.

Zadání2: ${\displaystyle n=15}$; ${\displaystyle a=2;1^{2-1}=1}$

${\displaystyle 1^{14}\equiv 1{\pmod {15}}}$

${\displaystyle 2^{14}\equiv 4{\pmod {15}}}$ ${\displaystyle \Rightarrow }$ kongruence není rovna ${\displaystyle 1}$, proto číslo ${\displaystyle 15}$ není prvočíslo a číslo ${\displaystyle 4}$ je svědek složenosti.^[3]

Pro „velká“ čísla je časově náročné používat Fermatův test pro všechna čísla ${\displaystyle n}$.

Zadání3: Je číslo ${\displaystyle n=21}$ prvočíslo? Lze vybrat náhodná čísla ${\displaystyle a=\{8,13,3\}.}$

${\displaystyle a=8\Rightarrow 8^{20}\equiv 8^{2^{10}}\equiv 64^{10}\equiv 1^{10}\equiv 1{\pmod {21}}}$ ${\displaystyle \Rightarrow 21}$ může být prvočíslo,

${\displaystyle a=13\Rightarrow 13^{20}\equiv 13^{2^{10}}\equiv 169^{10}\equiv 1^{10}\equiv 1{\pmod {21}}}$ ${\displaystyle \Rightarrow 21}$ může být prvočíslo,

${\displaystyle a=3\Rightarrow 3^{20}\equiv 9^{10}\equiv 81^{5}\equiv (-3)^{5}\equiv (-3).81\equiv 9{\pmod {21}}}$ ${\displaystyle \Rightarrow 21}$ není prvočíslo!

Fermatův test prvočíselnosti:

Vstup: liché celé číslo ${\displaystyle n\geqq 3}$, parametr počet čísel ${\displaystyle t\geqq 1}$.

Výstup: odpověď na otázku „je ${\displaystyle n}$ prvočíslo?“

for (i = 1; i <= t; i++)
{
    vyber náhodné int a;
    r = a*(n-1) \mod n; //RSMA 
    if (r !i = 1 ) then
    return ("složené")
    break;
}
return ("prvočíslo")

Pro testování prvočíselnosti velkého čísla se Fermatův test v praxi běžně nepoužívá. Existuje pravděpodobnost, že místo náhodného lichého celého čísla bude vygenerováno pseudoprvočíslo, tedy složené kladné celé číslo, které je chybně určeno jako prvočíslo.^[1]

• Test prvočíselnosti

• Malá Fermatova věta

• Slovníkové heslo Fermatův test prvočíselnosti ve Wikislovníku

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.