Lucas-Lehmer-Riesel-test
Van Wikipedia
De Lucas-Lehmer-Riesel-test is een test om de primaliteit van een getal N te testen, waarbij N = k * 2n − 1, met 2n > k. De test is ontwikkeld door Hans Riesel en hij is gebaseerd op de bestaande Lucas-Lehmer-test voor Mersenne-getallen. Hij staat beschreven in het artikel "Lucasian Criteria for the Primality of h * 2n − 1".
Inhoud |
[bewerk] Het algoritme
Het algoritme is gebaseerd op dezelfde rij als de Lucas-Lehmer-test, maar dan met een variabele beginwaarde, die afhankelijk is van k.
Definieer de volgende rij u:
Als nu geldt k * 2n − 1 | un − 2 dan is k * 2n − 1 een priemgetal. Omdat de rij zeer snel groter wordt, gaan we rekenen modulo k * 2n − 1. Als un − 2 = 0 mod k * 2n − 1 dan is het een priemgetal.
Nu moeten we nog een goede waarde voor u0 zien te vinden.
[bewerk] Het vinden van de startwaarde
- Als k gelijk is aan 1, dan is 4 een goede startwaarde als n oneven is, en als n = 3 mod 4, dan geldt u0 = 3.
- Als k = 3, dan moet u0 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
.
[bewerk] LLR Software
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 computing project Riesel Sieve
