Lucas-Lehmer-Rieseltest

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

De Lucas-Lehmer-Rieseltest[1] is een test om te controleren dat een getal n een priemgetal is of niet. N = k*2^n-1, met 2n > k. De test is door Hans Riesel ontwikkeld en is gebaseerd op de bestaande Lucas-Lehmertest voor mersennegetallen.

Het algoritme[bewerken | brontekst bewerken]

Het algoritme is gebaseerd op dezelfde rij als de Lucas-Lehmertest, maar dan met een variabele beginwaarde, die afhankelijk is van .

Definieer voor de rij door:

Als het getal een deler is van , dan is een priemgetal. Omdat de rij zeer snel groter wordt, rekenet men modulo . Als , is een priemgetal.

Het is nog wel zaak een goede startwaarde te vinden.

Startwaarde[bewerken | brontekst bewerken]

  • Als , is 4 een goede startwaarde voor oneven ; als , geldt .
  • Als , moet voor of , geldt .
  • Als of en 3 is geen deler van , dan geldt .

LLR-software[bewerken | brontekst bewerken]

LLR is een programma dat LLR-tests uit kan voeren. Het programma is ontwikkeld door Jean Penné. Vincent Penné heeft het programma zo aangepast dat het tests op kan halen via internet. Deze software wordt ook door het distributed computingproject Riesel Sieve gebruikt. In 2010 is het project gestopt. Het project draait nu als onderdeel van PrimeGrid.

Verwijzingen en voetnoten[bewerken | brontekst bewerken]

  • Jean Penné. LLR.
  1. (en) Hans Riesel. Lucasian Criteria for the Primality of N = k*2^n-1, 4 oktober 1986. (pdf)