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 ( een priemgetal) een mersennepriemgetal is. De test is ontwikkeld door Édouard Lucas en later verbeterd door Derrick Henry Lehmer.
Algoritme
[bewerken | brontekst 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 | brontekst bewerken]Als voorbeeld nemen we .
dus 31 is een priemgetal.