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 2 p − 1 {\displaystyle 2^{p}-1} ( p {\displaystyle p} een priemgetal) een mersennepriemgetal is. De test is ontwikkeld door Édouard Lucas en later verbeterd door Derrick Henry Lehmer.

Algoritme

Laat M p = 2 p − 1 {\displaystyle M_{p}=2^{p}-1} een mersennegetal zijn met p {\displaystyle p} een priemgetal. Definieer nu de rij S {\displaystyle S} als volgt:

s i = { 4 als  i = 0 s i − 1 2 − 2 als  i > 0 } {\displaystyle s_{i}=\left\{{\begin{matrix}4&&{\mbox{als }}i=0\\s_{i-1}^{2}-2&&{\mbox{als }}i>0\end{matrix}}\right\}}

De eerste termen van deze rij zijn 4, 14, 194, 37634, ... Nu geldt dat M p {\displaystyle M_{p}} een priemgetal is dan en slechts dan als

s p − 2 ≡ 0 mod M p {\displaystyle s_{p-2}\equiv 0\mod {M_{p}}}

Anders is M p {\displaystyle M_{p}} een samengesteld getal.

Met FFT-implementatie heeft het algoritme een looptijd van O ( n 2 log ⁡ n ) {\displaystyle O(n^{2}\log n)} .

Voorbeeld

Als voorbeeld nemen we M 5 = 2 5 − 1 = 31 {\displaystyle M_{5}=2^{5}-1=31} .

s 0 ≡ 4 mod 31 {\displaystyle s_{0}\equiv 4\mod 31}
s 1 ≡ 4 2 − 2 ≡ 14 mod 31 {\displaystyle s_{1}\equiv 4^{2}-2\equiv 14\mod 31}
s 2 ≡ 14 2 − 2 ≡ 8 mod 31 {\displaystyle s_{2}\equiv 14^{2}-2\equiv 8\mod 31}
s 3 ≡ 8 2 − 2 ≡ 0 mod 31 {\displaystyle s_{3}\equiv 8^{2}-2\equiv 0\mod 31}

S 3 = 0 {\displaystyle S_{3}=0} dus 31 is een priemgetal.

Zie ook

  • Algemene Lucas-Lehmertest
  • Lucas-Lehmer-Rieseltest