Un test de primalité

Si, pour x non multiple de p, $x^{p-1}\not \equiv 1 \ [p]$, alors p n'est pas premier (contraposée du petit théorème de Fermat). On a la ``réciproque '' : si $x^{n-1} \ {\bmod} \ n =1$ et $x^{(n-1)/p} \ {\bmod} \ n \not = 1$ pour tout facteur premier p de n-1 alors n est premier. C'est la base même du test de primalité par descente-remontée (ou downrun) dont voici un exemple tiré de [Knuth] :
n₀=37866809061660057264219253397 ;
puisque $3^{n_0-1} \ {\bmod} \ n_0=1$, n₀ est sûrement premier.
n₀-1=2.2.19.107.353.n₁ avec n₁=13191270754108226049301 ;
puisque $3^{n_1-1} \ {\bmod} \ n_1 \not =1$, n₁ est composé.
En effet n₁=91813.n₂ où n₂=143675413657196977 ;
puisque $3^{n_2-1} \ {\bmod} \ n_2=1$, n₂ est sûrement premier.
n₂-1=2⁴.3².547.n₃ et n₃=1103.n₄ où n₄=1653701519 ;
puisque $3^{n_4-1} \ {\bmod} \ n_4=1$, n₄ est sûrement premier.
n₄-1=2.7.19.23.137.1973 est complètement factorisé donc on peut commencer notre test :

$$x^{(n_4-1)/p} \ {\bmod} \ n_4 x^{n_4-1} \ {\bmod} \ n_4$$ x p

2 2 1 1

2 7 766408626 1

2 19 332952683 1

2 23 1154237810 1

2 137 373782186 1

2 1973 490790919 1

3 2 1 1

5 2 1 1

7 2 1653701518 1

Pour p=2, on a essayé x=2, 3, 5 avant de trouver x=7 pour conclure. Donc n₄ est premier d'où n₂ est complètement factorisé. Et ainsi, en faisant un tableau similaire pour n₀ (car on a complètement factorisé n₀-1), on obtient que n₀ est premier. Mais bien sûr, on peut encore gagner du temps en utilisant la loi de réciprocité quadratique qui nous aurait indiqué, par le simple calcul de n₄ mod 10, que $5^\frac{n_4-1}{2}$ mod n₄=1.