Histoire et cultureNotion · Glossaire
test de primalité
Un test de primalité est un algorithme qui détermine si un entier est premier, c’est-à-dire s’il est supérieur ou égal à 2 et n’a pour diviseurs positifs que 1 et lui-même. Un test déterministe donne une réponse certaine, tandis qu’un test probabiliste fournit un verdict assorti d’un risque d’erreur contrôlé, que des répétitions permettent généralement de réduire. Ces tests servent notamment à rechercher les grands nombres premiers utilisés en cryptographie.
Sommaire
Ce que vous allez apprendre
- Identifier ce que décide un test de primalité.
- Refaire le test élémentaire de 91 et contrôler son verdict.
- Différencier un verdict déterministe d'un verdict probabiliste.
- Reconnaître les limites d'un test de pseudoprimalité.
En clair
Prenons l'entier 91. Pour savoir s'il est premier, on cherche si un entier autre que 1 et 91 le divise sans reste. Les essais par 2, 3 et 5 échouent, mais 7 convient : 91 = 7 × 13. Un test de primalité organise ce type de vérification pour annoncer « premier » ou « composé ».
Pour de très grands entiers, essayer naïvement beaucoup de diviseurs devient coûteux. Des algorithmes exploitent alors des propriétés arithmétiques : certains garantissent le verdict, tandis que d'autres acceptent une probabilité d'erreur contrôlée.
Définition
Un test de primalité prend en entrée un entier et cherche à décider s'il est premier, donc s'il possède exactement deux diviseurs positifs : 1 et lui-même. Si un entier supérieur ou égal à 2 admet un autre diviseur, il est composé. Les entiers 0 et 1 ne sont ni premiers ni composés.
Un test déterministe conclut avec certitude. Un test probabiliste, tel que Miller–Rabin lorsqu'il emploie des bases choisies aléatoirement, peut déclarer un entier « probablement premier » avec une erreur dont la probabilité est contrôlée par la répétition. Un test de pseudoprimalité vérifie une propriété nécessaire à la primalité : son échec prouve que l'entier est composé, mais sa réussite ne suffit pas toujours à établir qu'il est premier.
Le test de Fermat repose sur le petit théorème de Fermat. Lucas–Lehmer concerne des entiers d'une forme particulière, tandis que Solovay–Strassen et Miller–Rabin sont des tests probabilistes classiques. Le crible d'Ératosthène produit les nombres premiers jusqu'à une borne plutôt que de tester isolément un seul entier. Proposé en 2002 par Agrawal, Kayal et Saxena, AKS fut le premier test déterministe de primalité démontré polynomial.
Un exemple, pas à pas
On veut tester l'entier 91 par recherche de petits diviseurs. Les données sont le candidat 91 et les nombres premiers 2, 3, 5 et 7, qui ne dépassent pas sa racine carrée.
1. Essayons 2 : 91 est impair, donc 2 ne le divise pas.
2. Essayons 3 : la somme des chiffres vaut 9 + 1 = 10, qui n'est pas divisible par 3.
3. Essayons 5 : le dernier chiffre n'est ni 0 ni 5.
4. Essayons 7 : la division tombe juste, car . Le diviseur 7 est un témoin de composition.
Le test s'arrête : 91 est composé. Le contrôle est refaisable en multipliant 7 par 13 ; on retrouve exactement 91.
En pratique
Pour un petit entier, la recherche de diviseurs suffit souvent. Dès qu'un diviseur est trouvé, le calcul s'arrête et fournit une preuve concrète que l'entier est composé.
Pour de grands candidats en cryptographie, un test probabiliste comme Miller–Rabin est privilégié lorsqu'un verdict rapide avec un risque contrôlé convient. Plusieurs répétitions réduisent ce risque.
Lorsqu'une preuve certaine est exigée, on retient un test déterministe ou une procédure de certification. Le choix dépend donc de la taille de l'entier, de sa forme éventuelle et du niveau de certitude demandé.
À ne pas confondre
Test de primalité et crible d'Ératosthène. Le premier reçoit un entier et rend un verdict sur cet entier. Le second énumère les nombres premiers jusqu'à une borne. Pour examiner seulement 91, on parle d'un test ; pour dresser la liste jusqu'à 100, d'un crible.
Nombre premier et nombres premiers entre eux. La primalité concerne un entier seul. Deux entiers sont premiers entre eux lorsque leur seul diviseur positif commun est 1. Ainsi, 8 et 9 sont premiers entre eux, bien qu'aucun des deux ne soit premier.
Test et factorisation. Un test doit décider « premier » ou « composé ». Une factorisation doit trouver tous les facteurs premiers. L'égalité 91 = 7 × 13 accomplit les deux tâches ici, mais un témoin de composition suffit au test.
Limites et pièges
0 et 1. L'entier 1 possède un seul diviseur positif, tandis que 0 en possède une infinité. Un programme doit classer ces deux entiers « non premiers », sans pour autant les appeler composés.
Probablement premier ne signifie pas prouvé premier. La réussite d'un test probabiliste laisse un risque d'erreur contrôlé. Si une certitude mathématique est requise, il faut répéter selon le risque admis puis employer une preuve ou un test déterministe.
Réussir un test de pseudoprimalité ne suffit pas toujours. Un entier composé peut satisfaire la propriété vérifiée pour une base donnée. Il faut changer de base, utiliser un test plus discriminant ou produire un certificat.
La forme de l'entier compte. Lucas–Lehmer vise une famille particulière d'entiers ; il ne constitue pas une procédure générale pour tout candidat. Avant de l'appliquer, il faut vérifier que l'entier possède la forme exigée.
Pour aller plus loin
Le glossaire nombre premier précise le critère que tout test cherche à décider.
Le test de Miller-Rabin approfondit le fonctionnement d'un test probabiliste et la portée de son verdict.
Le petit théorème de Fermat présente la propriété arithmétique sur laquelle repose le test de Fermat.
Le crible d'Eratosthène montre comment obtenir tous les nombres premiers jusqu'à une borne donnée.
La fiche cryptographie situe l'usage des grands nombres premiers dans la protection de l'information.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres