Chapitre 7
Objectif du chapitre
Explorer la fascination millénaire pour une famille particulière de nombres premiers : les nombres de Mersenne, et comprendre comment ils sont devenus le terrain privilégié des records de primalité grâce aux tests de Lucas-Lehmer et à la puissance des ordinateurs modernes.
1. Marin Mersenne (1588–1648)
Moine savant et ami de Descartes, Marin Mersenne était passionné par les lois de la nature et des nombres.
Dans ses correspondances, il mentionne une classe spéciale de nombres définis par la formule :
\[
M_n = 2^n – 1
\]
Ces nombres, appelés nombres de Mersenne, sont étroitement liés aux nombres premiers, mais tous ne le sont pas.
2. Quand un nombre de Mersenne est-il premier ?
Un nombre de Mersenne \( M_n = 2^n – 1 \) ne peut être premier que si l’exposant ( n ) lui-même est premier.
Cette condition est nécessaire, mais pas suffisante.
💡 Exemples :
- \( n = 2 ) → \(M_2 = 3 \) → premier ✅
- \( n = 3 ) → \(M_3 = 7 \) → premier ✅
- \( n = 4 \) → \(M_4 = 15 = 3 \times 5 \) → composé ❌
- \( n = 5 \) → \( M_5 = 31 \) → premier ✅
- ( n = 11 \) → \( M_{11} = 2047 = 23 \times 89 \) → composé ❌
Ainsi, seuls certains exposants premiers donnent naissance à un nombre premier de Mersenne.
3. La beauté mathématique des nombres de Mersenne
Les nombres de Mersenne sont fascinants car ils se situent à la frontière entre la simplicité de la formule et la complexité de la primalité.
Ils apparaissent aussi dans de nombreux domaines :
- Nombres parfaits : chaque nombre premier de Mersenne est lié à un nombre parfait \( P = 2^{n-1}(2^n – 1) \).
Exemple :
\[
M_3 = 7 \quad \Rightarrow \quad P = 2^2 \times 7 = 28
\] - Cryptographie : leur structure binaire (suite de 1 en base 2) les rend utiles dans certains générateurs pseudo-aléatoires.
- Recherche expérimentale : leur forme compacte permet de tester rapidement de très grands entiers.
4. Le test de Lucas-Lehmer
Le test de Lucas-Lehmer est le moyen le plus efficace pour vérifier si un nombre de Mersenne \( M_n = 2^n – 1 \) est premier.
🔹 Principe :
On définit une suite :
\[
S_1 = 4, \quad S_{k+1} = S_k^2 – 2
\]
Le test dit que \( M_n \) est premier si et seulement si :
\[
S_{n-1} \equiv 0 \pmod{M_n}
\]
💡 Exemple :
Pour ( n = 5 ) (donc \( M_5 = 31 \)) :
\[
\begin{aligned}
S_1 &= 4 \
S_2 &= 4^2 – 2 = 14 \
S_3 &= 14^2 – 2 = 194 \
S_4 &= 194^2 – 2 = 37634
\end{aligned}
\]
On réduit \( S_4 \) modulo 31 :
\[
37634 \bmod 31 = 0
\]
✅ Donc \( M_5 = 31 \) est bien premier !
5. L’ère du calcul distribué — le projet GIMPS
Depuis 1996, le projet GIMPS (Great Internet Mersenne Prime Search) mobilise des milliers d’ordinateurs dans le monde entier pour tester la primalité des nombres de Mersenne.
Chaque participant installe un petit logiciel qui exécute le test de Lucas-Lehmer sur un exposant donné.
🔹 Quelques records récents :
| Année | Exposant ( n ) | Taille du nombre ( M_n ) | Nombre de chiffres |
|---|---|---|---|
| 1996 | 1 398 269 | \( 2^{1 398 269} – 1 \) | 420 921 |
| 2008 | 43 112 609 | \( 2^{43 112 609} – \) | 12 978 189 |
| 2018 | 82 589 933 | \( 2^{82 589 933} – 1 \) | 24 862 048 |
| 2024 | ≈ 86 000 000 | \( 2^{86 000 000} – 1 \) | ≈ 26 000 000 |
“Les plus grands nombres premiers connus sont toujours des nombres de Mersenne.”
6. Les tests modernes de primalité
Bien que le test de Lucas-Lehmer soit réservé aux nombres de Mersenne, d’autres méthodes générales ont émergé pour vérifier la primalité de tout entier.
🔹 Tests probabilistes :
- Miller-Rabin : rapide, utilisé en cryptographie.
- Baillie-PSW : très fiable, combine plusieurs méthodes.
🔹 Tests déterministes :
- AKS (Agrawal–Kayal–Saxena, 2002) : premier algorithme polynomial prouvant la primalité de manière absolue.
\[
\text{Un nombre } n \text{ est premier si } (x-1)^n \equiv x^n – 1 \pmod{n}
\]
Même si le test AKS est révolutionnaire théoriquement, il reste trop lent pour des applications pratiques.
Les chercheurs continuent donc d’utiliser des tests hybrides ou adaptés aux formes spéciales comme les Mersenne.
7. Applications contemporaines
Les nombres de Mersenne trouvent aujourd’hui des usages variés :
- en génération pseudo-aléatoire (algorithme Mersenne Twister, utilisé dans Python et C++),
- en cryptographie avancée,
- en études statistiques sur la répartition des nombres premiers,
- et même dans les recherches de physique mathématique (modèles de symétrie et de chaos quantique).
💬 Ils sont devenus un symbole : celui de la rencontre entre la pureté mathématique et la puissance du calcul moderne.
🔗 Pages liées
- Mersenne — Le moine des nombres.
- Lucas-Lehmer — Le test parfait pour les puissances de 2.
- GIMPS — Le projet mondial des nombres premiers.
- AKS — La primalité prouvée sans hasard.
🧭 Transition vers le Chapitre 8
Les nombres premiers quittent désormais le domaine de la théorie pure pour entrer dans le monde concret : la cryptographie, les communications sécurisées et l’informatique quantique.
➜ Chapitre 8 : Cryptographie et applications modernes