Cesko.wiki Fermatův test prvočíselnosti
Author
Albert FloresFermatův test prvočíselnosti je jednoduchá metoda, která slouží k určení, zda je dané číslo prvočíslem nebo složeným číslem. Test je založen na Fermatově malé větě, která říká, že pokud je p prvočíslo a a je celé číslo, které není násobkem p, pak platí vztah a^(p-1) mod p = 1. Fermatův test spočívá v testování tohoto vztahu pro dané číslo a prvočíslo p. Pokud platí tento vztah, je pravděpodobné, že číslo p je prvočíslem. Pokud ale vztah neplatí, je číslo p jistě složené. Fermatův test je rychlý a snadno implementovatelný, ale není zcela spolehlivý, protože existují i složená čísla, která tento vztah splňují.
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. +more Carmichaelova čísla), proto je často označován jako test složenosti.
Na základě malé Fermatovy věty, je-li n prvočíslo a a není jeho násobek platí a^{n-1}\equiv 1 \pmod{n} , nebo lze také říci, že a^{n-1} - 1 je dělitelné číslem n. Po použití obrácené implikace tohoto tvrzení je zřejmé, že existuje-li a \in \{1, 2, . +more, n - 1\} takové, že n nedělí a^{n-1} - 1, pak musí být n číslo složené.
Příklad: Při zvolení a = 2; n = 9 ; 2^8 - 1 = 255 , číslo 9 není dělitelem čísla 255 nebo
a = 2; n = 21 ; 2^{20} - 1 = 1048575 , také 21 nedělí číslo 1048575 . Fermatův test potvrdil složenost čísla pro a = 2 .
n je složené číslo
Pro složené číslo n a přirozené číslo a , platí:
* a^{n-1}\not\equiv 1 \pmod{n} - číslo a se nazývá Fermatův svědek složenosti čísla n * a^{n-1}\equiv 1 \pmod{n} - číslo n se nazývá pseudoprvočíslo vzhledem k bázi a .
Zobecnění
Je-li n prvočíslo \Rightarrow \bigl(\forall a \in \{1, 2, . , n - 1\} : a^{n-1}\equiv 1 \pmod{n} ) nebo \exists a \in \{1, 2, . +more, n - 1\} : a^{n-1}\not\equiv 1 \pmod{n} \Rightarrow n není prvočíslo.
Příklady
Zadání1: n = 5 a platí pro a = 1; 1^{5-1} = 1^4 = 1 , a = 2; 2^{5-1} = 2^4 = 16 atd.
1^4 \equiv 1 \pmod{5}
16 = 2^4 \equiv 1 \pmod{5}
81 = 3^4 \equiv 1 \pmod{5}
4^4 \equiv 1 \pmod{5} \Rightarrow n = 5 je prvočíslo.
Zadání2: n = 15 ; a = 2; 1^{2-1} = 1
1^{14}\equiv 1 \pmod{15}
2^{14}\equiv 4 \pmod{15} \Rightarrow kongruence není rovna 1 , proto číslo 15 není prvočíslo a číslo 4 je svědek složenosti.
Test pro velká čísla
Pro „velká“ čísla je časově náročné používat Fermatův test pro všechna čísla n .
Zadání3: Je číslo n =21 prvočíslo? Lze vybrat náhodná čísla a = \{8, 13, 3\}.
a = 8 \Rightarrow 8^{20} \equiv 8^{2^{10}} \equiv 64^{10} \equiv 1^{10} \equiv 1 \pmod{21} \Rightarrow 21 může být prvočíslo,
a = 13 \Rightarrow 13^{20} \equiv 13^{2^{10}} \equiv 169^{10} \equiv 1^{10} \equiv 1 \pmod{21} \Rightarrow 21 může být prvočíslo,
a = 3 \Rightarrow 3^{20} \equiv 9^{10} \equiv 81^{5} \equiv (-3)^{5} \equiv (-3) . 81 \equiv 9 \pmod{21} \Rightarrow 21 není prvočíslo!
Algoritmus
Fermatův test prvočíselnosti:
Vstup: liché celé číslo n \geqq 3 , parametr počet čísel t\geqq 1 .
Výstup: odpověď na otázku „je n prvočíslo. “ for (i = 1; i Pro testování prvočíselnosti velkého čísla se Fermatův test v praxi běžně nepoužívá. +more 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.