Brontekst bekijken van Lucas-Lehmer-Rieseltest

De '''Lucas-Lehmer-Rieseltest'''<ref>{{en}} Hans Riesel. Lucasian Criteria for the Primality of {{math|N {{=}}  k*2^n-1}}, 4 oktober 1986. (pdf)</ref> is een test om te controleren dat een getal {{math|n}} een [[priemgetal]] is of niet. {{math|N {{=}}  k*2^n-1}}, met {{math|2<sup>n</sup> > 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 <math>k</math>. 

Definieer voor <math>i=1,2,\ldots</math> de rij <math>(u_i)</math> door:

:<math>u_{i+1} = u_i^2-2</math>

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

Het is nog wel zaak een goede startwaarde <math>u_0</math> te vinden.

== Startwaarde ==
* Als <math>k=1</math>, is 4 een goede startwaarde voor oneven <math>n</math>; als <math>n\equiv 3 \pmod 4</math>, geldt <math>u_0 = 3</math>.
* Als <math>k=3</math>, moet <math>u_0=5778</math> voor <math>n\equiv 3 \pmod 4</math> of <math>n\equiv 0 \pmod 4</math>, geldt <math>u_0 = 3</math>.
* Als <math>k=1</math> of <math>k\equiv 5 \pmod 6</math> en 3 is geen deler van <math>N</math>, dan geldt <math>u_0 = (2+\sqrt{3})^h+(2-\sqrt{3})^h</math>.

== 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é. [http://perso.orange.fr/jean.penne/index2.html LLR].

{{References}}

[[Categorie:Getaltheorie]]
[[Categorie:Priemgetaltest]]