Des atomes des mathématiques à la cryptographie quantique — le dictionnaire complet de la théorie des nombres : familles, théorèmes, algorithmes, applications modernes et chronologie historique.
Plus grand connu (2024)
136 M
chiffres — M136279841
Premiers sous 1 000 000
78 498
nombres premiers
Table des matières
00
Fondements et définitions
Nombre premier — définition fondatrice
Fondement
Un entier naturel p > 1 est dit premier s'il n'admet exactement que deux diviseurs distincts : 1 et lui-même. Cette définition exclut explicitement 1, qui n'a qu'un seul diviseur. Tout entier > 1 qui n'est pas premier est dit composé.
p premier ⟺ ∀d | p ⟹ d = 1 ou d = p
Les 10 premiers
2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Le cas de 2 est unique : c'est le seul nombre premier pair.
Tout entier naturel n > 1 se décompose de manière unique (à l'ordre des facteurs près) en un produit de nombres premiers. C'est pourquoi les premiers sont souvent appelés les "atomes" des mathématiques.
360 = 2³ × 3² × 5¹
Conséquence profonde
La factorisation est facile à vérifier, mais incroyablement difficile à effectuer pour de très grands nombres. Ce paradoxe est le fondement de la cryptographie RSA.
Infinité des nombres premiers
Théorème · Euclide
Euclide (~300 av. J.-C.) démontre par l'absurde qu'il existe une infinité de nombres premiers. Sa preuve est l'une des plus élégantes de l'histoire des mathématiques.
Preuve en 3 lignes
Soient p₁...pₙ tous les premiers supposés finis. Posons N = p₁ × ... × pₙ + 1. Soit q un diviseur premier de N : q ≠ pᵢ pour tout i. Contradiction.
Nombres de 1 à 50 — visualisation du crible d'Ératosthène
Nombre premier
Nombre composé
1 (ni premier, ni composé)
01
Familles et catégories de nombres premiers
Nombres premiers jumeaux
Famille
Paires de premiers de la forme (p, p+2). La conjecture des premiers jumeaux — non résolue — postule qu'il en existe une infinité. En 2013, Yitang Zhang a prouvé l'existence d'une infinité de paires de premiers avec un écart borné, ramené à 246 par le projet Polymath.
(3,5), (5,7), (11,13), (17,19), (29,31), (41,43)...
Record actuel
La plus grande paire jumelle connue dépasse 2 × 10684929.
Nombres de Mersenne
Famille
Un nombre premier de Mersenne est de la forme Mp = 2p − 1, où p est lui-même premier. Condition nécessaire mais non suffisante : tous les Mp ne sont pas premiers. En base binaire, ils s'écrivent uniquement avec des "1" consécutifs.
M₂=3, M₃=7, M₅=31, M₇=127, M₁₃=8 191...
Record mondial 2024
M136279841 est le plus grand nombre premier connu, découvert par le projet GIMPS, avec plus de 136 millions de chiffres.
Nombres de Sophie Germain
Famille
Un premier p est dit de Sophie Germain si 2p + 1 est également premier (appelé premier "sûr"). Sophie Germain les utilisa dans sa démonstration partielle du Grand Théorème de Fermat. Ils sont aujourd'hui cruciaux pour la génération de clés cryptographiques robustes.
p=2 → 2p+1=5 ✓ | p=3 → 2p+1=7 ✓ | p=11 → 2p+1=23 ✓
Nombres de Fermat
Famille
De la forme Fn = 22n + 1. Fermat conjecturait que tous étaient premiers. Seuls F₀ à F₄ le sont (3, 5, 17, 257, 65 537). Euler prouva que F₅ = 4 294 967 297 = 641 × 6 700 417. Aujourd'hui, aucun Fn pour n ≥ 5 n'est connu premier.
F₅ = 4 294 967 297 = 641 × 6 700 417
Application géométrique
F₁ à F₄ sont les seuls polygones réguliers constructibles à la règle et au compas avec un nombre de côtés de la forme 2k × F₁ × ... × Fn (Gauss, 1796).
Premiers de Wieferich
Rareté extrême
Un premier p est de Wieferich si 2p−1 ≡ 1 (mod p²). Seuls deux sont connus à ce jour : 1093 et 3511. Leur rarissime est fascinante et liée aux conjectures abc et au dernier théorème de Fermat.
21092 ≡ 1 (mod 1093²)
Premiers de Chen
Famille
Un premier p est de Chen si p + 2 est soit premier, soit produit de deux premiers (semi-premier). Jingrun Chen démontra en 1973 qu'il en existe une infinité — l'un des résultats les plus proches de la conjecture des jumeaux jamais démontré.
p=5 : p+2=7 ✓ | p=7 : p+2=9=3×3 ✓ | p=11 : p+2=13 ✓
Premiers palindromes
Récréatif
Nombres premiers se lisant identiquement de gauche à droite et de droite à gauche. Dépendent de la base de numération. En base 10, les plus petits sont 11, 101, 131, 151, 181, 191, 313, 353…
11, 101, 131, 151, 181, 191, 313, 353...
Constellations et progressions arithmétiques
Green-Tao 2004
Les triplets (p, p+2, p+6), quadruplets, etc. généralisent les jumeaux. Le théorème de Green-Tao (2004, Médaille Fields) garantit l'existence de progressions arithmétiques de premiers de toute longueur k.
5, 11, 17, 23, 29 — progression arithmétique de raison 6 (5 premiers)
Record k=27
224 584 605 939 537 911 + 81 292 139 × 23# × n, pour n=0..26 (# = primorial).
02
Arithmétique modulaire et fonctions fondamentales
Pourquoi l'arithmétique modulaire ?
L'arithmétique modulaire est "l'arithmétique de l'horloge" : 10h + 5h = 3h (mod 12). Ce cadre est indispensable pour étudier les propriétés des nombres premiers et fonde toute la cryptographie moderne.
Congruence modulaire
Outil fondamental
Dire que a ≡ b (mod n) signifie que a et b ont le même reste dans la division euclidienne par n. C'est le langage universel de la théorie des nombres, compatible avec les opérations +, −, ×.
17 ≡ 2 (mod 5) car 17 = 3×5 + 2
Petit théorème de Fermat
Théorème · 1640
Si p est premier et a non divisible par p, alors ap−1 ≡ 1 (mod p). Démontré par Euler en 1736. C'est le fondement du test de primalité de Fermat et du chiffrement RSA.
ap−1 ≡ 1 (mod p) pour p premier et p ∤ a
Vérification numérique
p=7, a=3 : 36 = 729 = 7×104 + 1, donc 36 ≡ 1 (mod 7) ✓
Théorème de Wilson
Théorème
Un entier p > 1 est premier si et seulement si (p−1)! ≡ −1 (mod p). C'est une caractérisation exacte et élégante de la primalité, bien que calculatoirement inutilisable en pratique (la factorielle croît trop vite).
(p−1)! ≡ −1 (mod p) ⟺ p est premier
Vérification pour p=5
(5−1)! = 24 = 5×4 + 4 ≡ 4 ≡ −1 (mod 5) ✓
Fonction indicatrice d'Euler φ(n)
Fonction clé
φ(n) compte les entiers k ∈ [1, n] premiers avec n (c'est-à-dire pgcd(k,n)=1). Pour p premier : φ(p) = p−1. La fonction est multiplicative. C'est le module de la clé privée en RSA : φ(n) = (p−1)(q−1).
φ(pa) = pa−1(p−1) | φ(77) = 6×10 = 60
Application RSA
p=7, q=11, n=77 : φ(77) = 60. La clé privée d est calculée modulo 60.
Théorème d'Euler (généralisation)
Théorème
Pour tout entier n, si pgcd(a,n)=1, alors aφ(n) ≡ 1 (mod n). Quand n=p (premier), φ(p)=p−1 et on retrouve Fermat. C'est le fondement théorique du chiffrement RSA pour des modules non premiers.
aφ(n) ≡ 1 (mod n) si pgcd(a,n) = 1
Nombres de Carmichael — les imposteurs
Piège
Entiers composés qui vérifient an ≡ a (mod n) pour tout entier a, trompant ainsi le test de Fermat. Le plus petit est 561 = 3×11×17. Il en existe une infinité (Alford-Granville-Pomerance, 1994). Le test de Miller-Rabin les détecte.
561 = 3 × 11 × 17 (composé mais pseudo-premier absolu)
Autres nombres de Carmichael
1 105, 1 729 (nombre de Hardy-Ramanujan !), 2 465, 2 821, 6 601...
Loi de réciprocité quadratique de Gauss
Théorème · 1796
Le "théorème fondamental" selon Gauss. Pour deux premiers impairs distincts p et q, le symbole de Legendre (a/p) = ±1 selon que a est un carré parfait modulo p ou non. La loi de réciprocité relie (p/q) et (q/p), permettant de tester la solubilité de x² ≡ a (mod p) sans calcul explicite.
(p/q)(q/p) = (−1)((p−1)(q−1)/4)
03
Conjectures et grands théorèmes
Démontré
Ouvert (non résolu)
Partiellement résolu
Hypothèse de Riemann
Ouvert · 1859 · 1 M$
La conjecture la plus célèbre des mathématiques — l'un des 7 problèmes du millénaire (prix Clay : 1 million de dollars). Tous les zéros non triviaux de la fonction zêta de Riemann ζ(s) auraient une partie réelle égale à 1/2. Sa démonstration fournirait la meilleure estimation possible de π(x).
ζ(s) = 0 (non trivial) ⟹ Re(s) = 1/2
État actuel
Plus de 1013 zéros ont été calculés numériquement, tous sur la droite critique. La conjecture demeure non prouvée depuis 165 ans.
Conjecture de Goldbach
Ouvert · 1742
Tout entier pair > 2 est somme de deux nombres premiers. Vérifiée computationnellement jusqu'à 4 × 1018, mais non démontrée. La conjecture "faible" (tout impair > 5 est somme de trois premiers) a été prouvée par Harald Helfgott en 2013.
100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53
Théorème des nombres premiers (TNP)
Démontré · 1896
Prouvé indépendamment par Hadamard et de la Vallée-Poussin. Il décrit la densité asymptotique des premiers : π(x), le nombre de premiers ≤ x, est asymptotiquement équivalent à x/ln(x). La fonction Li(x) donne une approximation encore plus précise.
π(x) ~ x / ln(x) ~ Li(x) = ∫₂ˣ dt/ln(t)
Application numérique
π(10⁶) = 78 498 ≈ 10⁶/ln(10⁶) = 72 382. Li(10⁶) ≈ 78 628 est encore plus précis.
Postulat de Bertrand
Démontré · 1852
Pour tout entier n > 1, il existe toujours au moins un nombre premier p tel que n < p < 2n. Conjecturé par Bertrand en 1845, démontré par Tchebychev en 1852. Erdős en donna une preuve élémentaire remarquable à l'âge de 19 ans.
∀n > 1, ∃p premier : n < p < 2n
Vérification
Entre 25 et 50 : on trouve 29, 31, 37, 41, 43, 47 — bien plus d'un premier.
Théorème de Green-Tao
Démontré · 2004
Médaille Fields 2006 (Terence Tao). Pour tout entier k, il existe des suites arithmétiques de longueur k constituées uniquement de nombres premiers. Résultat étonnant combinant théorie analytique des nombres et combinatoire additive.
∀k, ∃a,d : a, a+d, a+2d, ..., a+(k-1)d tous premiers
Il existe une infinité de paires (p, p+2) de nombres premiers. Zhang (2013) a prouvé l'existence d'une infinité de paires avec un écart ≤ 70 000 000, ramené à 246 par le projet Polymath. L'écart exact de 2 (vrais jumeaux) reste hors de portée.
∃ infinité de paires (p, p+2) — non prouvé
Conjecture de Legendre
Ouvert
Pour tout entier n ≥ 1, il existe au moins un nombre premier entre n² et (n+1)². Beaucoup plus fort que Bertrand, ce résultat implique que les écarts entre premiers ne croissent pas trop vite. Non prouvé malgré de nombreuses tentatives.
∀n ≥ 1, ∃p premier : n² < p < (n+1)²
04
Algorithmes de crible et tests de primalité
| Algorithme | Complexité | Type | Usage |
|---|---|---|---|
| Crible d'Ératosthène ~240 av. J.-C. |
O(n log log n) | Exact | Trouver tous les premiers jusqu'à une borne fixée |
| Crible d'Atkin 2003 |
O(n / log log n) | Exact | Version optimisée via formes quadratiques, plus rapide pour de grandes bornes |
| Test de Miller-Rabin 1976-1980 |
O(k log²n) | Probabiliste | Standard industriel en cryptographie. Erreur < 4−k par tour. |
| Test AKS Agrawal-Kayal-Saxena, 2002 |
O(log⁶n) | Déterministe | Premier test polynomial déterministe. Percée théorique majeure, plus lent en pratique. |
| Test de Lucas-Lehmer | Spécialisé | Mersenne | Test déterministe ultra-efficace dédié aux nombres de Mersenne. Utilisé par GIMPS. |
| Crible quadratique / NFS | Sous-exponentiel | Factorisation | Algorithmes de factorisation (pas de test). Menace directe à RSA si assez puissants. |
Comment fonctionne Miller-Rabin en détail
Algorithme phare
Pour tester si n est premier : (1) écrire n−1 = 2s × d avec d impair. (2) Choisir aléatoirement une base a. (3) Calculer ad mod n. (4) Si ad ≡ 1 ou a2rd ≡ −1 pour un r < s, le nombre passe le test. (5) Répéter k fois. Un composé réussit avec probabilité < (1/4)k.
Déterminisme pratique
Avec les bases {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}, Miller-Rabin est déterministe pour tout n < 3,317,044,064,679,887,385,961,981.
05
Cryptographie et applications modernes
⚠ Menace quantique imminente
L'algorithme de Shor, exécuté sur un ordinateur quantique suffisamment puissant, factorisera un module RSA de 2048 bits en quelques heures. Le NIST a finalisé en 2024 ses premiers standards de cryptographie post-quantique (CRYSTALS-Kyber, CRYSTALS-Dilithium) pour préparer la migration mondiale.
RSA (Rivest-Shamir-Adleman)
Cryptographie · 1977
L'algorithme de chiffrement asymétrique le plus déployé au monde. Sa sécurité repose sur la difficulté de factoriser le produit de deux grands premiers.
Génération : choisir deux grands premiers p et q → calculer n=pq et φ(n)=(p−1)(q−1) → choisir e premier avec φ(n) → calculer d≡e−1 (mod φ(n)). Clé publique : (n,e). Clé privée : d.
Génération : choisir deux grands premiers p et q → calculer n=pq et φ(n)=(p−1)(q−1) → choisir e premier avec φ(n) → calculer d≡e−1 (mod φ(n)). Clé publique : (n,e). Clé privée : d.
Chiffrement : c = me mod n | Déchiffrement : m = cd mod n
Taille recommandée 2025
RSA-3072 bits minimum (NIST), soit des premiers d'environ 1536 bits chacun.
Diffie-Hellman et logarithme discret
Cryptographie · 1976
Le protocole Diffie-Hellman permet à deux parties d'établir un secret partagé sur un canal public. Il repose sur la difficulté du logarithme discret : connaître ga mod p ne permet pas facilement de retrouver a. Fondement de TLS, SSH, des échanges de clés.
Alice envoie ga mod p, Bob envoie gb mod p → secret = gab mod p
Cryptographie sur courbes elliptiques (ECC)
Cryptographie
Les courbes elliptiques définies sur des corps finis Z/pZ offrent des groupes où le logarithme discret est encore plus difficile. Une clé ECC de 256 bits offre une sécurité comparable à une clé RSA de 3072 bits. Utilisée dans Bitcoin, TLS 1.3, les cartes à puce, les passeports biométriques.
y² = x³ + ax + b (mod p)
Avantage décisif
Clés 10× plus courtes qu'en RSA pour une sécurité équivalente → idéal pour IoT, mobiles et appareils à ressources limitées.
Algorithme de Shor (quantique)
Menace future
Découvert en 1994 par Peter Shor. Sur un ordinateur quantique universel avec suffisamment de qubits sans erreur, il factorise en temps polynomial, détruisant RSA, Diffie-Hellman et ECC simultanément.
Complexité classique : exp(O(n1/3)) → Shor : O(poly(log n))
État actuel (2025)
Les ordinateurs quantiques actuels n'ont pas assez de qubits logiques pour menacer RSA-2048. La migration post-quantique est néanmoins urgente dès maintenant.
Cryptographie post-quantique (PQC)
Standards NIST 2024
Algorithmes résistants aux attaques quantiques, standardisés par le NIST en août 2024 (FIPS 203, 204, 205). Ces algorithmes reposent sur des problèmes difficiles même pour les ordinateurs quantiques.
4 standards publiés
CRYSTALS-Kyber (FIPS 203) — échange de clés, réseaux euclidiens. CRYSTALS-Dilithium (FIPS 204) — signatures. FALCON — signatures NTRU. SPHINCS+ (FIPS 205) — signatures à base de hachage.
Nombres premiers dans le hachage cryptographique
Application
Les fonctions de hachage utilisent des constantes dérivées des nombres premiers pour leurs valeurs d'initialisation. SHA-256 utilise les 32 premiers bits des racines carrées des 8 premiers nombres premiers. Cette technique garantit l'absence de "trappe secrète" dans les constantes.
SHA-256 : h₀ = ⌊frac(√2) × 2³²⌋ = 6a09e66716
06
Chronologie historique
~300
av. J.-C.
av. J.-C.
Euclide — Infinité des nombres premiers
Dans ses Éléments, Euclide démontre qu'il existe une infinité de nombres premiers par l'une des preuves par l'absurde les plus célèbres de l'histoire.
~240
av. J.-C.
av. J.-C.
Ératosthène — Le crible
Ératosthène de Cyrène invente le premier algorithme systématique pour identifier les nombres premiers jusqu'à une borne donnée.
1640
Fermat — Petit théorème et nombres de Fermat
Pierre de Fermat énonce son petit théorème et conjecture à tort que tous les Fn = 22n+1 sont premiers.
1736
Euler — Preuve du petit théorème et réfutation de F₅
Euler prouve rigoureusement le petit théorème de Fermat et montre que F₅ = 641 × 6 700 417, réfutant la conjecture de Fermat.
1742
Goldbach — La conjecture
Dans une lettre à Euler, Christian Goldbach propose sa célèbre conjecture : tout entier pair > 2 est somme de deux nombres premiers.
1859
Riemann — L'hypothèse
Bernhard Riemann publie son mémoire fondateur et formule l'hypothèse qui porte son nom, reliant les nombres premiers aux zéros de ζ(s).
1896
Hadamard & de la Vallée-Poussin — Théorème des nombres premiers
Démonstration indépendante du TNP, confirmant π(x) ~ x/ln(x) et résolvant l'un des grands problèmes du XIXe siècle.
1977
RSA — La cryptographie à clé publique
Rivest, Shamir et Adleman publient RSA, transformant les nombres premiers en piliers de la sécurité informatique mondiale.
1994
Shor — L'algorithme quantique
Peter Shor découvre son algorithme quantique polynomial qui menace RSA et tous les systèmes cryptographiques basés sur la factorisation.
2002
AKS — Premier test déterministe polynomial
Agrawal, Kayal et Saxena (IIT Kanpur) publient leur algorithme révolutionnaire, résolvant un problème ouvert depuis des décennies.
2004
Green-Tao — Progressions arithmétiques de longueur arbitraire
Ben Green et Terence Tao prouvent l'existence de progressions arithmétiques de tout longueur parmi les nombres premiers (Médaille Fields 2006).
2013
Zhang & Polymath — Écarts bornés entre premiers
Yitang Zhang prouve l'existence d'une infinité de paires de premiers avec un écart borné. Le projet Polymath ramène la borne à 246.
2024
NIST — Standards post-quantiques finalisés & record Mersenne
Le NIST publie ses premiers standards PQC (FIPS 203-205) et le projet GIMPS découvre M136279841, nouveau record mondial avec 136 millions de chiffres.
07
Curiosités, records et faits insolites
Le seul nombre premier pair
Curiosité
2 est le seul nombre premier pair — et donc le seul "premier impair" par la plaisanterie des mathématiciens. Tous les autres premiers sont impairs. Conséquence : la recherche de premiers se concentre sur les impairs, traitant 2 comme un cas particulier dans presque tous les énoncés.
L'horloge des cigales et l'évolution
Nature
Certaines espèces de cigales (Magicicada) n'émergent que tous les 13 ou 17 ans — deux nombres premiers. Cette stratégie évolutive minimise les rencontres avec des prédateurs à cycles périodiques (2, 3, 4, 5, 6 ans) : le PGCD d'un premier avec tout nombre plus petit vaut toujours 1, donc les cycles ne coïncident jamais souvent.
La spirale d'Ulam
Visualisation
En 1963, Stanisław Ulam, ennuyé pendant une conférence, écrit les entiers en spirale et entoure les nombres premiers. Il observe qu'ils s'alignent préférentiellement sur des diagonales — suggérant que certains polynômes quadratiques génèrent des nombres premiers plus fréquemment que le hasard. Ce motif reste partiellement inexpliqué.
Le paradoxe de Skewes
Paradoxe
Li(x) est une meilleure approximation de π(x) que x/ln(x), et on observe que Li(x) > π(x) pour toutes les valeurs testées. Pourtant, Littlewood prouva que π(x) − Li(x) change de signe une infinité de fois. La première inversion se produirait vers 10316 — un nombre tellement grand qu'il ne peut jamais être atteint par le calcul.
GIMPS et les records mondiaux
Record
Le Great Internet Mersenne Prime Search (GIMPS), fondé en 1996, est un projet de calcul distribué. Des bénévoles prêtent leur CPU pour tester des nombres de Mersenne. Il a découvert les 17 plus grands nombres premiers connus. Le record actuel (octobre 2024) : M136279841, avec 136 279 841 chiffres.
Récompenses EFF
150 000 $ pour un premier de 100 millions de chiffres (atteint). 250 000 $ pour le premier milliard de chiffres — toujours disponible.
Le signal de contact extraterrestre dans Contact de Carl Sagan est une suite de pulses en nombres premiers. Dans L'oncle Pétros et la conjecture de Goldbach d'Apostolos Doxiadis, un mathématicien dédie sa vie à une conjecture insoluble. Le nombre 1729 — "le plus petit entier expressible comme somme de deux cubes de deux manières différentes" — est aussi appelé le nombre de Hardy-Ramanujan et est… un nombre de Carmichael.
1 Commentaires
C est concis et précis
RépondreSupprimer