ArithmétiqueNotion · Glossaire
Solovay-Strassen (test de primalité de)
Le test de primalité de Solovay-Strassen compare deux résultats calculés à partir du même entier n et d’une base a. S’ils diffèrent modulo n, l’entier est certainement composé. S’ils coïncident, il est seulement probablement premier : répéter le test avec d’autres bases réduit le risque d’erreur. Le symbole de Jacobi et le critère d’Euler fournissent les deux résultats à comparer.
Sommaire
Ce que vous allez apprendre
- Relier le symbole de Jacobi au résidu du critère d’Euler.
- Refaire un tour complet du test sur l’entier 15 avec la base 2.
- Interpréter correctement un témoin de composition et un verdict probablement premier.
- Calculer la borne d’erreur après plusieurs tours indépendants.
En clair
Prenons 15 et choisissons la base 2. Deux calculs donnent alors des résultats qui devraient coïncider si 15 était premier. Le symbole de Jacobi donne 1, tandis qu’une puissance de 2 laisse le reste 8 après division par 15. Cette contradiction démasque aussitôt un nombre composé.
Le test de Solovay-Strassen répète cette confrontation avec des bases choisies au hasard. Une base qui produit une contradiction constitue une preuve de composition. Une base qui passe le contrôle ne prouve pas la primalité, mais plusieurs succès indépendants rendent une erreur de moins en moins probable.
Définition
Le test de Solovay-Strassen est un test probabiliste de primalité à erreur unilatérale. Il s’applique à un entier impair n supérieur à 2. À chaque tour, on choisit une base entière a telle que 1 ≤ a < n. Si le plus grand commun diviseur de a et n dépasse 1, un diviseur non trivial est trouvé et n est composé.
Lorsque a et n sont premiers entre eux, le symbole de Jacobi, noté J(a,n), vaut 1 ou −1. Le critère d’Euler impose à tout nombre premier n la congruence suivante : . Dans la comparaison modulo n, la valeur −1 du symbole correspond au reste n − 1. Si la congruence échoue, a est un témoin d’Euler-Jacobi et n est certainement composé.
Si la congruence réussit, le verdict du tour est seulement « probablement premier ». Un nombre premier passe toujours. Pour tout entier composé admissible, au moins la moitié des bases possibles révèlent la composition. Après k tours indépendants réussis, la probabilité qu’un entier composé ait échappé à tous les contrôles est donc au plus .
Un exemple, pas à pas
Données. L’entier testé est n = 15 et la base choisie est a = 2. L’exposant du critère d’Euler vaut (15 − 1)/2 = 7.
1. Contrôler le diviseur commun. Le plus grand commun diviseur de 2 et 15 vaut 1. Aucun facteur de 15 n’est donc découvert à cette étape.
2. Calculer le symbole de Jacobi. Comme 15 = 3 × 5, on décompose le symbole. La règle complémentaire pour 2 donne J(2,m) = −1 lorsque l’entier impair m laisse le reste 3 ou 5 modulo 8. C’est le cas de 3 et de 5, donc .
3. Calculer le résidu d’Euler. On élève 2 à la puissance 7 : 27 = 128. Or 128 = 8 × 15 + 8, donc le reste modulo 15 vaut 8.
4. Comparer. Le symbole annonce le reste 1, mais la puissance donne 8. La congruence exigée échoue : la base 2 est un témoin et 15 est composé.
Le contrôle est refaisable directement : 15 = 3 × 5 confirme le verdict. Le test a certifié la composition sans avoir besoin de connaître ces deux facteurs à l’avance.
En pratique
Pour écarter rapidement un candidat premier, on lance un tour avec une base aléatoire. La moindre divergence entre le symbole de Jacobi et le résidu d’Euler arrête le calcul : le candidat est composé.
Quand plusieurs tours réussissent, on fixe leur nombre d’après le risque maximal accepté. Dix succès indépendants bornent par exemple la probabilité d’erreur par 2−10, soit 1/1 024, pour un entier composé.
Si une preuve absolue de primalité est exigée, le verdict « probablement premier » ne suffit pas : il faut employer ensuite une méthode de certification. En revanche, un verdict « composé » de Solovay-Strassen est déjà certain.
À ne pas confondre
Test de Fermat. Il compare une puissance à 1 modulo l’entier testé, sans faire intervenir le symbole de Jacobi. Sur 15 avec la base 2, Solovay-Strassen tranche en comparant précisément les restes 1 et 8.
Factorisation. Déclarer un entier composé ne signifie pas nécessairement produire ses facteurs. Dans l’exemple, la divergence suffit au verdict, même si le contrôle 15 = 3 × 5 fournit ensuite la décomposition.
Preuve de primalité. Un témoin qui échoue prouve que le nombre est composé. Des bases qui réussissent ne constituent qu’un résultat probabiliste ; elles ne délivrent pas, à elles seules, un certificat vérifiable de primalité.
Limites et pièges
Entrées paires et petites. Le protocole décrit vise les entiers impairs n > 2. Un entier pair supérieur à 2 est déjà composé ; 2 est premier et doit être traité directement.
Base non première avec n. Si le plus grand commun diviseur de a et n dépasse 1, le symbole de Jacobi vaut 0. Il ne faut pas poursuivre la comparaison : ce diviseur commun établit immédiatement la composition.
Succès isolé. Une base peut masquer un entier composé. Le symptôme trompeur est une congruence satisfaite ; le bon verdict reste « probablement premier », puis le test doit être répété avec des bases indépendantes.
Borne probabiliste. Après k tours indépendants, 2−k est une borne conditionnelle pour un entier composé, pas la probabilité qu’un entier donné soit premier. Le choix des bases doit rester aléatoire et indépendant pour appliquer cette borne.
Pour aller plus loin
Le symbole de Jacobi détaille le calcul arithmétique placé au cœur de chaque tour.
Le critère d’Euler explique la congruence que toute base admissible vérifie modulo un nombre premier.
La fiche test de primalité replace Solovay-Strassen parmi les méthodes qui décident ou estiment la primalité d’un entier.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres