pseudo-premier d'Euler

Prenez 561 : ses facteurs 3, 11 et 17 prouvent qu’il n’est pas premier. Pourtant, élevé à une puissance bien choisie puis réduit modulo 561, le nombre 2 donne exactement le résultat attendu pour un nombre premier. 561 passe donc ce contrôle en base 2 sous une fausse identité.

Un pseudo-premier d’Euler est précisément un entier composé capable de produire ce faux positif pour une base donnée. Le test filtre mieux les imposteurs que le seul test de Fermat, sans constituer une preuve absolue de primalité.

Soit un entier impair composé n et une base entière a première avec n. La version faible du test d’Euler examine le reste de a élevé à la puissance (n − 1)/2 dans la division par n. L’entier n est un pseudo-premier d’Euler en base a lorsque ce reste vaut 1 ou −1 : $a^{(n-1)\mathrm{/}2}\equiv \pm 1(\mathrm{m}\mathrm{o}\mathrm{d}n)a^\{(n-1)/2\}\; \backslash equiv\; \backslash pm\; 1\; \backslash pmod\; n$. La propriété dépend de la base choisie.

Le test d’Euler–Jacobi impose une égalité plus précise. Le symbole de Jacobi de a modulo n, noté $\left(\frac{a}{n}\right)\backslash left(\backslash frac\{a\}\{n\}\backslash right)$, vaut 1 ou −1 dans ce cadre. Un pseudo-premier d’Euler–Jacobi en base a est un entier composé qui vérifie $a^{(n-1)\mathrm{/}2}\equiv \left(\frac{a}{n}\right)(\mathrm{m}\mathrm{o}\mathrm{d}n)a^\{(n-1)/2\}\; \backslash equiv\; \backslash left(\backslash frac\{a\}\{n\}\backslash right)\; \backslash pmod\; n$. Ainsi, satisfaire seulement la condition ±1 ne suffit pas toujours à satisfaire la variante Euler–Jacobi.

Pour un nombre premier impair n qui ne divise pas a, le critère d’Euler garantit cette dernière congruence. Pour un entier composé, sa réussite ne donne qu’un verdict de « premier probable » pour la base a, jamais une preuve de primalité.

On rencontre cette notion dans un calcul de primalité portant sur un entier impair. Quatre éléments la signalent : un candidat n, une base a, une réduction modulo n et l’exposant moitié de n − 1. La mention du symbole de Jacobi indique la variante Euler–Jacobi.

Le support peut être un exercice d’arithmétique modulaire ou une étape d’un algorithme qui sélectionne de grands nombres premiers. Le résultat porté par ce calcul est un statut provisoire : l’entier échoue comme composé, ou passe comme premier probable pour la base testée.

La grandeur lue est le reste modulo n. Pour interpréter un test d’Euler–Jacobi, on suit quatre étapes ordonnées.

1. On vérifie que n est impair et que la base a est première avec n.
2. On calcule le symbole de Jacobi $\left(\frac{a}{n}\right)\backslash left(\backslash frac\{a\}\{n\}\backslash right)$.
3. On calcule a^{(n − 1)/2} modulo n, de préférence par exponentiation rapide.
4. On compare les deux restes modulo n : une différence prouve que n est composé ; une égalité laisse seulement n premier probable pour cette base.

Le piège visuel consiste à prendre le reste 1 ou −1 pour une preuve. Le bon réflexe est de regarder le verdict, la base et la variante du test : « passe en base a » ne signifie pas « est premier ».

Testons 561 en base 2. Les données sont n = 561 = 3 × 11 × 17, a = 2, l’exposant (561 − 1)/2 = 280 et le reste de 561 modulo 8 égal à 1.

1. La factorisation montre immédiatement que 561 est composé. De plus, 2 n’a aucun facteur commun avec 561.

2. Comme 561 ≡ 1 modulo 8, la règle du symbole de Jacobi pour 2 donne $\left(\frac{2}{561}\right)=1\backslash left(\backslash frac\{2\}\{561\}\backslash right)=1$.

3. Les réductions successives donnent 2¹⁰ ≡ 463 modulo 561, puis 2²⁰ ≡ 67 modulo 561 et enfin 2⁴⁰ ≡ 1 modulo 561.

4. Puisque 280 = 7 × 40, on obtient 2²⁸⁰ ≡ 1⁷ ≡ 1 modulo 561.

Le reste calculé et le symbole de Jacobi valent tous deux 1. Ainsi, 561 passe le test d’Euler–Jacobi en base 2, alors que sa factorisation prouve qu’il est composé : c’est bien un pseudo-premier d’Euler–Jacobi pour cette base. Le contrôle peut être refait en vérifiant que 67² = 4 489 = 8 × 561 + 1.

Dans un exercice, le test sert à fabriquer un certificat rapide de composition : dès que la congruence attendue échoue, le candidat est composé. Si elle réussit, il faut conserver la mention de la base et poursuivre l’examen.

Dans un programme de génération de grands nombres premiers, plusieurs tests éliminent rapidement de nombreux candidats. Quand une preuve formelle est exigée, un test probabiliste réussi est remplacé ou complété par une méthode qui fournit un certificat de primalité.

En cryptologie, cette différence de verdict est décisive : un entier destiné à jouer le rôle d’un nombre premier ne doit pas être accepté sur la seule réussite d’une base.

Un pseudo-premier de Fermat en base a est un entier composé n tel que a est premier avec n et a^{n − 1} ≡ 1 modulo n. Le test d’Euler examine déjà la demi-puissance : un entier peut donc passer Fermat tout en échouant à Euler.

Un nombre de Carmichael est composé et passe le test de Fermat pour toute base première avec lui. Ce comportement global ne le rend pas automatiquement pseudo-premier d’Euler–Jacobi pour chaque base.

Un nombre premier satisfait le critère d’Euler pour toutes les bases admissibles. La réussite d’un pseudo-premier peut dépendre de la base ; les nombres de Carmichael font exception dans le cadre de Fermat, où ils passent pour toute base première avec eux. Sa composition peut être établie par une factorisation comme 561 = 3 × 11 × 17.

La réussite dépend de la base. Le symptôme trompeur est un verdict présenté sans « en base a ». Il faut consigner la base testée et ne jamais transformer un résultat local en propriété absolue.

Si a et n ont un facteur commun supérieur à 1, le cadre habituel du critère n’est pas satisfait. Si 1 < pgcd(a, n) < n, ce calcul fournit un diviseur propre de n et prouve que n est composé. Si pgcd(a, n) = n, la base n’est pas admissible, mais ce calcul seul ne permet pas de conclure que n est composé.

La condition faible a^{(n − 1)/2} ≡ ±1 et la condition Euler–Jacobi ne sont pas synonymes. Dans la seconde, le signe doit être précisément celui du symbole de Jacobi. Vérifier seulement « plus ou moins un » peut donc accepter un entier que la comparaison complète rejetterait.

Même l’égalité Euler–Jacobi peut réussir pour un composé : 561 en base 2 en est un cas charnière explicite. Il faut multiplier les contrôles indépendants ou employer un test avec certificat lorsque la primalité doit être démontrée.

Le critère d’Euler explique pourquoi la congruence est garantie pour un nombre premier impair.

Le symbole de Jacobi donne le signe exact auquel comparer la puissance dans la variante Euler–Jacobi.

Le petit théorème de Fermat fournit le test plus faible dont le critère d’Euler affine le filtrage.

Le nombre de Carmichael montre jusqu’où un entier composé peut résister aux tests fondés sur Fermat.