Algemene Lucas-Lehmer-test
Van Wikipedia
- Dit artikel gaat over de algemene Lucas-Lehmertest. Er is ook een Lucas-Lehmer-test voor Mersennegetallen.
De algemene Lucas-Lehmertest is een algoritme om te bepalen of een getal n een priemgetal is. Hiervoor moeten de factoren van het getal n-1 bekend zijn. De test is ontwikkeld door Edouard Lucas en Derrick Henry Lehmer.
Inhoud |
[bewerk] Algoritme
Als er een getal a bestaat tussen 1 en n zodanig dat:
en
voor alle priemfactoren q van n−1, dan is n priem. Is dit niet het geval dan is n een samengesteld getal.
[bewerk] Voorbeeld
Neem n = 71.
.
Neem als eerst a = 11:
Dit betekent niet dat de multiplicatieve orde van 11 mod 71 gelijk is aan 70, want een factor van 70 zou ook kunnen werken. Dus probeer ook 70 gedeeld door zijn priemfactoren.
Hieruit volgt dat de multiplicatieve orde van 11 mod 71 gelijk is aan 70, en dus is 71 een priemgetal.
Om het machtsverheffen modulo n snel uit te voeren, kan gebruik gemaakt worden van machtsverheffen door kwadrateren.
[bewerk] Bewijs
Als a de eerste stap doorkomt, 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 
gelijk aan n-1, dus de orde van de groep is n-1, dus dit betekent dat n priem is. Als n priem is, dan moet er een primitieve wortel modulo n zijn, en deze wortel komt door beide stappen van het algoritme.
