Lucasin ja Lehmerin alkulukutesti Mersennen luvuille


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

Alkulukutestit