Lucas-Lehmer-Rieseltest

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

De Lucas-Lehmer-Rieseltest is een test om de primaliteit van een getal N te testen, waarbij N = k*2^n-1, met 2^n > k. De test is ontwikkeld door Hans Riesel en hij is gebaseerd op de bestaande Lucas-Lehmertest voor mersennegetallen. Hij staat beschreven in het artikel "Lucasian Criteria for the Primality of h*2^n-1".

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 gebruikt door het distributed computingproject Riesel Sieve. In 2010 is het project gestopt. Het project draait nu als subproject van PrimeGrid

Externe links[bewerken]