Lucasin ja Lehmerin alkulukutesti

Lucasin ja Lehmerin alkulukutesti on alkulukutesti, joka toimii hyvin arvolla n jos luvun n-1 alkutekijät tunnetaan.

Jos on olemassa 1<a<n, jolle

ja

kaikilla luvun n-1 alkutekijöillä q, on n alkuluku. Jos tällaista a ei ole, on n yhdistetty luku.

Modulaarisen eksponentoinnin voi toteuttaa nopeasti laskemalla lukujen neliöitä ja kertomalla niitä keskenään. Jos a läpäisee lisäksi toisen testin, on a:n kertaluku ryhmässä (Z/nZ)* yhtä suuri kuin n-1, jolloin tämän ryhmän kertaluku on n-1, eli n on alkuluku. Toisaalta, jos n on alkuluku, on olemassa primitiivinen juuri modulo n ja kaikki primitiiviset juuret läpäisevät testin molemmat osat.

Katso myös 
 Lucasin ja Lehmerin alkulukutesti Mersennen luvuille

Alkulukutestit