Voir la source de Test de primalité de Lucas-Lehmer

{{voir homonymie|Lucas|Lehmer|Test de Lucas}}
Le '''test de primalité de Lucas<ref>{{Ouvrage|auteur=[[Édouard Lucas]]|titre=Théorie des nombres|tome=1|url=http://visualiseur.bnf.fr/CadresFenetre?O=NUMM-29021&I=239|year=1891|page=441}}.</ref>-Lehmer<ref>{{Article|lang=en|revue=[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]]|vol=33|issue=3|year=1927|p.=327-340|titre=Tests for primality by the converse of Fermat's theorem|auteur=[[Derrick Lehmer|D. H. Lehmer]]|url=http://projecteuclid.org/euclid.bams/1183492108}}.</ref>''' est une méthode pour [[Test de primalité|tester la primalité]] d'un [[Entier naturel|entier]] {{math|''n''}}, connaissant les [[Décomposition en produit de facteurs premiers|facteurs premiers]] de {{math|''n'' – 1}}.

==Le test==
Un entier {{math|''n'' > 2}} est [[Nombre premier|premier]] [[si et seulement si]] il existe un entier {{math|''a''}}, strictement compris entre {{math|1}} et {{math|''n''}}, tel que  
:<math>a^{n-1}\equiv1\pmod n</math>
et, pour tout facteur premier<ref>Optimisation par {{Harvsp|Lehmer|1927}} de l'énoncé de {{Harvsp|Lucas|1891}}, qui testait sur tous les [[Diviseur non trivial|diviseurs non triviaux]] {{math|''q''}} de {{math|''n'' – 1}}.</ref> {{math|''q''}} de {{math|''n'' – 1}},
:<math>a^{({n-1})/q}\not\equiv1\pmod n.</math>

==Exemple==

Par exemple, prenons ''n'' = 2017, ''n'' – 1 = 2016 = 2{{5}}×3{{2}}×7.

''a'' = 2 ne convient pas car 2{{exp|288}} ≡ 1 (mod ''n'').

''a'' = 3 non plus car 3{{exp|1008}} ≡ 1 (mod ''n'')

Essayons ''a'' = 5 (pour calculer rapidement mod ''n'' les puissances voulues, on peut utiliser la méthode d'[[exponentiation rapide]] et de plus, calculer d'abord 5{{exp|2{{4}}×3}}) :
:<math>5^{1008}\equiv-1\not\equiv1\pmod n\text{ et }5^{2016}\equiv(-1)^2\equiv1\pmod n</math>
:<math>5^{672}\equiv294\not\equiv1\pmod n</math>
:<math>5^{288}\equiv-138\not\equiv1\pmod n</math>
Donc 2017 est premier.

==Démonstration==
La première condition signifie que ''a'' est [[Inverse modulaire|inversible modulo ''n'']] et que son [[ordre multiplicatif]] est un [[diviseur]] de ''n'' – 1. La seconde signifie que cet ordre est exactement ''n'' – 1 (et non un [[diviseur strict]]). Par conséquent, l'[[Ordre (théorie des groupes)|ordre]] du [[groupe des inversibles]] de l'[[Anneau ℤ/nℤ|anneau ℤ/''n''ℤ]] — qui est ''a priori'' inférieur ou égal à ''n'' – 1 — [[Théorème de Lagrange sur les groupes|est divisible par ''n'' – 1]] donc égal à  ''n'' – 1, ce qui signifie que ''n'' est premier.

[[Réciproque]]ment, si ''n'' est premier, alors il existe [[Indicatrice d'Euler|φ(''n'' – 1)]] [[racine primitive modulo n|racines primitives modulo ''n'']], et n'importe laquelle satisfera toutes les conditions du test.

==Utilisation==
En [[théorie de la complexité (informatique théorique)|théorie de la complexité]], ce test donne un {{Lien|trad=Primality certificate|certificat de primalité}}, appelé certificat de {{Lien|Vaughan Pratt|texte=Pratt}}, qui montre que le test de primalité est dans '''[[NP(complexité)|NP]]'''<ref>{{Article|lang=en|auteur=Vaughan Pratt|titre=Every prime has a succinct certificate|revue=[[Liste des journaux scientifiques en mathématiques#S|Siam J. Comput.]]|vol=4|issue=3|year=1975|p.=214-220|url=http://boole.stanford.edu/pub/SucCert.pdf}}.</ref>.

==Notes et références==
{{Traduction/Référence|en|Lucas primality test|10784117|type=n}}
{{Références}}

==Articles connexes==
* [[Suite de Lucas]]
*[[Test de primalité de Fermat]]
* [[Test de primalité de Lucas-Lehmer pour les nombres de Mersenne]]
*[[Théorème de Pocklington]] (une double généralisation du test, où ''a'' n'est pas nécessairement le même pour chaque ''q'', et où une factorisation partielle de ''n'' – 1 suffit)

{{Portail|nombre}}

[[Catégorie:Test de primalité|Lucas-Lehmer]]