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

s i = { 4 ,   jos  i = 0 ;     s i − 1 2 − 2 muulloin. {\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 Mp on alkuluku vain jos

s p − 2 ≡ 0 ( mod M p ) . {\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}

Lukua sp − 2 mod Mp kutsutaan p:n Lucasin ja Lehmerin jäännökseksi.

Katso myös

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