- 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
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
Als voorbeeld nemen we .
dus 31 is een priemgetal.