Algemene Lucas-Lehmertest

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Nuvola single chevron right.svg 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[bewerken]

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 a niet bestaat, dan 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 (Z/nZ)* 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 (Z/nZ)* genoemd. Zo'n voortbrenger heeft orde |(Z/nZ)*| = 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[bewerken]

Als voorbeeld nemen we n = 71. Dan is n−1 = 70 en de priemfactoren van 70 zijn 2, 5 en 7. We kiezen een willekeurige a < n, bijvoorbeeld a = 17. Nu berekenen we:

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

Voor alle gehele getallen a weten we dat:

a^{n - 1}\equiv 1 \pmod{n}\ \text{  dan en slechts dan als } \text{ ord}(a)|(n-1).

Dit heeft tot gevolg dat de multiplicatieve orde van 17 (mod 71) niet per se 70 hoeft te zijn, want een factor van 70 zou ook kunnen werken. Dus controleren we ook 70 gedeeld door zijn priemfactoren:

17^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}
17^{14}\ \equiv\ 25\ \not\equiv\ 1 \pmod {71}
17^{10}\ \equiv\ 1\ \equiv\ 1 \pmod {71}.

Helaas krijgen we dat 1710≡1 (mod 71). We weten dus nog steeds niet of 71 een priemgetal is of niet. Als 71 geen priemgetal is, dan wordt 17 een Fermat leugenaar van 71 genoemd.

We proberen een andere willekeurige a, bijvoorbeeld a = 11. Nu berekenen we:

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

Opnieuw betekent dit niet dat de multiplicatieve orde van 11 (mod 71) gelijk is aan 70, omdat een factor van 70 ook zou kunnen werken. Dus controleren we ook 70 gedeeld door zijn priemfactoren:

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}.

We zien dat de multiplicatieve orde van 11 (mod 71) gelijk is aan 70 and dus is 71 een priemgetal. Om het machtsverheffen modulo n snel uit te voeren, kan gebruik gemaakt worden van machtsverheffen door kwadrateren.

Algoritme[bewerken]

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 an-1 \not\equiv 1 (mod n) dan uitvoer samengesteld 
      anders
         LOOP2: voor alle priemfactoren q van n−1:
            als a(n-1)/q \not\equiv 1 (mod 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.

Zie ook[bewerken]

Referenties[bewerken]