Fermatův test prvočíselnosti

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   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  .

n je složené číslo

editovat

Pro složené číslo   a přirozené číslo  , platí:

  •   – číslo   se nazývá Fermatův svědek složenosti čísla  
  •   – číslo   se nazývá pseudoprvočíslo vzhledem k bázi  .[2][1]

Zobecnění

editovat

Je-li   prvočíslo     nebo   není prvočíslo

Příklady

editovat
Související informace naleznete také v článku Kongruence.

Zadání1:   a platí pro  ,   atd.

 

 

 

      je prvočíslo.

Zadání2:  ;  

 

    kongruence není rovna  , proto číslo   není prvočíslo a číslo   je svědek složenosti.[3]

Test pro velká čísla

editovat

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

Zadání3: Je číslo   prvočíslo? Lze vybrat náhodná čísla  

    může být prvočíslo,

    může být prvočíslo,

    není prvočíslo!

Algoritmus

editovat

Fermatův test prvočíselnosti:

Vstup: liché celé číslo  , parametr počet čísel  .

Výstup: odpověď na otázku „je   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]

Reference

editovat
  1. a b c OCHODKOVÁ, 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. 
  2. a b MASÁKOVÁ, Zuzana. Prvočísla v akci. Rozhledy matematicko-fyzikální. 2015, roč. 90, čís. 1, s. 66–77. Dostupné online [cit. 2021-10-31]. ISSN 0035-9343. 
  3. STULÍKOVÁ, Gabriela. TESTOVÁNÍ PRVOČÍSELNOSTI [online]. Plzeň: Západočeská univerzita v Plzni, Fakulta pedagogická, 2017 [cit. 2021-10-31]. Dostupné online. 

Související články

editovat

Externí odkazy

editovat