Algemene Lucas-Lehmertest

Dit artikel gaat over de algemene Lucas-Lehmertest. Er is ook een Lucas-Lehmertest voor mersennegetallen.

De algemene Lucas-Lehmertest is een algoritme om te bepalen of een natuurlijk getal $n$ een priemgetal is. Hiervoor moeten de priemfactoren van het getal $n-1$ bekend zijn. De test is ontwikkeld door Edouard Lucas en Derrick Henry Lehmer en wordt met name gebruikt in de numerieke getaltheorie.

Theorie

Zij $n$ een positief geheel getal. Als er een geheel getal $1<a<n$ is, zodanig dat:

a^{n-1}\ \equiv \ 1{\pmod {n}}

en voor alle priemfactoren $q$ van $n-1$ :

a^{({n-1})/q}\ \not \equiv \ 1{\pmod {n}},

dan is $n$ priem. Als zo'n getal $a$ niet bestaat, is $n$ een samengesteld getal.

Deze bewering is juist, om de volgende reden: als de eerste gelijkheid geldt voor $a,$ betekent dit dat $a$ en $n$ relatief priem zijn. Als $a$ ook door de tweede stap komt, dan is de orde van $a$ in de groep $(\mathbb {Z} /n\mathbb {Z} )^{*}$ gelijk aan $n-1,$ en dus is de orde van de groep is $n-1$ (vanwege het feit dat de orde van elk element in een groep de orde van de groep deelt). Dit betekent dat $n$ priem is.

Anderzijds, als $n$ priem is, dan moet er een primitieve wortel modulo $n$ zijn, ook wel voortbrenger van de groep $(\mathbb {Z} /n\mathbb {Z} )^{*}$ genoemd. Zo'n voortbrenger heeft de orde $|(\mathbb {Z} /n\mathbb {Z} )^{*}|=n-1$ en beide equivalenties gelden voor zo'n voortbrenger.

Merk op dat als er een $a<n$ bestaat waarvoor de eerste equivalentie niet geldt, we $a$ een Fermat getuige noemen van het feit dat $n$ samengesteld is.

Voorbeeld

Neem als voorbeeld $n=71$ . Dan is $n-1=70$ met de priemfactoren 2, 5 en 7. Kies als willekeurig getal bijvoorbeeld $a=17<n$ . Dan is:

17^{70}\equiv 1{\pmod {71}}.

Ga vervolgens voor elke priemfactor $q$ van $n-1=70$ na wat de waarde is van

a^{70/q}{\pmod {71}}

Er geldt:

17^{35}\equiv 70\not \equiv 1{\pmod {71}}

17^{14}\equiv 25\not \equiv 1{\pmod {71}}

17^{10}\equiv 1{\pmod {71}}.

Helaas blijkt dat $17^{10}\equiv 1{\pmod {71}}$ . Dus is nog steeds niet duidelijk of 71 een priemgetal is of niet. Als 71 geen priemgetal is, wordt 17 een Fermatleugenaar van 71 genoemd.

Probeer daarom een andere willekeurige $a$ , bijvoorbeeld $a=11$ , en bereken:

11^{70}\equiv 1{\pmod {71}}.

En eveneens:

11^{35}\equiv 70\ \not \equiv 1{\pmod {71}}

11^{14}\equiv 54\ \not \equiv 1{\pmod {71}}

11^{10}\equiv 32\ \not \equiv 1{\pmod {71}}.

Het blijkt dat de multiplicatieve orde van 11 (mod 71) gelijk is aan 70 en dus dat 71 een priemgetal is. Om het machtsverheffen modulo $n$ snel uit te voeren, kan gebruikgemaakt worden van machtsverheffen door kwadrateren.

Algoritme

Het algoritme kan in pseudocode als volgt geschreven worden:

Invoer: 
 $n>2$ , een oneven geheel getal, te testen op primaliteit;
 $k$ , een parameter die de nauwkeurigheid van de test bepaalt.

Uitvoer: 
priem, als  $n$  priem is, anders samengesteld of mogelijk samengesteld;

bepaal de priemfactoren van  $n-1$ 
LOOP1: herhaal  $k$  keer:
   kies een willekeurige  $a$  uit het interval  $[2,n-1]$ 
      als  $a^{n-1}\not \equiv 1{\pmod {n}}$ , dan uitvoer samengesteld 
      anders
         LOOP2: voor alle priemfactoren  $q$  van  $n-1:$ 
            als  $a^{(n-1)/q}\not \equiv 1{\pmod {n}}$ 
               als we deze ongelijkheid nog niet voor alle priemfactoren van  $n-1$  hebben gecontroleerd 
                   dan doe een volgende LOOP2
               anders uitvoer priem
            anders doe een volgende LOOP1
uitvoer mogelijk samengesteld.