Lucasin ja Lehmerin alkulukutesti

Wikipedia
Loikkaa: valikkoon, hakuun

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 \pmod n

ja

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.