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 M_p = 2^p− 1 testattava Mersennen luku, missä p on pariton alkuluku. Määritellään sarja {s_i} kaikilla i ≥ 0 asettamalla

${\displaystyle s_{i}=\left\{{\begin{matrix}4,\qquad \ \,&&{\mbox{jos }}i=0;\ \ \,\\s_{i-1}^{2}-2&&{\mbox{muulloin.}}\end{matrix}}\right.}$

Tällöin M_p on alkuluku vain jos

${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}$

Lukua s_{p − 2} mod M_p 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