Lucasin ja Lehmerin alkulukutesti
Wikipedia
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.
