Lucas-Lehmertest voor mersennegetallen

De Lucas-Lehmertest voor mersennegetallen is een algoritme om te bepalen of het mersennegetal ${\displaystyle 2^{p}-1}$ (${\displaystyle p}$ een priemgetal) een mersennepriemgetal is. De test is ontwikkeld door Édouard Lucas en later verbeterd door Derrick Henry Lehmer.

Dit artikel gaat over de Lucas-Lehmertest voor mersennegetallen. Er is ook een algemene Lucas-Lehmertest, voor alle natuurlijke getallen.

Algoritme

Laat ${\displaystyle M_{p}=2^{p}-1}$ een mersennegetal zijn met ${\displaystyle p}$ een priemgetal. Definieer nu de rij ${\displaystyle S}$ als volgt:

${\displaystyle s_{i}=\left\{{\begin{matrix}4&&{\mbox{als }}i=0\\s_{i-1}^{2}-2&&{\mbox{als }}i>0\end{matrix}}\right\}}$

De eerste termen van deze rij zijn 4, 14, 194, 37634, ... Nu geldt dat ${\displaystyle M_{p}}$ een priemgetal is dan en slechts dan als

${\displaystyle s_{p-2}\equiv 0\mod {M_{p}}}$

Anders is ${\displaystyle M_{p}}$ een samengesteld getal.

Met FFT-implementatie heeft het algoritme een looptijd van ${\displaystyle O(p^{2}\log p)}$.

Voorbeeld

Als voorbeeld nemen we ${\displaystyle M_{5}=2^{5}-1=31}$.

${\displaystyle s_{0}\equiv 4\mod 31}$

${\displaystyle s_{1}\equiv 4^{2}-2\equiv 14\mod 31}$

${\displaystyle s_{2}\equiv 14^{2}-2\equiv 8\mod 31}$

${\displaystyle s_{3}\equiv 8^{2}-2\equiv 0\mod 31}$

${\displaystyle S_{3}=0}$ dus 31 is een priemgetal.

Zie ook

• Algemene Lucas-Lehmertest
• Lucas-Lehmer-Rieseltest