Lucas-Lehmertest voor mersennegetallen

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

Algoritme[bewerken]

Laat een mersennegetal zijn met een priemgetal. Definieer nu de rij als volgt:

De eerste termen van deze rij zijn 4, 14, 194, 37634, ... Nu geldt dat een priemgetal is dan en slechts dan als

Anders is een samengesteld getal.

Met FFT-implementatie heeft het algoritme een looptijd van .

Voorbeeld[bewerken]

Als voorbeeld nemen we .

dus 31 is een priemgetal.

Zie ook[bewerken]