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

$a^{n-1}\equiv 1(\mathrm{mod}n)$

ja

$a^{(n-1)/q}\equiv ̸1(\mathrm{mod}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.

Katso myös

• Lucasin ja Lehmerin alkulukutesti Mersennen luvuille