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 ${\displaystyle n}$ een priemgetal is. Hiervoor moeten de priemfactoren van het getal ${\displaystyle 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 ${\displaystyle n}$ een positief geheel getal. Als er een geheel getal ${\displaystyle 1<a<n}$ is, zodanig dat:

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

en voor alle priemfactoren ${\displaystyle q}$ van ${\displaystyle n-1}$:

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

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

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

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

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

Voorbeeld

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

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

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

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

Er geldt:

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

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

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

Helaas blijkt dat ${\displaystyle 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 ${\displaystyle a}$, bijvoorbeeld ${\displaystyle a=11}$, en bereken:

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

En eveneens:

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

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

${\displaystyle 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 ${\displaystyle n}$ snel uit te voeren, kan gebruikgemaakt worden van machtsverheffen door kwadrateren.

Algoritme

Het algoritme kan in pseudocode als volgt geschreven worden:

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

Uitvoer: 
priem, als ${\displaystyle n}$ priem is, anders samengesteld of mogelijk samengesteld;

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

Zie ook

• Lucas-Lehmertest voor mersennegetallen
• Priemgetaltest

Referenties

• (en) Lucas-Lehmertest op de Engelstalige Wikipedia