Naar inhoud springen

Lucas-Lehmertest voor mersennegetallen

Uit Wikipedia, de vrije encyclopedie
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 Édouard Lucas en later verbeterd door Derrick Henry Lehmer.

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 .

Als voorbeeld nemen we .

dus 31 is een priemgetal.