On considère un entier p>2, et le nombre de Mersenne
M=2p-1; on voudrait savoir si ce nombre est premier.
Si on essaye la divisibilité par les nombres impairs allant
jusqu'à √M∼2p/2, pour de grandes valeurs
de p, on prend un temps tellement long qu'il devient impossible
de prouver la primalité de M en un temps raisonnable (environ
2p/4 divisions à mener). L'algorithme de Lucas-Lehmer
(mis au point par Édouard Lucas à la fin du XIXe siècle, et amélioré
par Derrick Lehmer dans les années 1930) consiste à faire les calculs
suivants:
On prend un nombre entier, dont la valeur de départ est 4;
On répète p-1 fois les opérations suivantes:
élever le nombre au carré;
soustraire 2 au résultat (soit enlever le pion en position 2 de l'échiquier)
Si à un moment, l'échiquier est vide (le nombre s'est annulé), on arrête.
Si, au bout de p-1 itérations de ce programme de calcul, on n'arrive toujours
pas à 0 (il reste des pions sur l'échiquier) alors 2p-1 est
composé: Il possède un diviseur que l'algorithme de Lucas-Lehmer
ne fournit pas, mais on sait que M n'est pas un nombre premier.
Sinon, on a réussi avec p-1 calculs seulement, à prouver que M
est premier.
Cet algorithme devient intéressant dès que 2p/4 dépasse
p-1, soit p=17. De plus, il s'implémente bien en binaire et est
donc très utilisé pour tester la primalité de grands nombres de Mersenne.
Résultats obtenus
Pour p petit
Pour p=3, on voit avec l'algorithme que 7 est premier
Pour p=11, la suite de Lucas-Lehmer donne (modulo 211-1=2047), respectivement,
14,
194,
788,
701,
119,
1877,
240,
282,
1736,
510 et on voit qu'au bout de 11-1=10 itérations, l'échiquier n'est toujours pas vide (il
porte encore le nombre 111111110 soit 8 pions): 2047 n'est
pas premier. Cela, Mersenne le savait déjà au début du
XVIIe siècle, en effet 2047 est divisible par 23.
Pour p=13 par contre, la suite est 14,
194,
4870,
3953,
5970,
1857,
36,
1294,
3470,
128,
0 qui s'annule juste à temps: Il suffit de 12 calculs menés
sur un échiquier 13×13 pour prouver la primalité de 8191.
De même, on vérifie la primalité de 131071=217-1
en obtenant sur un échiquier 17×17 les nombres binaires suivants
(à partir de 100 soit 4 en binaire):
Lucas montre rapidement à la fin du XIXe siècle ce résultat connu
depuis 1588 (Cataldi)
Pour p=19, on vérifie là aussi la primalité de 524287 (connue
depuis 1588 aussi) par la suite 1110,
11000010,
1001001100000010,
110101011010001111,
1111100100001110010,
1011110010100101000,
1001110111001010100,
110101010110011110,
1111011000101001100,
11001010000101101,
1100101111110101010,
1001011000011011001,
1011101100000001101,
1000011010110000010,
10100110011101010,
1111111101111111111,
0 sur un échiquier 19×19.
Pour p=23, les nombres obtenus sont, en binaire, 1110,
11000010,
1001001100000010,
11010110100110010101010,
11010110101001100111100,
100011111001101101101,
11101001010000011011110,
1100001000010011011111,
1010010001111001110000,
10111010011010000101,
1111111101000010001110,
11010101101111101100001,
101110101111000111110,
10110011101101100100101,
100010110011110001110,
10000011111000010010111,
11010110111000100101100,
1010100000111100101000,
100111000100000110010,
11001000010010011000001,
10111010011001011110111,
10111110100011001110010 : Le dernier n'étant pas nul,
223-1 = 8388607 n'est pas premier
(il est divisible par 47)
Pour p=29, la suite des nombres obtenus est 1110,
11000010,
1001001100000010,
10100011010110100110000000100,
1110111100011110011011011000,
11001110100111010010011011110,
111110010101100111100011,
11011001011010011011001000110,
11011001100100010011010010101,
11101001000011000001001110010,
10010011000001101101001000100,
111101001011111110010111110,
1100010001101001100010010011,
11000000010000111001010010010,
1110011100110000100101010100,
11000010101010100100101000010,
1101010010111000011000101111,
10001011001010100101111100011,
111000100011010110010010111,
11111110010000011001010011,
111000100001000000001,
1001111001001110011110011,
11000001011010100101101000101,
1110101001111011000110100010,
11011010100111001010010110101,
1001000101011010110100111110,
11111111111010001101100100011,
10001001110101001000 et cela prouve là encore, que
536870911 est composé (il est divisible par 233)
Pour p=31, 2 147 483 647 qui était le plus grand
nombre premier connu à la fin du XIXe siècle (résultat
établi par Fermat et vérifié par Euler), Lucas redémontre
sa primalité à l'aide d'un échiquier de 31×31 cases, avec cette
suite de nombres sur l'échiquier :
On passe typiquement de un an à une heure, avec l'algorithme
de Lucas sur échiquier. Du moins, avant de bénéficier d'un
ordinateur.
Records établis avec l'algorithme de Lucas-Lehmer
En 1876, le plus grand nombre premier connu
était 231-1=2 147 483 647. Mais avec un échiquier
127×127, Lucas a prouvé avec son algorithme (126 itérations)
que 2127-1 est premier: Record du monde battu, ce
nombre étant égal à
Par la suite, Lucas et Genaille ont essayé de redémontrer la primalité
de ce nombre avec un arithmomètre de Thomas de Colmar. Après la seconde guerre mondiale,
les premiers programmes d'ordinateur ont souvent été des implémentations
de l'algorithme de Lucas-Lehmer et la primalité de 2127-1
a été vérifiée par l'équipe de Lehmer en 1952, sur un ordinateur SWAC.
Le même jour, le même programme a prouvé la primalité de 2521-1,
dont l'écriture décimale comprend 157 chiffres.
Toujours en 1952, cette équipe a prouvé successivment la
primalité de 2607-1, puis de 21279-1,
puis de 22203-1 et enfin de 22281-1
Les records se sont ensuite succédés, toujours avec l'algorithme
de Lucas-Lehmer, sur des machines de plus en plus puissantes.
Par exemple en 1979, c'est sur un Cray qu'a été vérifiée la
primalité de 244497-1, puis de 286243-1.
Dans les années 1990, démarre le projet GIMPS
("Great Internet Mersenne Prime Search"), qui consiste
essentiellement à utiliser Internet pour faire du calcul en
réseau: On met en route l'algorithme de Lucas-Lehmer pour
tester un nombre de Mersenne attribué au hasard. Au passage
des erreurs de conception de CPU (marque Intel) ont été
découvertes grâce à ce genre de test.
En 2016, le plus grand nombre premier connu était
274207281-1 (dont l'écriture décimale occupe
plus de 22 millions de chiffres). Le détenteur du record est
Curtis Cooper (déjà détenteur du record précédent avec
257885161-1 ainsi que d'autres records précédents).
Il a fait tourner le programme du GIMPS sur un PC (CPU Intel I7-4970)
pendant 31 jours (le programme a donc démarré en 2015 pour finir en 2016).
La vérification a duré 2 jours et demie sur un GPU NVidia et
3 jours et demie sur un GPU AMD. En 2017, sur les 10 nombres
premiers les plus grands connus, 9 sont des nombres de Mersenne.