Lähdekoodi sivulle 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
:<math>a^{n-1}\ \equiv\ 1 \pmod n</math>
ja
:<math>a^{({n-1})/q}\ \not\equiv\ 1 \pmod n</math>
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'''/''n'''''Z''')* 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]]

[[Luokka:Alkulukutestit]]