De Lucas-Lehmertest voor mersennegetallen is een priemgetaltest. Het is een algoritme om te bepalen of het mersennegetal , met een priemgetal, een mersennepriemgetal is. De test is door Édouard Lucas ontwikkeld en later door Derrick Henry Lehmer verbeterd. Dit artikel gaat over de Lucas-Lehmertest voor mersennegetallen. Er zijn ook de algemene Lucas-Lehmertest voor alle natuurlijke getallen en de Lucas-Lehmer-Rieseltest, die op de Lucas-Lehmertest voor mersennegetallen is gebaseerd.
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 een FFT-implementatie heeft het algoritme een looptijd van .
Voorbeeld Als voorbeeld nemen we .
dus is 31 een priemgetal.
Categorie:Priemgetaltest