théorème de Pocklington

Pour savoir si 13 est premier, on observe d’abord que 13 − 1 vaut 12 et que 12 contient le facteur connu 2². On cherche ensuite un nombre témoin, ici 2, qui passe deux contrôles de restes et de divisibilité. Ces contrôles obligent tout éventuel facteur premier de 13 à dépasser 4.

Or un nombre composé égal à 13 devrait posséder un facteur premier inférieur ou égal à sa racine carrée, donc inférieur à 4. Les deux contraintes sont incompatibles : 13 est premier. Le théorème transforme ainsi une partie connue de la factorisation de N − 1 en certificat.

Le théorème de Pocklington est un critère de primalité fondé sur une factorisation partielle de l’entier N − 1. L’entier naturel à tester est noté N et doit être supérieur à 1. On suppose qu’un nombre premier q, un entier n au moins égal à 1 et un entier R vérifient $N-1=q^{n}RN-1=q^nR$. Il faut alors trouver un entier positif a qui joue le rôle de témoin.

Le témoin doit satisfaire simultanément les deux conditions suivantes : Le théorème assure alors que chaque facteur premier p de N vérifie $p=k{q}^n+1p=kq^n+1$ pour un certain entier k. Autrement dit, ces facteurs valent tous 1 modulo qⁿ.

Cette conclusion devient un certificat de primalité lorsque la puissance connue qⁿ dépasse la racine carrée de N. Tout facteur premier de N serait alors strictement supérieur à cette racine, ce qui est impossible si N est composé. Ce cadre général contient notamment le théorème de Proth et se rattache au test de Lucas-Lehmer.

Soit N un entier naturel supérieur à 1. Si N − 1 se décompose sous la forme $N-1=q^{n}RN-1=q^nR$, où q est premier et n au moins égal à 1, et s’il existe un entier positif a tel que $a^{N-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}N)a^\{N-1\}\backslash equiv1\backslash pmod\; N$ et $\gcd (a^{(N-1)\mathrm{/}q}-1,N)=1\backslash gcd(a^\{(N-1)/q\}-1,N)=1$, alors tout facteur premier p de N est égal à kqⁿ + 1 pour un entier k. Si, en plus, qⁿ est supérieur à √N, alors N est premier.

Le critère s’applique à un entier naturel N supérieur à 1, dont on connaît dans N − 1 une puissance qⁿ, avec q premier et n ≥ 1. Le reste R n’a pas besoin d’être entièrement factorisé. Il faut toutefois exhiber un même témoin positif a pour la congruence de Fermat et pour le contrôle par le PGCD. Pour conclure directement que N est premier avec cette version, la condition qⁿ > √N doit aussi être vérifiée.

Le nombre 15 montre un blocage concret. Avec q = 2, n = 1 et a = 4, la première congruence est satisfaite, car 4¹⁴ laisse le reste 1 modulo 15. Mais le second contrôle donne PGCD(4⁷ − 1, 15) = 3. Le témoin échoue ; il faut en chercher un autre ou employer un autre test, sans conclure à partir de la seule première congruence.

On veut certifier que N = 13 est premier. Les données sont N − 1 = 12, le nombre premier q = 2, l’exposant n = 2, le reste R = 3 et le témoin a = 2.

1. La partie factorisée convient : $13-1=12=2^2\times 313-1=12=2^2\backslash times3$. La puissance connue vaut donc qⁿ = 4.

2. La première congruence est vérifiée : $2^{12}=4096=315\times 13+12^\{12\}=4096=315\backslash times13+1$. Le reste de 2¹² modulo 13 est bien 1.

3. Pour la seconde condition, l’exposant vaut (13 − 1)/2 = 6. Or 2⁶ − 1 = 63 et PGCD(63, 13) = 1.

4. Tout facteur premier p de 13 doit donc valoir 4k + 1, et être au moins égal à 5. Comme √13 ≈ 3,606, un entier composé égal à 13 devrait au contraire avoir un facteur premier inférieur ou égal à 3,606. Cette contradiction certifie que 13 est premier. La division par 2 et par 3 fournit un contrôle direct : aucune ne tombe juste.

Pour certifier un entier N, on commence par factoriser autant que possible N − 1. Pocklington est particulièrement adapté lorsqu’une puissance première connue y dépasse déjà √N ; une factorisation complète serait alors inutile.

Pour contrôler un certificat reçu, on refait seulement les puissances modulo N, le calcul du PGCD et la comparaison avec √N. Si une condition échoue, le certificat est rejeté, mais cet échec ne prouve pas à lui seul que N est composé.

Dans la production de grands nombres premiers, notamment en cryptographie, on peut choisir des candidats dont N − 1 possède une grande partie déjà factorisée. Si cette structure manque, un autre test de primalité est préférable.

Le critère de Pocklington ne se réduit pas au test de Fermat. La congruence a^N−1 ≡ 1 modulo N ne suffit pas : pour N = 15 et a = 4, elle est vraie, tandis que le PGCD exigé vaut 3 et révèle l’échec du témoin.

Le théorème de Proth vise les entiers de la forme k · 2ⁿ + 1 sous une condition de taille sur k. Pocklington part plus largement d’une puissance première connue dans N − 1 ; 13 peut ici s’écrire avec q = 2 et R = 3.

Le test de Lucas-Lehmer est associé aux nombres de Mersenne. Pocklington se reconnaît plutôt à la factorisation partielle de N − 1 et au double contrôle portant sur un témoin a.

Les deux contrôles ne disent d’abord que ceci : tout facteur premier p de N vaut 1 modulo qⁿ. Si qⁿ ≤ √N, cette information peut être trop faible pour établir la primalité. Il faut alors factoriser une plus grande partie de N − 1 ou utiliser un critère complémentaire.

Le nombre q doit être premier et l’exposant n doit correspondre à une puissance effectivement divisant N − 1. Employer un facteur composé à la place de q, ou surestimer n, invalide l’argument sur la forme des facteurs.

Tous les calculs sont exacts et effectués modulo N. Un reste approché ou un PGCD calculé sur une valeur arrondie n’a aucun sens ici ; il faut recourir à l’arithmétique entière.

Ne pas trouver rapidement de témoin a n’est pas une preuve que N est composé. Le théorème fournit une implication : un témoin satisfaisant les conditions donne la conclusion, tandis qu’une tentative infructueuse impose seulement de poursuivre la recherche ou de changer de test.

Le glossaire nombre premier replace le verdict de primalité dans sa définition arithmétique.

La fiche Factorisation précise l’opération qui fournit la partie connue de N − 1.

Le théorème de Proth présente un critère spécialisé pour une famille d’entiers construits avec une puissance de 2.

Le test de Lucas-Lehmer montre un autre certificat spécialisé, cette fois pour les nombres de Mersenne.

La fiche PGCD détaille le calcul qui vérifie qu’aucun facteur commun ne bloque le témoin choisi.