Lucas-Lehmertest voor mersennegetallen

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

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

Algoritme

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

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 $M_{p}$ een priemgetal is dan en slechts dan als

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

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

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

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

s_{0}\equiv 4\mod 31

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

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

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

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