Util Monster
Gratuit
Test de primalité · Factorisation · Génération de nombres premiers
Un nombre premier est un nombre naturel supérieur à 1 qui n'a d'autres diviseurs positifs que 1 et lui-même. Exemples : 2, 3, 5, 7, 11, 13... Tous les nombres premiers sauf 2 sont impairs. Les nombres premiers sont les « atomes des nombres ».
Un ancien algorithme développé par le mathématicien grec Ératosthène vers 240 av. J.-C. Il trouve efficacement tous les nombres premiers jusqu'à n en marquant de manière itérative les multiples de chaque nombre premier comme composites.
Les nombres premiers jumeaux sont des paires de nombres premiers qui diffèrent de 2 : (3,5), (5,7), (11,13), (17,19)... Savoir s'il en existe une infinité reste un problème non résolu.
• Chiffrement RSA : sécurité fondée sur la difficulté de factoriser de grands nombres • Fonctions de hachage : les tables de hachage de taille première réduisent les collisions • Génération de nombres aléatoires : nombres premiers dans les algorithmes PRNG • Nature : les cycles de vie des cigales utilisent des nombres premiers
Un nombre premier est un nombre naturel supérieur à 1 qui n'a pour diviseurs que 1 et lui-même. Le plus petit nombre premier est 2, le seul nombre premier pair. Suite : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Le mathématicien grec Euclide a démontré vers 300 av. J.-C. qu'il existe une infinité de nombres premiers. Les nombres premiers sont appelés les « atomes des nombres » car tout entier > 1 se factorise de manière unique en nombres premiers (théorème fondamental de l'arithmétique). Exemples : 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5.
La méthode la plus simple teste la divisibilité par tous les nombres de 2 à n-1, mais elle est inefficace. Une amélioration consiste à ne tester que de 2 à √n, car si n = a × b, alors a ≤ √n ou b ≤ √n. Pour 101 : √101 ≈ 10.05, donc on teste seulement 2, 3, 5, 7. Le test probabiliste de Miller-Rabin traite efficacement les très grands nombres. AKS (2002) est le premier algorithme déterministe en temps polynomial. La cryptographie moderne utilise des nombres de plusieurs centaines de chiffres, ce qui exige des tests efficaces.
Développé par le mathématicien grec Ératosthène vers 240 av. J.-C. Processus : ① Lister les nombres de 2 à n. ② Marquer 2 comme premier, éliminer ses multiples (4,6,8,10...). ③ Le nombre suivant non marqué, 3, est premier, éliminer ses multiples. ④ Continuer avec 5, 7, etc. jusqu'à √n. ⑤ Les nombres restants sont premiers. Pour n=30 : les nombres premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Complexité temporelle : O(n log log n). Peut trouver tous les nombres premiers inférieurs à 1 million en quelques secondes.
La factorisation en nombres premiers exprime un nombre comme un produit de nombres premiers. D'après le théorème fondamental, tout entier > 1 possède une factorisation unique. Méthode : ① Commencer par le plus petit nombre premier, 2. ② Diviser répétitivement par 2 jusqu'à ce que ce ne soit plus divisible. ③ Essayer les nombres premiers suivants 3, 5, 7... ④ Continuer jusqu'à ce que le quotient soit 1. Exemple 360 : 360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1. Résultat : 360 = 2³×3²×5. Applications : calcul du PGCD/PPCM, réduction des fractions, sécurité RSA.
Les nombres premiers jumeaux diffèrent de 2 : (3,5), (5,7), (11,13), (17,19), (29,31)... La conjecture des nombres premiers jumeaux affirme qu'il en existe une infinité, mais elle n'a pas été démontrée. En 2013, Yitang Zhang a prouvé qu'il existe une infinité de paires de nombres premiers dont l'écart est inférieur ou égal à 70 millions, puis ce seuil a été réduit à 246. Conjecture de Goldbach (1742) : tout nombre pair > 2 est la somme de deux nombres premiers. Exemples : 4=2+2, 6=3+3, 8=3+5, 10=5+5. Vérifiée jusqu'à 4×10¹⁸ mais toujours non démontrée.
Le chiffrement RSA, au cœur de la sécurité Internet, repose sur une multiplication facile mais une factorisation difficile de grands nombres premiers. Génération de clés : ① Choisir de grands nombres premiers p et q (1024+ bits chacun). ② Calculer n = p×q (public). ③ Calculer φ(n) = (p-1)(q-1). ④ Choisir un exposant public e premier avec φ(n) (généralement 65537). ⑤ Calculer l'exposant privé d tel que e×d ≡ 1 (mod φ(n)). Clé publique : (n,e), clé privée : (n,d). Chiffrement : C = M^e mod n, Déchiffrement : M = C^d mod n. Factoriser n pour trouver p,q casserait le chiffrement, mais factoriser des nombres de plusieurs centaines de chiffres prend des millions d'années. Autres applications : les tailles de tables de hachage premières réduisent les collisions, les cycles de cigales de 13/17 ans évitent le chevauchement avec les prédateurs, les rythmes premiers en musique.