Test de nombre premier
Vérifiez si un nombre est premier, consultez sa décomposition complète en facteurs premiers et les nombres premiers voisins, criblez tous les nombres premiers d’un intervalle ou testez la primalité d’un nombre de Mersenne 2ᵖ − 1 avec le test de Lucas–Lehmer.
Rédigé par Suhaib Hassan. Chaque algorithme est classique et revérifié indépendamment. Notre méthodologie.
La primalité utilise un test de Miller–Rabin déterministe (exact, non probabiliste, pour tout entier inférieur à 2⁶⁴) ; la factorisation utilise la division d’essai ; les nombres de Mersenne utilisent le test de Lucas–Lehmer.
Il montre les véritables essais de divisibilité et les itérations de Lucas–Lehmer, et pas seulement une réponse oui/non.
—
Nombres premiers proches de n
Écarts entre nombres premiers autour du candidat.
Calcul étape par étape
—
Exemples détaillés
Un nombre premier célèbre
104 729 est-il premier ?
Oui, c’est le 10 000ᵉ nombre premier
Un nombre de Carmichael
561 est-il premier ?
Non, il est composé, bien qu’il passe, fait notoire, le test de Fermat plus simple pour toute base
Un nombre premier de Mersenne
2¹³ − 1 = 8191 est-il premier ?
Oui, 8191 est premier
Qu’est-ce qu’un nombre premier ?
Un nombre premier est un entier supérieur à 1 qui possède exactement deux diviseurs positifs : 1 et lui-même. Tout autre entier supérieur à 1 est composé et, d’après le théorème fondamental de l’arithmétique, tout nombre composé se décompose de manière unique en facteurs premiers.
Fonctionnement des tests
- Division d’essai : on teste la divisibilité par tous les entiers jusqu’à √n ; si aucun ne divise exactement, n est premier.
- Miller–Rabin (déterministe ici) : un test de primalité rapide qui, avec un ensemble fixe et prouvé de bases témoins, donne une réponse oui/non exacte pour tout n inférieur à 2⁶⁴, sans hasard ni incertitude.
- Lucas–Lehmer : pour les nombres de Mersenne Mₚ = 2ᵖ − 1 avec p premier, on itère s ← s² − 2 (mod Mₚ) à partir de s = 4 ; Mₚ est premier exactement lorsque le résultat vaut 0 après p − 2 étapes.
Par Suhaib Hassan · Vérifié le 29 septembre 2026 · Comment CalculatePilot vérifie ses formules →
Sources
- Pomerance, C., Selfridge, J. L., & Wagstaff, S. S. (1980). The pseudoprimes to 25·10⁹. Mathematics of Computation 35(151), 1003–1026.
- Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective (2nd ed.). Springer, chapitres 3–4 (Miller–Rabin, Lucas–Lehmer).
- ISO 80000-2:2019, article 6 (notation de la théorie des nombres).
Questions fréquentes
1 est-il un nombre premier ?
Non. Par définition, un nombre premier possède exactement deux diviseurs positifs distincts ; 1 n’en a qu’un seul (lui-même), il n’est donc ni premier ni composé.
Pourquoi la division d’essai n’a-t-elle besoin de vérifier que jusqu’à √n ?
Si n = a × b avec a ≤ b, alors a ≤ √n. Donc si aucun diviseur jusqu’à √n n’est trouvé, il ne peut pas en exister au-delà de √n : tout nombre composé possède au moins un facteur inférieur ou égal à sa racine carrée.
Pourquoi les nombres de Carmichael sont-ils délicats ?
Un nombre de Carmichael est composé mais vérifie le petit théorème de Fermat pour toute base première avec lui, de sorte que le simple test de primalité de Fermat le déclare à tort premier. Le test de Miller–Rabin avec des témoins appropriés l’identifie correctement comme composé.
Qu’est-ce qu’un nombre premier de Mersenne ?
Un nombre premier de la forme 2ᵖ − 1. p lui-même doit être premier (condition nécessaire mais non suffisante) : par exemple, 2¹¹ − 1 = 2047 = 23 × 89 est composé alors que 11 est premier. Les plus grands nombres premiers connus aujourd’hui sont presque tous des nombres de Mersenne, trouvés grâce au test de Lucas–Lehmer.
Combien existe-t-il de nombres premiers ?
Une infinité, ce qu’Euclide a démontré vers 300 av. J.-C. : si l’on suppose une liste finie de nombres premiers, leur produit augmenté de 1 donne toujours un nombre ayant un facteur premier absent de la liste, ce qui est une contradiction.
Pourquoi les nombres premiers sont-ils importants en cryptographie ?
Le chiffrement RSA repose sur le fait que multiplier deux grands nombres premiers est rapide, mais que retrouver ces nombres premiers à partir de leur produit est très difficile en calcul. Cette asymétrie garantit la sécurité du chiffrement.
Calculateurs associés
Poursuivez avec la théorie des nombres.