Lucasin ja Lehmerin alkulukutesti Mersennen luvuille

Kohteesta 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

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

Lähteet[muokkaa | muokkaa wikitekstiä]

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]