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} = {\begin{matrix} 4 & als i = 0 \\ s_{i - 1}^{2} - 2 & als i > 0 \end{matrix}}

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 (p^{2} \log p)$ .

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 1 4^{2} - 2 \equiv 8 mod 31

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

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