WikiDer > Lucas-Lehmer-Riesel-Test

Das Lucas-Lehmer-Riesel-Test^[1] ist ein Test, um zu überprüfen, ob eine Zahl nein ein Primzahl ist oder nicht. N = k*2^n-1, mit 2^nein > k. Der Test wurde von Hans Riesel entwickelt und basiert auf den bestehenden Lucas-Lehmer-Test für Mersenne-Zahlen.

Der Algorithmus

Der Algorithmus basiert auf derselben Zeile wie der Lucas-Lehmer-Test, jedoch mit einem variablen Anfangswert, der abhängig ist von ${displaystyle k}$.

Definiere für ${displaystyle i=1,2,ldots}$ die Reihe ${displaystyle (u_{i})}$ durch:

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

Wenn die Zahl ${Displaystil N=kcdot 2^{n}-1}$ ist ein Teiler von ${displaystyle u_{n-2}}$, dann ist ${Displaystil N}$ eine Primzahl. Da die Reihe sehr schnell größer wird, rechnet man modular${Displaystil N}$. wenn ${displaystyle u_{n-2}äquivalent 0{pmod {N}}}$, ist ${Displaystil N}$ eine Primzahl.

Wichtig ist nach wie vor ein guter Startwert ${displaystyle u_{0}}$ finden.

Startwert

• wenn ${Anzeigestil k=1}$, 4 ist ein guter Startwert für ungerade ${displaystyle n}$; wenn ${displaystyle nequiv 3{pmod {4}}}$, gilt ${displaystyle u_{0}=3}$.
• wenn ${Anzeigestil k=3}$, Muss ${displaystyle u_{0}=5778}$ vor dem ${displaystyle nequiv 3{pmod {4}}}$ oder ${Displaystil-Nequiv 0{pmod {4}}}$, gilt ${displaystyle u_{0}=3}$.
• wenn ${Anzeigestil k=1}$ oder ${displaystyle kequiv 5{pmod {6}}}$ und 3 ist kein Teiler von ${Displaystil N}$, dann ${displaystyle u_{0}=(2 {sqrt {3}})^{h} (2-{sqrt {3}})^{h}}$.

LLR-Software

LLR ist ein Programm, das LLR-Tests durchführen kann. Das Programm wurde von Jean Penné entwickelt. Vincent Penné hat das Programm so angepasst, dass es Tests über das Internet abrufen kann. Diese Software wird auch vom Distributed Computing Project unterstützt Rieselsieb benutzt. Das Projekt wurde 2010 gestoppt. Das Projekt läuft jetzt im Rahmen von PrimeGrid.

Referenzen und Fußnoten

• Jean Penne. LLR.