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ě.
Popis
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 prvočíslo a není jeho násobek platí , nebo lze také říci, že je dělitelné číslem . Po použití obrácené implikace tohoto tvrzení je zřejmé, že existuje-li takové, že nedělí , pak musí být číslo složené.[2]
Příklad: Při zvolení ; , číslo není dělitelem čísla nebo
; , také nedělí číslo . Fermatův test potvrdil složenost čísla pro .
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]
Reference
↑ abcOCHODKOVÁ, Eliška. Matematické základy kryptografických algoritmů [online]. Západočeská univerzita v Plzni: Vysoká škola báňská – Technická univerzita Ostrava, 2012 [cit. 2021-10-31]. Dostupné online.
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.