Lucas-Lehmer-Rieseltest

De Lucas-Lehmer-Rieseltest 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 $k$.

Definieer voor $i=1,2,\dots$ de rij $(u_i)$ door:

$u_{i+1}=u_i^2-2$

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

Het is nog wel zaak een goede startwaarde $u_0$ te vinden.

Startwaarde

• Als $k=1$, is 4 een goede startwaarde voor oneven $n$; als $n\equiv 3(\mathrm{mod}4)$, geldt $u_0=3$.
• Als $k=3$, moet $u_0=5778$ voor $n\equiv 3(\mathrm{mod}4)$ of $n\equiv 0(\mathrm{mod}4)$, geldt $u_0=3$.
• Als $k=1$ of $k\equiv 5(\mathrm{mod}6)$ en 3 is geen deler van $N$, dan geldt $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.