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

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

Als voorbeeld nemen we  .

 
 
 
 

  dus 31 is een priemgetal.

Zie ook bewerken