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 een mersennegetal zijn met p een priemgetal. Definieer nu de rij S als volgt:

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

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

S3 = 0 dus 31 is een priemgetal.

Zie ook[bewerken]