Algemene Lucas-Lehmertest

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Jump to search
Zie artikel 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 een priemgetal is. Hiervoor moeten de priemfactoren van het getal 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 een positief geheel getal. Als er een geheel getal is, zodanig dat:

en voor alle priemfactoren van :

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

Deze bewering is juist, om de volgende reden: als de eerste gelijkheid geldt voor betekent dit dat en relatief priem zijn. Als ook door de tweede stap komt, dan is de orde van in de groep gelijk aan en dus is de orde van de groep is (vanwege het feit dat de orde van elk element in een groep de orde van de groep deelt). Dit betekent dat priem is.

Anderzijds, als priem is, dan moet er een primitieve wortel modulo zijn, ook wel voortbrenger van de groep genoemd. Zo'n voortbrenger heeft de orde en beide equivalenties gelden voor zo'n voortbrenger.

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

Voorbeeld[bewerken]

Neem als voorbeeld . Dan is met de priemfactoren 2, 5 en 7. Kies als willekeurig getal bijvoorbeeld . Dan is:

Ga vervolgens voor elke priemfactor van na wat de waarde is van

Er geldt:

Helaas blijkt dat . 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 , bijvoorbeeld , en bereken:

En eveneens:

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 snel uit te voeren, kan gebruikgemaakt worden van machtsverheffen door kwadrateren.

Algoritme[bewerken]

Het algoritme kan in pseudocode als volgt geschreven worden:

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

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

bepaal de priemfactoren van 
LOOP1: herhaal  keer:
   kies een willekeurige  uit het interval 
      als , dan uitvoer samengesteld 
      anders
         LOOP2: voor alle priemfactoren  van 
            als 
               als we deze ongelijkheid nog niet voor alle priemfactoren van  hebben gecontroleerd 
                   dan doe een volgende LOOP2
               anders uitvoer priem
            anders doe een volgende LOOP1
uitvoer mogelijk samengesteld.

Zie ook[bewerken]

Referenties[bewerken]