Lucas-Lehmer-Rieseltest

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 2ⁿ > k. De test is door Hans Riesel ontwikkeld en is gebaseerd op de bestaande Lucas-Lehmertest voor mersennegetallen.

Het algoritme

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

Definieer voor ${\displaystyle i=1,2,\ldots }$ de rij ${\displaystyle (u_{i})}$ door:

${\displaystyle u_{i+1}=u_{i}^{2}-2}$

Als het getal ${\displaystyle N=k\cdot 2^{n}-1}$ een deler is van ${\displaystyle u_{n-2}}$, dan is ${\displaystyle N}$ een priemgetal. Omdat de rij zeer snel groter wordt, rekenet men modulo ${\displaystyle N}$. Als ${\displaystyle u_{n-2}\equiv 0{\pmod {N}}}$, is ${\displaystyle N}$ een priemgetal.

Het is nog wel zaak een goede startwaarde ${\displaystyle u_{0}}$ te vinden.

Startwaarde

• Als ${\displaystyle k=1}$, is 4 een goede startwaarde voor oneven ${\displaystyle n}$; als ${\displaystyle n\equiv 3{\pmod {4}}}$, geldt ${\displaystyle u_{0}=3}$.
• Als ${\displaystyle k=3}$, moet ${\displaystyle u_{0}=5778}$ voor ${\displaystyle n\equiv 3{\pmod {4}}}$ of ${\displaystyle n\equiv 0{\pmod {4}}}$, geldt ${\displaystyle u_{0}=3}$.
• Als ${\displaystyle k=1}$ of ${\displaystyle k\equiv 5{\pmod {6}}}$ en 3 is geen deler van ${\displaystyle N}$, dan geldt ${\displaystyle u_{0}=(2+{\sqrt {3}})^{h}+(2-{\sqrt {3}})^{h}}$.

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

Verwijzingen en voetnoten

• Jean Penné. LLR.

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