Le 12 octobre 2024, Luke Durant, un chercheur californien de 36 ans, ancien employé de NVIDIA, a confirmé le plus grand nombre premier connu : 2 puissance 136 279 841, moins 1. Écrit en entier, il compte 41 024 320 chiffres. Pour le trouver, il a fait travailler des milliers de cartes graphiques de serveurs, louées dans des centres de données de 17 pays. Et pourtant, on sait depuis plus de deux mille ans qu'il existe des nombres premiers encore plus grands : Euclide l'a démontré en quelques lignes, sans calculatrice.
Les nombres premiers sont à la fois l'un des plus vieux objets des mathématiques et l'un des plus utiles aujourd'hui. Ils sont au cœur de RSA, un système de chiffrement inventé en 1977 et toujours utilisé. Voici ce qu'ils sont, pourquoi ils ne s'arrêtent jamais, et comment ils gardent un secret.
Qu'est-ce qu'un nombre premier ?
Un nombre premier est un entier naturel qui a exactement deux diviseurs : 1 et lui-même. 2, 3, 5, 7, 11 et 13 sont premiers ; 12 ne l'est pas, puisqu'il se divise par 2, 3, 4 et 6.
Le nombre 1 n'est pas premier : il n'a qu'un seul diviseur. Et ce choix a une raison : tout entier supérieur ou égal à 2 s'écrit comme un produit de nombres premiers, et cette écriture est unique à l'ordre près : 360 = 2³ × 3² × 5, et pas autrement. Si 1 était premier, on pourrait écrire 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3, et l'unicité disparaîtrait. Les nombres premiers sont les briques de base de la multiplication : c'est tout l'enjeu du chapitre d'arithmétique de 3e.
Le crible d'Ératosthène : trouver les nombres premiers à la main
La méthode la plus simple pour les lister est attribuée à Ératosthène de Cyrène (276 – 194 avant notre ère), qui dirigea la bibliothèque d'Alexandrie. Pour trouver les nombres premiers jusqu'à 100 :
- On écrit tous les entiers de 2 à 100.
- 2 est premier. On barre tous ses multiples : 4, 6, 8, 10…
- Le premier nombre non barré, 3, est premier. On barre ses multiples : 9, 15, 21… (6, 12 et 18 le sont déjà).
- On recommence avec 5, puis avec 7.
- On s'arrête là : le nombre premier suivant est 11, et 11 × 11 = 121 dépasse 100. Tout nombre composé jusqu'à 100 a un diviseur premier inférieur ou égal à 10, donc il est déjà barré.
Il reste 25 nombres : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 et 97. Ce crible reste efficace : c'est lui qui a servi à recompter, pour cet article, les 5 761 455 nombres premiers inférieurs à cent millions.
La preuve d'Euclide : il y en a une infinité
Dans le livre IX des Éléments, proposition 20, Euclide affirme que les nombres premiers sont plus nombreux que n'importe quelle quantité de nombres premiers qu'on se donne. Autrement dit, aucune liste finie ne les contient tous. Voici son raisonnement, en langage d'aujourd'hui.
- Prends n'importe quelle liste finie de nombres premiers, par exemple 2, 3 et 5.
- Multiplie-les : N = 2 × 3 × 5 = 30. Chaque nombre de la liste divise N.
- Ajoute 1 : N + 1 = 31.
- N + 1 est plus grand que 1, donc il a au moins un diviseur premier. Son plus petit diviseur supérieur à 1 convient : s'il n'était pas premier, il aurait lui-même un diviseur plus petit, qui diviserait aussi N + 1.
- Ce diviseur premier ne peut pas être dans la liste. S'il divisait à la fois N et N + 1, il diviserait leur différence, qui vaut 1. C'est impossible.
- On a donc trouvé un nombre premier qui n'était pas dans la liste. Comme la liste de départ était quelconque, aucune liste finie n'est complète.
On présente souvent cette preuve comme un raisonnement par l'absurde partant de « la liste de tous les nombres premiers ». Euclide procède plus directement : à partir de trois nombres premiers donnés, il construit un nombre qui est soit premier et nouveau, soit divisible par un nombre premier nouveau. L'absurde ne sert qu'à montrer que ce diviseur est hors de la liste.
L'erreur classique : « le produit plus un est toujours premier »
En essayant la preuve sur les premiers nombres premiers, on tombe sur une série troublante :
- 2 + 1 = 3, premier ;
- 2 × 3 + 1 = 7, premier ;
- 2 × 3 × 5 + 1 = 31, premier ;
- 2 × 3 × 5 × 7 + 1 = 211, premier ;
- 2 × 3 × 5 × 7 × 11 + 1 = 2 311, premier.
Il est tentant d'en conclure que ce nombre est toujours premier. C'est faux. Au cran suivant, 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30 031 = 59 × 509. Aucun des nombres 2, 3, 5, 7, 11 et 13 ne divise 30 031 (le reste vaut 1 à chaque fois), mais 30 031 n'est pas premier pour autant : ses facteurs premiers, 59 et 509, sont simplement absents de la liste. C'est exactement ce que garantit la preuve. Le cran d'après donne 510 511 = 19 × 97 × 277.
Autre subtilité : le nombre premier « nouveau » n'est pas forcément plus grand que ceux de la liste. Avec la liste 3 et 5, on obtient 3 × 5 + 1 = 16 = 2⁴, et le nombre premier manquant est 2.
Comment les nombres premiers se répartissent
De plus en plus rares
Il y a 25 nombres premiers jusqu'à 100, 168 jusqu'à 1 000, 78 498 jusqu'à un million et 5 761 455 jusqu'à cent millions. Leur proportion baisse (25 %, puis 7,8 %, puis 5,8 %), mais lentement et très régulièrement.
Le théorème des nombres premiers décrit cette régularité : le nombre de premiers inférieurs à x est à peu près x ÷ ln x, où ln désigne le logarithme népérien. Legendre et Gauss l'avaient conjecturé, et Jacques Hadamard et Charles-Jean de La Vallée Poussin l'ont démontré en 1896. Pour un million, la formule donne 72 382, contre 78 498 en réalité : l'écart relatif, encore proche de 8 %, se réduit très lentement quand x grandit.
Autour d'un nombre x, l'écart moyen entre deux nombres premiers consécutifs vaut donc environ ln x : entre 900 000 et 1 000 000, il est de 13,8, et ln(1 000 000) ≈ 13,8.
Des déserts aussi longs qu'on veut
On peut même fabriquer des déserts sans nombre premier aussi longs qu'on veut. Prends 10! = 1 × 2 × 3 × … × 10 = 3 628 800. Alors 10! + 2 est divisible par 2, 10! + 3 par 3, et ainsi de suite jusqu'à 10! + 10, divisible par 10 : voilà neuf nombres composés consécutifs. Avec 101! + 2, …, 101! + 101, on en obtient cent. En dessous d'un million, le plus grand trou sépare 492 113 de 492 227 : 113 nombres composés d'affilée.
Les nombres premiers jumeaux, un problème ouvert
À l'inverse, certains nombres premiers ne sont séparés que de 2 : 3 et 5, 11 et 13, 17 et 19, 29 et 31… On en compte 8 169 paires en dessous d'un million. La conjecture des nombres premiers jumeaux affirme qu'il en existe une infinité. Personne ne sait le démontrer.
En 2013, Yitang Zhang a prouvé qu'il existe une infinité de paires de nombres premiers séparés d'au plus 70 millions. Un projet collaboratif en ligne, Polymath, a ensuite abaissé cette borne à 246, en s'appuyant notamment sur une méthode de James Maynard. Il reste à passer de 246 à 2.
Le plus grand nombre premier connu
Au 25 octobre 2026, le record reste celui de Luke Durant : 2 puissance 136 279 841, moins 1, trouvé dans le cadre du projet collaboratif GIMPS et annoncé le 21 octobre 2024. Le précédent, 2 puissance 82 589 933, moins 1, datait de décembre 2018. Imprimé à 3 000 caractères par page, le nouveau remplirait environ 13 700 pages.
C'est un nombre de Mersenne, de la forme 2 puissance p, moins 1 : pour ces nombres, le test de Lucas-Lehmer vérifie la primalité bien plus vite que pour un nombre quelconque. Les puissances vues en 4e mènent directement à ces géants.
RSA : chiffrer avec des nombres premiers
Un cadenas que tout le monde peut fermer
En 1977, au MIT, Ronald Rivest, Adi Shamir et Leonard Adleman ont décrit une méthode de chiffrement « à clé publique », publiée l'année suivante. Le principe ressemble à un cadenas ouvert distribué à tout le monde : n'importe qui peut le fermer sur un message, mais seul son propriétaire a la clé. Fait remarquable, Clifford Cocks, mathématicien du service de renseignement britannique GCHQ, avait trouvé un système équivalent peu après son arrivée en 1973 ; sa découverte est restée secrète pendant 24 ans.
Un exemple complet avec 11 et 17
Avec de petits nombres, on peut tout vérifier à la main. On note « mod 187 » le reste de la division par 187.
- Choisir deux nombres premiers secrets : p = 11 et q = 17.
- Calculer n = p × q = 187. Ce nombre est public.
- Calculer φ = (p − 1) × (q − 1) = 10 × 16 = 160. Ce nombre reste secret.
- Choisir l'exposant public e = 7, qui n'a aucun facteur commun avec 160. La clé publique est le couple (187, 7).
- Trouver l'exposant secret d tel que e × d laisse un reste de 1 dans la division par 160 : 7 × 23 = 161 = 160 + 1, donc d = 23.
- Chiffrer le message m = 42 : c = 42⁷ mod 187. En réduisant à chaque étape, les puissances successives de 42 modulo 187 sont 42, 81, 36, 16, 111, 174 et enfin 15 (et 42⁷ = 230 539 333 248 laisse bien un reste de 15). Le message chiffré est c = 15.
- Déchiffrer : on calcule 15²³ mod 187. Comme 23 = 16 + 4 + 2 + 1, on élève 15 au carré à répétition : 15² ≡ 38, 15⁴ ≡ 135, 15⁸ ≡ 86, 15¹⁶ ≡ 103 (modulo 187). Puis 15 × 38 ≡ 9, 9 × 135 ≡ 93, 93 × 103 ≡ 42. On retrouve m = 42.
Pourquoi ça marche ? Un théorème d'Euler, généralisation du petit théorème de Fermat, assure que si m n'a pas de facteur commun avec n, alors m puissance φ laisse un reste de 1 dans la division par n. Comme e × d = 1 + 160, élever à la puissance e puis à la puissance d revient à multiplier m par m puissance 160, c'est-à-dire par 1 modulo 187.
Pourquoi factoriser est si difficile
Toute la sécurité repose sur une asymétrie. Un espion qui connaît n = 187 et e = 7 n'a qu'à factoriser n : 187 = 11 × 17 se trouve en quelques essais, d'où φ = 160 et d = 23. Mais avec une clé réelle, n compte des centaines de chiffres.
Multiplier deux nombres de 309 chiffres prend quelques millionièmes de seconde à un ordinateur. Défaire la multiplication est une autre histoire. Essayer tous les diviseurs premiers jusqu'à la racine carrée d'un n de 617 chiffres demanderait de tester environ 10 puissance 305 nombres premiers ; à un milliard de milliards d'essais par seconde, il faudrait environ 10 puissance 280 années, quand l'Univers a moins de 14 milliards d'années.
Les mathématiciens ont trouvé bien mieux que ces essais, ce qui oblige à allonger les clés. Dans leur article, Rivest, Shamir et Adleman estimaient qu'avec la meilleure méthode connue, à un calcul par microseconde, factoriser un nombre de 200 chiffres prendrait 3,8 milliards d'années. Le 28 février 2020, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé et Paul Zimmermann ont factorisé RSA-250, un nombre de 250 chiffres, grâce à l'algorithme du crible algébrique (number field sieve) et au logiciel libre CADO-NFS : environ 2 700 années de calcul d'un cœur de processeur. C'est pourquoi l'Agence nationale de la sécurité des systèmes d'information (ANSSI) recommande des clés RSA d'au moins 3 072 bits, soit environ 925 chiffres, et juge les clés de 2 048 bits obsolescentes.
Deux nuances importantes. D'abord, personne n'a démontré que la factorisation est difficile : on ne connaît simplement aucune méthode rapide sur un ordinateur classique. Ensuite, un ordinateur quantique suffisamment puissant pourrait factoriser rapidement grâce à l'algorithme de Shor. Par précaution, l'ANSSI recommande déjà d'adapter les choix cryptographiques pour les données qui doivent rester protégées au-delà de 2030.
Ce qu'il faut retenir
Les nombres premiers ne s'arrêtent jamais : à partir de n'importe quelle liste finie, la preuve d'Euclide en fabrique un nouveau. Ils se raréfient lentement selon une loi précise, laissent des trous aussi grands qu'on veut et gardent leurs mystères, comme celui des jumeaux. Et la facilité de multiplier, face à la difficulté de factoriser, suffit à bâtir un chiffrement que tu peux refaire à la main avec 11 et 17.
Dans Mathflow, l'arithmétique se travaille en trois niveaux : au niveau Manipuler, tu fais pousser des arbres de facteurs ; au niveau Expliquer, tu repères l'erreur dans la copie d'un autre élève ; au niveau Raisonner, tu résous seul des problèmes. Alphi, le coach IA, donne un indice quand tu bloques. L'appli, conçue avec Inria et notée 4,8 sur l'App Store, est gratuite pour commencer.
Sources
- David E. Joyce (Clark University), Euclid's Elements, Book IX, Proposition 20, 1998
- John J. O'Connor et Edmund F. Robertson (MacTutor, université de St Andrews), Prime numbers, 2018
- GIMPS, GIMPS Discovers Largest Known Prime Number: 2^136,279,841-1, 2024
- D. H. J. Polymath, The "bounded gaps between primes" Polymath project: a retrospective, 2014
- Ronald Rivest, Adi Shamir et Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, 1978
- Université de Bristol, Dr Clifford Cocks CB, 2008
- Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé et Paul Zimmermann, Factorization of RSA-250, 2020
- ANSSI, Guide de sélection d'algorithmes cryptographiques, 2021
