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

${\displaystyle a^{n-1}\ \equiv \ 1{\pmod {n}}}$

ja

${\displaystyle a^{({n-1})/q}\ \not \equiv \ 1{\pmod {n}}}$

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.

• Lucasin ja Lehmerin alkulukutesti Mersennen luvuille