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

→‎Menete: futási idő
a (→‎Álprímek: segédjelek eltáv)
(→‎Menete: futási idő)
válik, hogy n valószínűleg prím. A legtöbb összetett szám ugyanis
legfeljebb ''1/2'' valószínűséggel állja a tesztet egy véletlen ''a'' -ra.
 
Futási ideje moduláris hatványozással O(''k'' × log<sup>2</sup>''n'' × log log ''n'' × log log log ''n''), ahol ''k'' a fordulók száma, azaz ennyi véletlen alapra megy a tesztelés.
 
==Álprímek==