Algemene Lucas-Lehmertest
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
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
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 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
 Lucas-Lehmertest voor mersennegetallen
 Priemgetaltest

Referenties
 Lucas-Lehmertest op de Engelstalige Wikipedia

Getaltheorie
Priemgetaltest