Lucas-Lehmer-Rieseltest

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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]

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

Definieer de volgende rij u:

u_i = u_{i-1}^2-2 \mbox{ als } i>0

Als nu geldt k*2^n-1|u_{n-2} dan is k*2^n-1 een priemgetal. Omdat de rij zeer snel groter wordt, gaan we rekenen modulo k*2^n-1. Als u_{n-2} = 0 mod k*2^n-1 dan is het een priemgetal.

Nu moeten we nog een goede waarde voor u_0 zien te vinden.

Het vinden van de startwaarde[bewerken]

  • Als k gelijk is aan 1, dan is 4 een goede startwaarde als n oneven is, en als n = 3 mod 4, dan geldt u_0 = 3.
  • Als k = 3, dan moet u_0 gelijk zijn aan 5778 voor n = 0 of 3 mod 4.
  • Als geldt dat k = 1 of 5 mod 6 en 3 deelt N niet, dan geldt u_0 = (2+\sqrt{3})^h+(2-\sqrt{3})^h.

LLR-software[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]

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