Test de primalite
Testez si un nombre (meme tres grand) est premier avec le test de Miller-Rabin. Factorisation si composite.
Miller-Rabin
Supporte les tres grands entiers (pas de limite de taille)
Tout savoir sur le test de primalité Miller-Rabin
Pourquoi utiliser le test de primalité Miller-Rabin ?
Le test de Miller-Rabin est l'algorithme probabiliste de référence pour déterminer si un entier est premier, en particulier lorsque les nombres atteignent des dizaines ou des centaines de chiffres. Contrairement aux méthodes déterministes comme le crible d'Ératosthène, il ne nécessite pas de parcourir tous les diviseurs potentiels, ce qui le rend extrêmement performant même pour des entiers de plusieurs milliers de bits. C'est la raison pour laquelle il est adopté dans la quasi-totalité des bibliothèques cryptographiques modernes.
L'algorithme repose sur le petit théorème de Fermat et ses extensions : pour chaque témoin (witness) choisi aléatoirement, il vérifie si le nombre candidat satisfait certaines congruences modulaires qui ne peuvent être vraies que si le nombre est premier. En répétant le test avec plusieurs témoins indépendants, la probabilité d'une erreur (c'est-à-dire de déclarer premier un nombre composite) devient astronomiquement faible — inférieure à 4⁻ᵏ pour k tours, soit moins d'une chance sur un trillion avec seulement 20 itérations. Pour les applications pratiques, ce niveau de certitude est largement suffisant.
Dans le domaine de la cryptographie à clé publique, notamment RSA et les courbes elliptiques, la génération de grands nombres premiers est une opération critique qui conditionne la sécurité de millions de communications chaque seconde. Utiliser un outil en ligne basé sur Miller-Rabin permet aux développeurs, aux étudiants et aux chercheurs de valider rapidement leurs implémentations, de tester des hypothèses mathématiques ou de comprendre le comportement de l'algorithme sans avoir à configurer un environnement de développement complet.
Cas d'utilisation courants
- Cryptographie RSA et génération de clés
- La sécurité du chiffrement RSA repose entièrement sur la difficulté de factoriser le produit de deux grands nombres premiers. Avant de générer une paire de clés RSA-2048 ou RSA-4096, les développeurs doivent s'assurer que les nombres p et q choisis sont effectivement premiers. Le test Miller-Rabin permet de valider ces candidats en quelques millisecondes, même pour des entiers de 1024 bits ou plus.
- Protocoles à courbes elliptiques (ECC)
- Les algorithmes de cryptographie sur courbes elliptiques tels qu'ECDSA ou ECDH requièrent des paramètres de courbe soigneusement choisis, dont certains doivent être des nombres premiers. Vérifier la primalité des ordres de groupes ou des modules de réduction est une étape indispensable lors de la conception ou de l'audit de ces protocoles. Cet outil offre une validation rapide et fiable pour ces vérifications.
- Enseignement des mathématiques et de l'algorithmique
- Les cours de théorie des nombres, d'algorithmique et de cryptographie font régulièrement référence au test de Miller-Rabin comme exemple canonique d'algorithme probabiliste. Disposer d'un outil interactif permet aux étudiants d'expérimenter directement avec des nombres de leur choix, d'observer la décomposition en facteurs premiers lorsque le nombre est composite, et de mieux comprendre les fondements mathématiques sous-jacents.
- Audit et vérification de bibliothèques cryptographiques
- Les auditeurs en sécurité et les ingénieurs DevSecOps ont régulièrement besoin de vérifier que les nombres premiers générés par une bibliothèque tierce sont bien premiers, ou que certains paramètres cryptographiques respectent les spécifications attendues. Cet outil permet une vérification indépendante instantanée, sans dépendance externe ni risque d'exposition des données sensibles.
Comment fonctionne le test de primalité Miller-Rabin ?
Préparation du candidat : l'entier n saisi est d'abord soumis à des vérifications préliminaires rapides — élimination des cas triviaux (n < 2, n pair, divisibilité par les petits premiers jusqu'à 1000). Si n passe ces filtres, il est écrit sous la forme n − 1 = 2ˢ × d, où d est impair, ce qui prépare la structure nécessaire aux tests de congruence modulaire.
Itérations probabilistes avec témoins aléatoires : pour chaque tour (typiquement 20 à 40), un témoin a est choisi aléatoirement dans l'intervalle [2, n − 2]. L'algorithme calcule aᵈ mod n par exponentiation modulaire rapide, puis effectue s élévations au carré successives. Si aucune des valeurs intermédiaires ne respecte les conditions du théorème de Miller, le nombre est déclaré composé avec certitude absolue. Si toutes les conditions sont satisfaites, le nombre est déclaré «probablement premier» pour ce témoin.
Résultat et factorisation : si n est déclaré composé, l'outil tente une factorisation partielle à l'aide de l'algorithme rho de Pollard, qui retrouve efficacement les facteurs premiers non triviaux même pour de très grands entiers. Si n est déclaré premier après tous les tours, la probabilité d'erreur est inférieure à 4⁻⁴⁰, ce qui représente un niveau de confiance cryptographique standard. Le résultat complet (statut, facteurs, témoins utilisés) est affiché instantanément dans le navigateur.
Questions fréquentes
- Quelle est la taille maximale des nombres que cet outil peut tester ?
- L'outil s'appuie sur l'arithmétique en précision arbitraire (BigInt) disponible nativement dans les navigateurs modernes, ce qui signifie qu'il n'y a pas de limite stricte imposée par le logiciel. En pratique, des nombres de plusieurs milliers de chiffres décimaux (soit plusieurs milliers de bits) peuvent être testés en moins d'une seconde. Pour des entiers au-delà de 10 000 bits, le temps de calcul peut augmenter de façon perceptible selon les performances du terminal utilisé.
- Le test de Miller-Rabin peut-il se tromper et déclarer premier un nombre composite ?
- Théoriquement oui, mais avec une probabilité extrêmement faible. Un nombre composite qui trompe un témoin aléatoire est appelé un pseudopremier de Miller-Rabin. La probabilité qu'un nombre composite passe k tours indépendants est au plus 4⁻ᵏ. Avec 40 tours, cette probabilité est inférieure à 10⁻²⁴, ce qui est bien en deçà de la probabilité d'une erreur matérielle aléatoire dans un processeur moderne. Pour des applications où une certitude absolue est requise, il existe des variantes déterministes de Miller-Rabin valables pour des plages de nombres définies.
- Quelle est la différence entre un test probabiliste et un test déterministe de primalité ?
- Un test déterministe garantit avec une certitude absolue que le résultat est correct, mais son coût computationnel est généralement beaucoup plus élevé. Le test AKS (Agrawal-Kayal-Saxena), premier algorithme déterministe polynomial prouvé, est par exemple bien plus lent que Miller-Rabin en pratique. Un test probabiliste comme Miller-Rabin peut théoriquement produire un faux positif, mais avec une probabilité si infime qu'il est considéré comme sûr pour toutes les applications cryptographiques réelles. La cryptographie moderne utilise systématiquement des tests probabilistes pour la génération de clés.
- Pourquoi utilise-t-on la factorisation de Pollard rho lorsque le nombre est composite ?
- L'algorithme rho de Pollard est une méthode de factorisation heuristique particulièrement efficace pour trouver les petits facteurs premiers d'un grand entier composite. Sa complexité en temps est sous-exponentielle — de l'ordre de O(n^(1/4)) opérations — ce qui le rend bien plus rapide que la division par essais pour des entiers à plusieurs dizaines de chiffres. Lorsqu'un nombre est déclaré composite par Miller-Rabin, afficher sa décomposition en facteurs premiers apporte une valeur pédagogique et pratique immédiate, permettant de comprendre pourquoi il n'est pas premier.
- Mes données personnelles sont-elles protégées ?
- Entièrement. Le calcul est réalisé à 100 % côté client, directement dans votre navigateur web. Aucune donnée personnelle n'est envoyée vers un serveur distant ni stockée. Toutes les informations restent sur votre appareil.