__NOTOC__ Lucasin ja Lehmerin alkulukutesti Mersennen luvuille on algoritmi, jolla voi määrittää onko annettu Mersennen luku alkuluku. Testin keksi ensimmäisenä Edouard Lucas vuonna 1878 ja testiä kehitti Derrick Lehmer 1930-luvulla.
Testi Lucasin ja Lehmerin alkulukutesti Mersennen luvuille toimii seuraavasti: Olkoon Mp = 2p− 1 testattava Mersennen luku, missä p on pariton alkuluku. Määritellään sarja {si} kaikilla i ≥ 0 asettamalla
Tällöin Mp on alkuluku vain jos
Lukua sp − 2 mod Mp kutsutaan p:n Lucasin ja Lehmerin jäännökseksi.
Katso myös Lucasin ja Lehmerin alkulukutesti
Lähteet Richard Crandall ja Carl Pomerance: Prime Numbers: A Computational Perspective: kappale 4.2.1: The Lucas-Lehmer test, sivut 167–170.
Aiheesta muualla MathWorld: Lucasin ja Lehmerin testi GIMPS (The Great Internet Mersenne Prime Search) Lucasin ja Lehmerin testin todistus archive.org
Luokka:Alkulukutestit