„Fermat-prímteszt” változatai közötti eltérés

nincs szerkesztési összefoglaló
(→‎Álprímek: 1. bizonyításának befejezése)
A '''Fermat-prímteszt''' (vagy Fermat-féle prímszámpróba) egy valószínűségi prímteszt. A [[kis Fermat-tétel]]en alapul, ami kimondja, hogy ha ''p'' [[prím]], akkor
''a^(''<sup>''p-1)''-1</sup> [[kongruencia|kongruens]] ''1'' mod ''p'', ha ''p'' nem osztója ''a''-nak.
 
==Menete==
 
LegyenMeg akívánjuk tesztelendővizsgálni, hogy ''n'' szám ''1''-nél nagyobb páratlan egész, ésprím-e. legyenLegyen
''1<a<n''. [[Euklidészi algoritmus]]sal ellenőrizhető, hogy ''n'' és ''a'' [[relatív prímek]]. Ha nem azok, akkor ''n'' bukja a tesztet, [[összetett szám|összetett]].