Lucasin ja Lehmerin alkulukutesti Mersennen luvuille

Wikipedia
Loikkaa: valikkoon, hakuun

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[muokkaa | muokkaa wikitekstiä]

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=
  \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}\equiv0\pmod{M_p}.

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

Viitteet[muokkaa | muokkaa wikitekstiä]

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]