De algemene Lucas-Lehmertest is een priemgetaltest. Het is algoritme om te bepalen of een natuurlijk getal een priemgetal is. Hiervoor moeten de priemfactoren van het getal bekend zijn. Het algoritme is door Édouard Lucas en Derrick Henry Lehmer ontwikkeld. Dit artikel gaat over de algemene Lucas-Lehmertest. Er is ook de Lucas-Lehmertest voor mersennegetallen.

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

Als de eerste gelijkheid voor geldt, betekent dit vanwege de kleine stelling van Fermat dat en onderling ondeelbaar zijn. Als ook door de tweede stap komt, dan is de orde van in de groep gelijk aan , dus is de orde van de groep . Dit is zo vanwege de stelling van Lagrange, dat de orde van een groep door de orde van ieder element in die groep kan worden gedeeld. Dit betekent dat een priemgetal is.

Anderzijds, als een priemgetal is, dan moet er in de groep een element voorkomen, die een voortbrenger is van de groep . 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 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 Het algoritme kan in pseudocode als volgt worden geschreven:

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.

Categorie:Priemgetaltest