Lucas-Lehmertest voor mersennegetallen

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
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 2p-1 (p een priemgetal) een mersennepriemgetal is. De test is ontwikkeld door Edouard Lucas en later verbeterd door Derrick Henry Lehmer.

Algoritme[bewerken]

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 Mp een priemgetal is dan en slechts dan als

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

Anders is Mp een samengesteld getal.

Met FFT-implementatie heeft het algoritme een looptijd van O(n2 log n).

Voorbeeld[bewerken]

Als voorbeeld nemen we M5 = 25-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

S3 = 0 dus 31 is een priemgetal.

Zie ook[bewerken]