Lähdekoodi sivulle Lucasin ja Lehmerin alkulukutesti Mersennen luvuille

__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 ''M''<sub>''p''</sub>&nbsp;=&nbsp;2<sup>''p''</sup>&minus;&nbsp;1 testattava Mersennen luku, missä ''p'' on pariton alkuluku. Määritellään sarja {''s''<sub>''i''</sub>} kaikilla ''i''&nbsp;&ge;&nbsp;0 asettamalla
:<math>
  s_i=
  \left\{
   \begin{matrix}
    4,\qquad\ \,&&\mbox{jos }i=0;\ \ \,
   \\
    s_{i-1}^2-2&&\mbox{muulloin.}
   \end{matrix}
  \right.
 </math>

Tällöin ''M''<sub>''p''</sub> on alkuluku vain jos
:<math>s_{p-2}\equiv0\pmod{M_p}.</math>
Lukua ''s''<sub>''p'' &minus; 2</sub> mod ''M''<sub>''p''</sub> 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&ndash;170.

== Aiheesta muualla ==
* [http://mathworld.wolfram.com/Lucas-LehmerTest.html MathWorld: Lucasin ja Lehmerin testi]
* [http://www.mersenne.org GIMPS (The Great Internet Mersenne Prime Search)]
* [https://web.archive.org/web/20090902181656/http://www.jt-actuary.com/lucas-le.htm Lucasin ja Lehmerin testin todistus] archive.org

[[Luokka:Alkulukutestit]]