test de Pocklington

Pour savoir si 31 est premier, on peut étudier 30, le nombre qui le précède. La factorisation partielle 30 = 5 × 6 fournit un facteur premier connu, 5. On choisit ensuite une base, ici 3, et l’on observe ses puissances modulo 31.

Deux vérifications arithmétiques contraignent alors tout éventuel facteur premier de 31 à laisser le reste 1 dans la division par 5. Comme le plus petit nombre premier possible de cette forme est 11, aucun ne peut être inférieur ou égal à √31. Cela exclut une décomposition de 31 en deux facteurs non triviaux.

Le test de Pocklington est un test de primalité fondé sur une factorisation, même partielle, de l’entier qui précède le candidat. Soit un entier n > 1. On écrit n − 1 = q^rm, où q est premier, r est un entier au moins égal à 1 et m est un entier.

Dans le critère cohérent, on cherche un entier a tel que $a^{n-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)a^\{n-1\}\; \backslash equiv\; 1\; \backslash pmod\; n$ et $\gcd \text{\hspace{0.17em}⁣}(a^{(n-1)\mathrm{/}q}-1,n)=1\backslash gcd\backslash !\backslash left(a^\{(n-1)/q\}-1,n\backslash right)=1$. Ces conditions impliquent que l’ordre multiplicatif de a modulo tout facteur premier p de n est divisible par q^r. Par conséquent, chaque tel facteur p vérifie $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{q}^r)p\; \backslash equiv\; 1\; \backslash pmod\; \{q^r\}$.

Cette contrainte ne prouve pas toujours à elle seule que n est premier. Elle devient décisive si elle exclut tous les facteurs premiers inférieurs ou égaux à √n. Une forme plus générale combine plusieurs puissances premières connues de n − 1 : lorsque leur produit dépasse √n et que les vérifications requises réussissent, on obtient un certificat de primalité vérifiable.

On teste n = 31 avec le facteur premier q = 5, l’exposant r = 1, le cofacteur m = 6 et la base a = 3. Ainsi, n − 1 = 30 = 5 × 6.

1. On vérifie la première congruence : $3^{30}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}31)3^\{30\}\; \backslash equiv\; 1\; \backslash pmod\; \{31\}$. Elle découle aussi de 3¹⁵ ≡ 30 ≡ −1 modulo 31.

2. On calcule 3⁶ − 1 = 728. Comme 728 = 31 × 23 + 15 et que l’algorithme d’Euclide donne pgcd(728, 31) = 1, la seconde condition est satisfaite.

3. Tout facteur premier p de 31 devrait donc vérifier p ≡ 1 modulo 5. Or √31 ≈ 5,57, tandis que le plus petit nombre premier supérieur à 1 et congru à 1 modulo 5 est 11. Un entier composé possède un facteur premier au plus égal à sa racine carrée : 31 est donc premier. Le contrôle direct confirme que 31 n’est divisible ni par 2, ni par 3, ni par 5.

Pour certifier un grand entier, on commence par factoriser autant que possible n − 1. Si la partie connue est assez grande, le test de Pocklington transforme ces facteurs connus en vérifications modulaires courtes. Le certificat obtenu peut ensuite être contrôlé sans recommencer toute la recherche.

Si n − 1 résiste à la factorisation et que sa partie connue reste trop petite, le critère ne conclut pas. On emploie alors un autre test de primalité ou l’on poursuit la factorisation de n − 1.

Pour un petit entier comme 31, les divisions par les nombres premiers jusqu’à √31 suffisent. L’exemple de Pocklington est néanmoins utile pour voir comment une information sur n − 1 devient une contrainte sur les facteurs de n.

Avec le test de Fermat. Vérifier seulement aⁿ⁻¹ ≡ 1 modulo n est une condition nécessaire pour un nombre premier lorsque a n’est pas divisible par n, mais certains nombres composés la satisfont. Pocklington ajoute une condition de pgcd liée aux facteurs connus de n − 1.

Avec la factorisation de n. Le test exploite la factorisation de n − 1 ; il ne suppose pas que les facteurs de n soient déjà connus. Dans l’exemple, on factorise 30, puis on déduit que 31 n’a aucun facteur premier possible sous sa racine carrée.

Une partie factorisée trop petite. Obtenir une congruence sur les facteurs de n ne suffit pas nécessairement à exclure tous ceux qui sont au plus égaux à √n. Il faut alors trouver davantage de facteurs de n − 1 ou choisir un autre test.

Une seule congruence ne suffit pas. Le succès de aⁿ⁻¹ ≡ 1 modulo n, sans la condition de pgcd correspondante, ne constitue pas un certificat de Pocklington. Un entier composé peut réussir cette vérification isolée.

Des conditions incompatibles. Si l’on exige simultanément a^qʳ ≡ 1 modulo n et pgcd(a^qʳ − 1, n) = 1 pour n > 1, la première relation rend le pgcd égal à n, jamais à 1. Ce couple de conditions signale donc un énoncé mal recopié ; il faut revenir à la formulation utilisant aⁿ⁻¹ et a^(n−1)/q.

Le seuil est strict. Dans la version qui combine une partie F entièrement factorisée de n − 1, la garantie usuelle demande F > √n. Une égalité F = √n n’est pas couverte par cette condition stricte.

La fiche test de primalité replace Pocklington parmi les méthodes qui décident si un entier est premier.

La notion de congruence modulo n précise le langage des restes employé dans les deux vérifications.

Le petit théorème de Fermat éclaire la première congruence et la raison pour laquelle elle ne suffit pas seule.

La fiche Factorisation développe l’opération préalable effectuée sur n − 1.