Problème de factorisation

La décomposition en facteurs premiers de grands entiers (nombres composés de plusieurs dizaines de chiffres) est encore aujourd'hui très difficile à réaliser. Malgré la puissance des ordinateurs qui n'a cessé d'augmenter depuis plus d'un demi-siècle, il n'est toujours pas possible de factoriser certains nombres qui possèdent plusieurs centaines de chiffres, dont les facteurs premiers sont peu nombreux et dont le plus petit d'entre eux possède, lui aussi, un très grand nombre de chiffres. C'est d'ailleurs la base de la cryptographie moderne.

Si l’on choisit deux nombres premiers suffisamment grands (composés de plusieurs centaines de chiffres chacun), il est très facile de les multiplier entre eux avec nos ordinateurs actuels, cela ne prendra qu'un certain temps (moins d'une seconde). Par contre, une fois le résultat obtenu, il est quasiment impossible d’effectuer sa décomposition en facteurs premiers, cela pourrait prendre un temps certain (jusqu'à plusieurs années).

Pour vous donner un ordre d'idée de la difficulté à décomposer en facteurs premiers, essayez de trouver, sans table de nombres premiers, les facteurs premiers du nombre 30 031 ou encore de 4 294 967 297, le sixième nombre de Fermat.

Fermat avait conjecturé au XVII^e siècle (vers 1640) que les nombres de la forme $2^{2^n}+1$ étaient premiers. Cette conjecture se révéla fausse. Les 5 premiers nombres de Fermat sont effectivement premiers :

F₀ = 3 ; F₁ = 5 ; F₂ = 17 ; F₃ = 257 ; F₄ = 65537.

Mais le sixième, 4 294 967 297, ne l’est pas. C’est le mathématicien Euler qui, en 1732, près d’un siècle plus tard, montra que le sixième nombre de Fermat pouvait se factoriser en un produit de 2 facteurs : 4 294 967 297 = 641 × 6 700 417.

En 1867, Landry trouve que le nombre de Mersenne M₅₉ est divisible par 179 951 ; il lui faut 143 divisions pour y parvenir. Pour démontrer que le second facteur 3 203 431 780 337 est premier, il lui faut encore plus de 1000 divisions. Ce nombre est resté le plus grand nombre premier connu pendant 9 ans.

Le 7^e nombre de Fermat F₆ = 274177 × 67280421310721 fut, quant à lui, factorisé en 1855 par Clausen.

Par la suite, les progrès dans la recherche de décompositions de grands nombres en produit de facteurs premiers ont été lents. Par exemple, au début du XX^e siècle, Frank Nelson Cole a donné la factorisation du nombre de Mersenne M₆₇ = 2⁶⁷ − 1 = 147 573 952 589 676 412 927 en 1903. De son propre aveu, le calcul lui avait pris tous ses dimanches durant 3 ans.

M₆₇ = 193 707 721 × 761 838 257 287.

Le 8^e nombre de Fermat F₇ = 2¹²⁸ + 1 (composé de 39 chiffres) n’a, quant à lui, été factorisé que dans les années 1970 avec l’avènement de nouveaux algorithmes et la montée en puissance des ordinateurs.

Il aura fallu plus de 250 000 secondes (près de 70 heures) à mon meilleur programme pour le décomposer, sur un Mac à 2 GHz, un ordinateur courant à l'époque où ces calculs ont été faits :

2¹²⁸ + 1 = 340282366920938463463374607431768211457(39) =
59649589127497217(17) × 5704689200685129054721(22) (temps de calcul : 251151,280743 s)

Aujourd'hui, les meilleurs algorithmes factorisent un tel nombre de 39 chiffres en quelques secondes. Pour les nombres les plus difficiles (produits de deux grands nombres premiers), le record est RSA-250, un nombre de 250 chiffres factorisé en 2020 avec des milliers d'ordinateurs.

Factorisation des nombres de Mersenne

Voilà ce que l'on peut obtenir avec un ordinateur de particulier et quelques heures de programmation. Plusieurs algorithmes sont à disposition sur le net, mais les plus simples ne mènent pas bien loin : on se trouve rapidement bloqué, ne serait-ce que par les nombres de Mersenne qui sont premiers. Il faut donc implanter un test de primalité ; j'ai choisi celui de Miller-Rabin, qui permet de ne pas avoir à tester, par l'algorithme de factorisation, les facteurs qui sont premiers.

Même avec ce test, les calculs sont assez lents. M₅₉ est un bon candidat pour tester des algorithmes. En effet, sa factorisation est facilement accessible, mais tout de même significative, du fait qu'il possède seulement 2 facteurs premiers.

Nous appellerons « force brute » l'algorithme des divisions successives jusqu'à la racine carrée du nombre testé.

Dans les résultats ci-dessous, le nombre entre parenthèses indique le nombre de chiffres.

Factorisation de M₅₉ en force brute avec le test de Miller-Rabin

M₅₉ = 2⁵⁹ − 1 = 576460752303423487(18) =
179951(6) × 3203431780337(13) (temps de calcul : 3,014073 s)

Factorisation de M₅₉ en force brute avec le test de Miller-Rabin, en remarquant que les facteurs des nombres de Mersenne sont de la forme 1 + 2kp

M₅₉ = 2⁵⁹ − 1 = 576460752303423487(18) =
179951(6) × 3203431780337(13) (temps de calcul : 0,192607 s)

Avec cette méthode, la factorisation de M₆₇ devient accessible :

M₆₇ = 2⁶⁷ − 1 = 147573952589676412927(21) =
193707721(9) × 761838257287(12) (temps de calcul : 55,185544 s)

Malgré l'optimisation des facteurs, il est évident que cette méthode va très vite trouver ses limites : en effet, le temps de factorisation est environ 290 fois plus long pour un petit facteur qui possède seulement 3 chiffres de plus. De plus, cette optimisation n'est valable que pour les nombres de Mersenne, c'est-à-dire pour p premier, et pas pour les autres valeurs de p.

Factorisation de M₆₇ avec l'algorithme rho de Pollard, sans autre optimisation

M₆₇ = 2⁶⁷ − 1 = 147573952589676412927(21) =
193707721(9) × 761838257287(12) (temps de calcul : 6,954788 s)

Factorisation de M₆₇ avec l'algorithme rho de Pollard et un algorithme de division rapide

M₆₇ = 2⁶⁷ − 1 = 147573952589676412927(21) =
193707721(9) × 761838257287(12) (temps de calcul : 1,870080 s)

Factorisation des nombres de Mersenne à l'aide de l'algorithme rho de Pollard (variante de Brent), de la division rapide et du test de Miller-Rabin

Cette fois, l'algorithme rho de Pollard (variante de Brent), aidé de la division rapide pour les calculs modulo n, nous permet d'accéder à la factorisation des nombres 2^p − 1 jusqu'à 2¹⁶⁹ − 1, à l'exception de 2¹²² − 1, 2¹³⁷ − 1 et 2¹⁴⁹ − 1. Ces trois nombres ont au plus trois facteurs premiers, et leurs grands facteurs ont au moins 18 chiffres, ce qui est hors de portée de mon programme :

2¹²² − 1 = 3 × 768 614 336 404 564 651 × 2 305 843 009 213 693 951 (trois facteurs premiers) ;
2¹³⁷ − 1 = 32 032 215 596 496 435 569 × 5 439 042 183 600 204 290 159 (deux facteurs premiers) ;
2¹⁴⁹ − 1 = 86 656 268 566 282 183 151 × 8 235 109 336 690 846 723 986 161 (deux facteurs premiers).

M₂ = 2² − 1 = 3(1) =
3(1) : nombre premier (temps de calcul : 0,003421 s)

M₃ = 2³ − 1 = 7(1) =
7(1) : nombre premier (temps de calcul : 0,003405 s)

M₄ = 2⁴ − 1 = 15(2) =
3(1) × 5(1) (temps de calcul : 0,003376 s)

M₅ = 2⁵ − 1 = 31(2) =
31(2) : nombre premier (temps de calcul : 0,003448 s)

M₆ = 2⁶ − 1 = 63(2) =
3(1) × 3(1) × 7(1) (temps de calcul : 0,003367 s)

M₇ = 2⁷ − 1 = 127(3) =
127(3) : nombre premier (temps de calcul : 0,003398 s)

M₈ = 2⁸ − 1 = 255(3) =
3(1) × 5(1) × 17(2) (temps de calcul : 0,003388 s)

M₉ = 2⁹ − 1 = 511(3) =
7(1) × 73(2) (temps de calcul : 0,003426 s)

M₁₀ = 2¹⁰ − 1 = 1023(4) =
3(1) × 11(2) × 31(2) (temps de calcul : 0,003433 s)

M₁₁ = 2¹¹ − 1 = 2047(4) =
23(2) × 89(2) (temps de calcul : 0,003474 s)

M₁₂ = 2¹² − 1 = 4095(4) =
3(1) × 3(1) × 5(1) × 7(1) × 13(2) (temps de calcul : 0,003518 s)

M₁₃ = 2¹³ − 1 = 8191(4) =
8191(4) : nombre premier (temps de calcul : 0,005621 s)

M₁₄ = 2¹⁴ − 1 = 16383(5) =
3(1) × 43(2) × 127(3) (temps de calcul : 0,003677 s)

M₁₅ = 2¹⁵ − 1 = 32767(5) =
7(1) × 31(2) × 151(3) (temps de calcul : 0,003614 s)

M₁₆ = 2¹⁶ − 1 = 65535(5) =
3(1) × 5(1) × 17(2) × 257(3) (temps de calcul : 0,003527 s)

M₁₇ = 2¹⁷ − 1 = 131071(6) =
131071(6) : nombre premier (temps de calcul : 0,019437 s)

M₁₈ = 2¹⁸ − 1 = 262143(6) =
3(1) × 3(1) × 3(1) × 7(1) × 19(2) × 73(2) (temps de calcul : 0,003686 s)

M₁₉ = 2¹⁹ − 1 = 524287(6) =
524287(6) : nombre premier (temps de calcul : 0,022863 s)

M₂₀ = 2²⁰ − 1 = 1048575(7) =
3(1) × 5(1) × 5(1) × 11(2) × 31(2) × 41(2) (temps de calcul : 0,003754 s)

M₂₁ = 2²¹ − 1 = 2097151(7) =
7(1) × 7(1) × 127(3) × 337(3) (temps de calcul : 0,003950 s)

M₂₂ = 2²² − 1 = 4194303(7) =
3(1) × 23(2) × 89(2) × 683(3) (temps de calcul : 0,003960 s)

M₂₃ = 2²³ − 1 = 8388607(7) =
47(2) × 178481(6) (temps de calcul : 0,012252 s)

M₂₄ = 2²⁴ − 1 = 16777215(8) =
3(1) × 3(1) × 5(1) × 7(1) × 13(2) × 17(2) × 241(3) (temps de calcul : 0,003912 s)

M₂₅ = 2²⁵ − 1 = 33554431(8) =
31(2) × 601(3) × 1801(4) (temps de calcul : 0,004751 s)

M₂₆ = 2²⁶ − 1 = 67108863(8) =
3(1) × 2731(4) × 8191(4) (temps de calcul : 0,009366 s)

M₂₇ = 2²⁷ − 1 = 134217727(9) =
7(1) × 73(2) × 262657(6) (temps de calcul : 0,011082 s)

M₂₈ = 2²⁸ − 1 = 268435455(9) =
3(1) × 5(1) × 29(2) × 43(2) × 113(3) × 127(3) (temps de calcul : 0,004298 s)

M₂₉ = 2²⁹ − 1 = 536870911(9) =
233(3) × 1103(4) × 2089(4) (temps de calcul : 0,006115 s)

M₃₀ = 2³⁰ − 1 = 1073741823(10) =
3(1) × 3(1) × 7(1) × 11(2) × 31(2) × 151(3) × 331(3) (temps de calcul : 0,004395 s)

M₃₁ = 2³¹ − 1 = 2147483647(10) =
2147483647(10) : nombre premier (temps de calcul : 0,067856 s)

M₃₂ = 2³² − 1 = 4294967295(10) =
3(1) × 5(1) × 17(2) × 257(3) × 65537(5) (temps de calcul : 0,006768 s)

M₃₃ = 2³³ − 1 = 8589934591(10) =
7(1) × 23(2) × 89(2) × 599479(6) (temps de calcul : 0,007629 s)

M₃₄ = 2³⁴ − 1 = 17179869183(11) =
3(1) × 43691(5) × 131071(6) (temps de calcul : 0,040584 s)

M₃₅ = 2³⁵ − 1 = 34359738367(11) =
31(2) × 71(2) × 127(3) × 122921(6) (temps de calcul : 0,011421 s)

M₃₆ = 2³⁶ − 1 = 68719476735(11) =
3(1) × 3(1) × 3(1) × 5(1) × 7(1) × 13(2) × 19(2) × 37(2) × 73(2) × 109(3) (temps de calcul : 0,010154 s)

M₃₇ = 2³⁷ − 1 = 137438953471(12) =
223(3) × 616318177(9) (temps de calcul : 0,032471 s)

M₃₈ = 2³⁸ − 1 = 274877906943(12) =
3(1) × 524287(6) × 174763(6) (temps de calcul : 0,052345 s)

M₃₉ = 2³⁹ − 1 = 549755813887(12) =
7(1) × 79(2) × 8191(4) × 121369(6) (temps de calcul : 0,021484 s)

M₄₀ = 2⁴⁰ − 1 = 1099511627775(13) =
3(1) × 5(1) × 5(1) × 11(2) × 17(2) × 31(2) × 41(2) × 61681(5) (temps de calcul : 0,011037 s)

M₄₁ = 2⁴¹ − 1 = 2199023255551(13) =
13367(5) × 164511353(9) (temps de calcul : 0,040871 s)

M₄₂ = 2⁴² − 1 = 4398046511103(13) =
3(1) × 3(1) × 7(1) × 7(1) × 43(2) × 127(3) × 337(3) × 5419(4) (temps de calcul : 0,006254 s)

M₄₃ = 2⁴³ − 1 = 8796093022207(13) =
431(3) × 9719(4) × 2099863(7) (temps de calcul : 0,031486 s)

M₄₄ = 2⁴⁴ − 1 = 17592186044415(14) =
3(1) × 5(1) × 23(2) × 89(2) × 397(3) × 683(3) × 2113(4) (temps de calcul : 0,006772 s)

M₄₅ = 2⁴⁵ − 1 = 35184372088831(14) =
7(1) × 31(2) × 73(2) × 151(3) × 631(3) × 23311(5) (temps de calcul : 0,010162 s)

M₄₆ = 2⁴⁶ − 1 = 70368744177663(14) =
3(1) × 47(2) × 178481(6) × 2796203(7) (temps de calcul : 0,060587 s)

M₄₇ = 2⁴⁷ − 1 = 140737488355327(15) =
2351(4) × 4513(4) × 13264529(8) (temps de calcul : 0,043228 s)

M₄₈ = 2⁴⁸ − 1 = 281474976710655(15) =
3(1) × 3(1) × 5(1) × 7(1) × 13(2) × 17(2) × 97(2) × 241(3) × 257(3) × 673(3) (temps de calcul : 0,014543 s)

M₄₉ = 2⁴⁹ − 1 = 562949953421311(15) =
127(3) × 4432676798593(13) (temps de calcul : 0,049894 s)

M₅₀ = 2⁵⁰ − 1 = 1125899906842623(16) =
3(1) × 11(2) × 31(2) × 251(3) × 601(3) × 1801(4) × 4051(4) (temps de calcul : 0,018363 s)

M₅₁ = 2⁵¹ − 1 = 2251799813685247(16) =
7(1) × 103(3) × 2143(4) × 11119(5) × 131071(6) (temps de calcul : 0,044818 s)

M₅₂ = 2⁵² − 1 = 4503599627370495(16) =
3(1) × 5(1) × 53(2) × 157(3) × 1613(4) × 2731(4) × 8191(4) (temps de calcul : 0,013494 s)

M₅₃ = 2⁵³ − 1 = 9007199254740991(16) =
6361(4) × 69431(5) × 20394401(8) (temps de calcul : 0,075092 s)

M₅₄ = 2⁵⁴ − 1 = 18014398509481983(17) =
3(1) × 3(1) × 3(1) × 3(1) × 7(1) × 19(2) × 73(2) × 87211(5) × 262657(6) (temps de calcul : 0,046612 s)

M₅₅ = 2⁵⁵ − 1 = 36028797018963967(17) =
23(2) × 31(2) × 89(2) × 881(3) × 3191(4) × 201961(6) (temps de calcul : 0,021523 s)

M₅₆ = 2⁵⁶ − 1 = 72057594037927935(17) =
3(1) × 5(1) × 17(2) × 29(2) × 43(2) × 113(3) × 127(3) × 15790321(8) (temps de calcul : 0,027449 s)

M₅₇ = 2⁵⁷ − 1 = 144115188075855871(18) =
7(1) × 32377(5) × 524287(6) × 1212847(7) (temps de calcul : 0,103639 s)

M₅₈ = 2⁵⁸ − 1 = 288230376151711743(18) =
3(1) × 59(2) × 233(3) × 1103(4) × 2089(4) × 3033169(7) (temps de calcul : 0,024562 s)

M₅₉ = 2⁵⁹ − 1 = 576460752303423487(18) =
179951(6) × 3203431780337(13) (temps de calcul : 0,143974 s)

M₆₀ = 2⁶⁰ − 1 = 1152921504606846975(19) =
3(1) × 3(1) × 5(1) × 5(1) × 7(1) × 11(2) × 13(2) × 31(2) × 41(2) × 61(2) × 151(3) × 331(3) × 1321(4) (temps de calcul : 0,008499 s)

M₆₁ = 2⁶¹ − 1 = 2305843009213693951(19) =
2305843009213693951(19) : nombre premier (temps de calcul : 0,356570 s)

M₆₂ = 2⁶² − 1 = 4611686018427387903(19) =
3(1) × 715827883(9) × 2147483647(10) (temps de calcul : 3,634923 s)

M₆₃ = 2⁶³ − 1 = 9223372036854775807(19) =
7(1) × 7(1) × 73(2) × 127(3) × 337(3) × 92737(5) × 649657(6) (temps de calcul : 0,046332 s)

M₆₄ = 2⁶⁴ − 1 = 18446744073709551615(20) =
3(1) × 5(1) × 17(2) × 257(3) × 641(3) × 65537(5) × 6700417(7) (temps de calcul : 0,071602 s)

M₆₅ = 2⁶⁵ − 1 = 36893488147419103231(20) =
31(2) × 8191(4) × 145295143558111(15) (temps de calcul : 0,114911 s)

M₆₆ = 2⁶⁶ − 1 = 73786976294838206463(20) =
3(1) × 3(1) × 7(1) × 23(2) × 67(2) × 89(2) × 683(3) × 20857(5) × 599479(6) (temps de calcul : 0,042356 s)

M₆₇ = 2⁶⁷ − 1 = 147573952589676412927(21) =
193707721(9) × 761838257287(12) (temps de calcul : 5,206143 s)

M₆₈ = 2⁶⁸ − 1 = 295147905179352825855(21) =
3(1) × 5(1) × 137(3) × 953(3) × 131071(6) × 43691(5) × 26317(5) (temps de calcul : 0,077998 s)

M₆₉ = 2⁶⁹ − 1 = 590295810358705651711(21) =
7(1) × 47(2) × 178481(6) × 10052678938039(14) (temps de calcul : 0,126579 s)

M₇₀ = 2⁷⁰ − 1 = 1180591620717411303423(22) =
3(1) × 11(2) × 31(2) × 43(2) × 71(2) × 127(3) × 281(3) × 86171(5) × 122921(6) (temps de calcul : 0,048207 s)

M₇₁ = 2⁷¹ − 1 = 2361183241434822606847(22) =
228479(6) × 48544121(8) × 212885833(9) (temps de calcul : 0,441938 s)

M₇₂ = 2⁷² − 1 = 4722366482869645213695(22) =
3(1) × 3(1) × 3(1) × 5(1) × 7(1) × 13(2) × 17(2) × 19(2) × 37(2) × 73(2) × 109(3) × 241(3) × 433(3) × 38737(5) (temps de calcul : 0,012349 s)

M₇₃ = 2⁷³ − 1 = 9444732965739290427391(22) =
439(3) × 2298041(7) × 9361973132609(13) (temps de calcul : 0,169009 s)

M₇₄ = 2⁷⁴ − 1 = 18889465931478580854783(23) =
3(1) × 223(3) × 1777(4) × 25781083(8) × 616318177(9) (temps de calcul : 1,688764 s)

M₇₅ = 2⁷⁵ − 1 = 37778931862957161709567(23) =
7(1) × 31(2) × 151(3) × 601(3) × 1801(4) × 100801(6) × 10567201(8) (temps de calcul : 0,061874 s)

M₇₆ = 2⁷⁶ − 1 = 75557863725914323419135(23) =
3(1) × 5(1) × 229(3) × 457(3) × 525313(6) × 524287(6) × 174763(6) (temps de calcul : 0,145446 s)

M₇₇ = 2⁷⁷ − 1 = 151115727451828646838271(24) =
23(2) × 89(2) × 127(3) × 581283643249112959(18) (temps de calcul : 0,154349 s)

M₇₈ = 2⁷⁸ − 1 = 302231454903657293676543(24) =
3(1) × 3(1) × 7(1) × 79(2) × 2731(4) × 8191(4) × 121369(6) × 22366891(8) (temps de calcul : 0,117375 s)

M₇₉ = 2⁷⁹ − 1 = 604462909807314587353087(24) =
2687(4) × 202029703(9) × 1113491139767(13) (temps de calcul : 2,256905 s)

M₈₀ = 2⁸⁰ − 1 = 1208925819614629174706175(25) =
3(1) × 5(1) × 5(1) × 11(2) × 17(2) × 31(2) × 41(2) × 257(3) × 61681(5) × 4278255361(10) (temps de calcul : 0,066193 s)

M₈₁ = 2⁸¹ − 1 = 2417851639229258349412351(25) =
7(1) × 73(2) × 2593(4) × 71119(5) × 262657(6) × 97685839(8) (temps de calcul : 0,165829 s)

M₈₂ = 2⁸² − 1 = 4835703278458516698824703(25) =
3(1) × 83(2) × 13367(5) × 164511353(9) × 8831418697(10) (temps de calcul : 0,626556 s)

M₈₃ = 2⁸³ − 1 = 9671406556917033397649407(25) =
167(3) × 57912614113275649087721(23) (temps de calcul : 0,293461 s)

M₈₄ = 2⁸⁴ − 1 = 19342813113834066795298815(26) =
3(1) × 3(1) × 5(1) × 7(1) × 7(1) × 13(2) × 29(2) × 43(2) × 113(3) × 127(3) × 337(3) × 1429(4) × 5419(4) × 14449(5) (temps de calcul : 0,031094 s)

M₈₅ = 2⁸⁵ − 1 = 38685626227668133590597631(26) =
31(2) × 131071(6) × 9520972806333758431(19) (temps de calcul : 0,229431 s)

M₈₆ = 2⁸⁶ − 1 = 77371252455336267181195263(26) =
3(1) × 431(3) × 9719(4) × 2099863(7) × 2932031007403(13) (temps de calcul : 0,377058 s)

M₈₇ = 2⁸⁷ − 1 = 154742504910672534362390527(27) =
7(1) × 233(3) × 1103(4) × 2089(4) × 4177(4) × 9857737155463(13) (temps de calcul : 0,115468 s)

M₈₈ = 2⁸⁸ − 1 = 309485009821345068724781055(27) =
3(1) × 5(1) × 17(2) × 23(2) × 89(2) × 353(3) × 397(3) × 683(3) × 2113(4) × 2931542417(10) (temps de calcul : 0,055248 s)

M₈₉ = 2⁸⁹ − 1 = 618970019642690137449562111(27) =
618970019642690137449562111(27) : nombre premier (temps de calcul : 1,110623 s)

M₉₀ = 2⁹⁰ − 1 = 1237940039285380274899124223(28) =
3(1) × 3(1) × 3(1) × 7(1) × 11(2) × 19(2) × 31(2) × 73(2) × 151(3) × 331(3) × 631(3) × 23311(5) × 18837001(8) (temps de calcul : 0,051574 s)

M₉₁ = 2⁹¹ − 1 = 2475880078570760549798248447(28) =
127(3) × 911(3) × 8191(4) × 112901153(9) × 23140471537(11) (temps de calcul : 2,328416 s)

M₉₂ = 2⁹² − 1 = 4951760157141521099596496895(28) =
3(1) × 5(1) × 47(2) × 277(3) × 1013(4) × 1657(4) × 178481(6) × 30269(5) × 2796203(7) (temps de calcul : 0,101921 s)

M₉₃ = 2⁹³ − 1 = 9903520314283042199192993791(28) =
7(1) × 2147483647(10) × 658812288653553079(18) (temps de calcul : 14,295108 s)

M₉₄ = 2⁹⁴ − 1 = 19807040628566084398385987583(29) =
3(1) × 283(3) × 2351(4) × 4513(4) × 13264529(8) × 165768537521(12) (temps de calcul : 0,579194 s)

M₉₅ = 2⁹⁵ − 1 = 39614081257132168796771975167(29) =
31(2) × 191(3) × 524287(6) × 420778751(9) × 30327152671(11) (temps de calcul : 2,670889 s)

M₉₆ = 2⁹⁶ − 1 = 79228162514264337593543950335(29) =
3(1) × 3(1) × 5(1) × 7(1) × 13(2) × 17(2) × 97(2) × 193(3) × 241(3) × 257(3) × 673(3) × 65537(5) × 22253377(8) (temps de calcul : 0,062759 s)

M₉₇ = 2⁹⁷ − 1 = 158456325028528675187087900671(30) =
11447(5) × 13842607235828485645766393(26) (temps de calcul : 0,441701 s)

M₉₈ = 2⁹⁸ − 1 = 316912650057057350374175801343(30) =
3(1) × 43(2) × 127(3) × 4363953127297(13) × 4432676798593(13) (temps de calcul : 109,166679 s)

M₉₉ = 2⁹⁹ − 1 = 633825300114114700748351602687(30) =
7(1) × 23(2) × 73(2) × 89(2) × 199(3) × 153649(6) × 599479(6) × 33057806959(11) (temps de calcul : 0,228902 s)

M₁₀₀ = 2¹⁰⁰ − 1 = 1267650600228229401496703205375(31) =
3(1) × 5(1) × 5(1) × 5(1) × 11(2) × 31(2) × 41(2) × 101(3) × 251(3) × 601(3) × 1801(4) × 8101(4) × 4051(4) × 268501(6) (temps de calcul : 0,055150 s)

M₁₀₁ = 2¹⁰¹ − 1 = 2535301200456458802993406410751(31) =
7432339208719(13) × 341117531003194129(18) (temps de calcul : 339,596614 s)

M₁₀₂ = 2¹⁰² − 1 = 5070602400912917605986812821503(31) =
3(1) × 3(1) × 7(1) × 103(3) × 307(3) × 2143(4) × 2857(4) × 6529(4) × 11119(5) × 43691(5) × 131071(6) (temps de calcul : 0,109578 s)

M₁₀₃ = 2¹⁰³ − 1 = 10141204801825835211973625643007(32) =
2550183799(10) × 3976656429941438590393(22) (temps de calcul : 14,061908 s)

M₁₀₄ = 2¹⁰⁴ − 1 = 20282409603651670423947251286015(32) =
3(1) × 5(1) × 17(2) × 53(2) × 157(3) × 1613(4) × 2731(4) × 8191(4) × 858001(6) × 308761441(9) (temps de calcul : 0,217423 s)

M₁₀₅ = 2¹⁰⁵ − 1 = 40564819207303340847894502572031(32) =
7(1) × 7(1) × 31(2) × 71(2) × 127(3) × 151(3) × 337(3) × 152041(6) × 106681(6) × 29191(5) × 122921(6) (temps de calcul : 0,116471 s)

M₁₀₆ = 2¹⁰⁶ − 1 = 81129638414606681695789005144063(32) =
3(1) × 107(3) × 6361(4) × 69431(5) × 20394401(8) × 28059810762433(14) (temps de calcul : 1,452694 s)

M₁₀₇ = 2¹⁰⁷ − 1 = 162259276829213363391578010288127(33) =
162259276829213363391578010288127(33) : nombre premier (temps de calcul : 1,910127 s)

M₁₀₈ = 2¹⁰⁸ − 1 = 324518553658426726783156020576255(33) =
3(1) × 3(1) × 3(1) × 3(1) × 5(1) × 7(1) × 13(2) × 19(2) × 37(2) × 73(2) × 109(3) × 87211(5) × 279073(6) × 262657(6) × 246241(6) (temps de calcul : 0,273271 s)

M₁₀₉ = 2¹⁰⁹ − 1 = 649037107316853453566312041152511(33) =
745988807(9) × 870035986098720987332873(24) (temps de calcul : 10,680712 s)

M₁₁₀ = 2¹¹⁰ − 1 = 1298074214633706907132624082305023(34) =
3(1) × 11(2) × 11(2) × 23(2) × 31(2) × 89(2) × 683(3) × 881(3) × 2971(4) × 3191(4) × 201961(6) × 48912491(8) (temps de calcul : 0,114724 s)

M₁₁₁ = 2¹¹¹ − 1 = 2596148429267413814265248164610047(34) =
7(1) × 223(3) × 321679(6) × 26295457(8) × 616318177(9) × 319020217(9) (temps de calcul : 2,167669 s)

M₁₁₂ = 2¹¹² − 1 = 5192296858534827628530496329220095(34) =
3(1) × 5(1) × 17(2) × 29(2) × 43(2) × 113(3) × 127(3) × 257(3) × 5153(4) × 15790321(8) × 54410972897(11) (temps de calcul : 0,577667 s)

M₁₁₃ = 2¹¹³ − 1 = 10384593717069655257060992658440191(35) =
3391(4) × 65993(5) × 23279(5) × 1868569(7) × 1066818132868207(16) (temps de calcul : 0,453087 s)

M₁₁₄ = 2¹¹⁴ − 1 = 20769187434139310514121985316880383(35) =
3(1) × 3(1) × 7(1) × 571(3) × 32377(5) × 174763(6) × 1212847(7) × 524287(6) × 160465489(9) (temps de calcul : 0,476220 s)

M₁₁₅ = 2¹¹⁵ − 1 = 41538374868278621028243970633760767(35) =
31(2) × 47(2) × 14951(5) × 4036961(7) × 178481(6) × 2646507710984041(16) (temps de calcul : 0,410467 s)

M₁₁₆ = 2¹¹⁶ − 1 = 83076749736557242056487941267521535(35) =
3(1) × 5(1) × 59(2) × 233(3) × 1103(4) × 2089(4) × 3033169(7) × 107367629(9) × 536903681(9) (temps de calcul : 1,224905 s)

M₁₁₇ = 2¹¹⁷ − 1 = 166153499473114484112975882535043071(36) =
7(1) × 73(2) × 79(2) × 937(3) × 8191(4) × 6553(4) × 121369(6) × 86113(5) × 7830118297(10) (temps de calcul : 0,234257 s)

M₁₁₈ = 2¹¹⁸ − 1 = 332306998946228968225951765070086143(36) =
3(1) × 2833(4) × 37171(5) × 179951(6) × 1824726041(10) × 3203431780337(13) (temps de calcul : 3,958981 s)

M₁₁₉ = 2¹¹⁹ − 1 = 664613997892457936451903530140172287(36) =
127(3) × 239(3) × 131071(6) × 20231(5) × 62983048367(11) × 131105292137(12) (temps de calcul : 83,686294 s)

M₁₂₀ = 2¹²⁰ − 1 = 1329227995784915872903807060280344575(37) =
3(1) × 3(1) × 5(1) × 5(1) × 7(1) × 11(2) × 13(2) × 17(2) × 31(2) × 41(2) × 61(2) × 151(3) × 241(3) × 331(3) × 1321(4) × 61681(5) × 4562284561(10) (temps de calcul : 0,146708 s)

M₁₂₁ = 2¹²¹ − 1 = 2658455991569831745807614120560689151(37) =
23(2) × 89(2) × 727(3) × 1786393878363164227858270210279(31) (temps de calcul : 0,700558 s)

M₁₂₃ = 2¹²³ − 1 = 10633823966279326983230456482242756607(38) =
7(1) × 13367(5) × 3887047(7) × 164511353(9) × 177722253954175633(18) (temps de calcul : 1,523651 s)

M₁₂₄ = 2¹²⁴ − 1 = 21267647932558653966460912964485513215(38) =
3(1) × 5(1) × 5581(4) × 49477(5) × 8681(4) × 384773(6) × 715827883(9) × 2147483647(10) (temps de calcul : 1,650659 s)

M₁₂₅ = 2¹²⁵ − 1 = 42535295865117307932921825928971026431(38) =
31(2) × 601(3) × 1801(4) × 269089806001(12) × 4710883168879506001(19) (temps de calcul : 134,247035 s)

M₁₂₆ = 2¹²⁶ − 1 = 85070591730234615865843651857942052863(38) =
3(1) × 3(1) × 3(1) × 7(1) × 7(1) × 19(2) × 43(2) × 73(2) × 127(3) × 337(3) × 5419(4) × 92737(5) × 649657(6) × 77158673929(11) (temps de calcul : 0,351213 s)

M₁₂₇ = 2¹²⁷ − 1 = 170141183460469231731687303715884105727(39) =
170141183460469231731687303715884105727(39) : nombre premier (temps de calcul : 3,194471 s)

M₁₂₈ = 2¹²⁸ − 1 = 340282366920938463463374607431768211455(39) =
3(1) × 5(1) × 17(2) × 257(3) × 641(3) × 65537(5) × 274177(6) × 6700417(7) × 67280421310721(14) (temps de calcul : 0,818332 s)

M₁₂₉ = 2¹²⁹ − 1 = 680564733841876926926749214863536422911(39) =
7(1) × 431(3) × 9719(4) × 2099863(7) × 11053036065049294753459639(26) (temps de calcul : 0,757458 s)

M₁₃₀ = 2¹³⁰ − 1 = 1361129467683753853853498429727072845823(40) =
3(1) × 11(2) × 31(2) × 131(3) × 2731(4) × 8191(4) × 409891(6) × 7623851(7) × 145295143558111(15) (temps de calcul : 0,963254 s)

M₁₃₁ = 2¹³¹ − 1 = 2722258935367507707706996859454145691647(40) =
263(3) × 10350794431055162386718619237468234569(38) (temps de calcul : 1,214412 s)

M₁₃₂ = 2¹³² − 1 = 5444517870735015415413993718908291383295(40) =
3(1) × 3(1) × 5(1) × 7(1) × 13(2) × 23(2) × 67(2) × 89(2) × 397(3) × 683(3) × 2113(4) × 20857(5) × 312709(6) × 599479(6) × 4327489(7) (temps de calcul : 0,289144 s)

M₁₃₃ = 2¹³³ − 1 = 10889035741470030830827987437816582766591(41) =
127(3) × 524287(6) × 163537220852725398851434325720959(33) (temps de calcul : 1,313349 s)

M₁₃₄ = 2¹³⁴ − 1 = 21778071482940061661655974875633165533183(41) =
3(1) × 7327657(7) × 193707721(9) × 761838257287(12) × 6713103182899(13) (temps de calcul : 111,577564 s)

M₁₃₅ = 2¹³⁵ − 1 = 43556142965880123323311949751266331066367(41) =
7(1) × 31(2) × 73(2) × 151(3) × 271(3) × 631(3) × 23311(5) × 348031(6) × 262657(6) × 49971617830801(14) (temps de calcul : 0,361143 s)

M₁₃₆ = 2¹³⁶ − 1 = 87112285931760246646623899502532662132735(41) =
3(1) × 5(1) × 17(2) × 17(2) × 137(3) × 953(3) × 26317(5) × 131071(6) × 43691(5) × 354689(6) × 2879347902817(13) (temps de calcul : 0,423485 s)

M₁₃₈ = 2¹³⁸ − 1 = 348449143727040986586495598010130648530943(42) =
3(1) × 3(1) × 7(1) × 47(2) × 139(3) × 178481(6) × 2796203(7) × 168749965921(12) × 10052678938039(14) (temps de calcul : 28,462524 s)

M₁₃₉ = 2¹³⁹ − 1 = 696898287454081973172991196020261297061887(42) =
5625767248687(13) × 123876132205208335762278423601(30) (temps de calcul : 2058,215868 s)

M₁₄₀ = 2¹⁴⁰ − 1 = 1393796574908163946345982392040522594123775(43) =
3(1) × 5(1) × 5(1) × 11(2) × 29(2) × 31(2) × 41(2) × 43(2) × 71(2) × 113(3) × 127(3) × 281(3) × 122921(6) × 86171(5) × 7416361(7) × 47392381(8) (temps de calcul : 0,345962 s)

M₁₄₁ = 2¹⁴¹ − 1 = 2787593149816327892691964784081045188247551(43) =
7(1) × 2351(4) × 4513(4) × 13264529(8) × 4375578271(10) × 646675035253258729(18) (temps de calcul : 16,111745 s)

M₁₄₂ = 2¹⁴² − 1 = 5575186299632655785383929568162090376495103(43) =
3(1) × 228479(6) × 212885833(9) × 56409643(8) × 48544121(8) × 13952598148481(14) (temps de calcul : 3,720195 s)

M₁₄₃ = 2¹⁴³ − 1 = 11150372599265311570767859136324180752990207(44) =
23(2) × 89(2) × 8191(4) × 724153(6) × 158822951431(12) × 5782172113400990737(19) (temps de calcul : 66,241051 s)

M₁₄₄ = 2¹⁴⁴ − 1 = 22300745198530623141535718272648361505980415(44) =
3(1) × 3(1) × 3(1) × 5(1) × 7(1) × 13(2) × 17(2) × 19(2) × 37(2) × 73(2) × 97(2) × 109(3) × 241(3) × 257(3) × 433(3) × 577(3) × 673(3) × 38737(5) × 487824887233(12) (temps de calcul : 0,154265 s)

M₁₄₅ = 2¹⁴⁵ − 1 = 44601490397061246283071436545296723011960831(44) =
31(2) × 233(3) × 1103(4) × 2089(4) × 2679895157783862814690027494144991(34) (temps de calcul : 0,936695 s)

M₁₄₆ = 2¹⁴⁶ − 1 = 89202980794122492566142873090593446023921663(44) =
3(1) × 439(3) × 1753(4) × 2298041(7) × 9361973132609(13) × 1795918038741070627(19) (temps de calcul : 1148,264036 s)

M₁₄₇ = 2¹⁴⁷ − 1 = 178405961588244985132285746181186892047843327(45) =
7(1) × 7(1) × 7(1) × 127(3) × 337(3) × 4432676798593(13) × 2741672362528725535068727(25) (temps de calcul : 482,217768 s)

M₁₄₈ = 2¹⁴⁸ − 1 = 356811923176489970264571492362373784095686655(45) =
3(1) × 5(1) × 149(3) × 223(3) × 593(3) × 1777(4) × 25781083(8) × 184481113(9) × 231769777(9) × 616318177(9) (temps de calcul : 3,468503 s)

M₁₅₀ = 2¹⁵⁰ − 1 = 1427247692705959881058285969449495136382746623(46) =
3(1) × 3(1) × 7(1) × 11(2) × 31(2) × 151(3) × 251(3) × 331(3) × 601(3) × 1801(4) × 4051(4) × 100801(6) × 10567201(8) × 1133836730401(13) (temps de calcul : 0,870632 s)

M₁₅₁ = 2¹⁵¹ − 1 = 2854495385411919762116571938898990272765493247(46) =
18121(5) × 165799(6) × 55871(5) × 2332951(7) × 7289088383388253664437433(25) (temps de calcul : 1,759978 s)

M₁₅₂ = 2¹⁵² − 1 = 5708990770823839524233143877797980545530986495(46) =
3(1) × 5(1) × 17(2) × 229(3) × 457(3) × 1217(4) × 525313(6) × 174763(6) × 148961(6) × 524287(6) × 24517014940753(14) (temps de calcul : 0,663364 s)

M₁₅₃ = 2¹⁵³ − 1 = 11417981541647679048466287755595961091061972991(47) =
7(1) × 73(2) × 103(3) × 919(3) × 2143(4) × 11119(5) × 131071(6) × 75582488424179347083438319(26) (temps de calcul : 0,660849 s)

M₁₅₄ = 2¹⁵⁴ − 1 = 22835963083295358096932575511191922182123945983(47) =
3(1) × 23(2) × 43(2) × 89(2) × 127(3) × 617(3) × 683(3) × 78233(5) × 35532364099(11) × 581283643249112959(18) (temps de calcul : 58,571867 s)

M₁₅₅ = 2¹⁵⁵ − 1 = 45671926166590716193865151022383844364247891967(47) =
31(2) × 31(2) × 311(3) × 11471(5) × 73471(5) × 4649919401(10) × 2147483647(10) × 18158209813151(14) (temps de calcul : 14,068695 s)

M₁₅₆ = 2¹⁵⁶ − 1 = 91343852333181432387730302044767688728495783935(47) =
3(1) × 3(1) × 5(1) × 7(1) × 13(2) × 13(2) × 53(2) × 79(2) × 157(3) × 313(3) × 1249(4) × 1613(4) × 2731(4) × 3121(4) × 8191(4) × 21841(5) × 121369(6) × 22366891(8) (temps de calcul : 0,211030 s)

M₁₅₇ = 2¹⁵⁷ − 1 = 182687704666362864775460604089535377456991567871(48) =
852133201(9) × 60726444167(11) × 1654058017289(13) × 2134387368610417(16) (temps de calcul : 428,819124 s)

M₁₅₈ = 2¹⁵⁸ − 1 = 365375409332725729550921208179070754913983135743(48) =
3(1) × 2687(4) × 202029703(9) × 1113491139767(13) × 201487636602438195784363(24) (temps de calcul : 157,165306 s)

M₁₅₉ = 2¹⁵⁹ − 1 = 730750818665451459101842416358141509827966271487(48) =
7(1) × 6679(4) × 69431(5) × 6361(4) × 540701761(9) × 13960201(8) × 20394401(8) × 229890275929(12) (temps de calcul : 6,160888 s)

M₁₆₀ = 2¹⁶⁰ − 1 = 1461501637330902918203684832716283019655932542975(49) =
3(1) × 5(1) × 5(1) × 11(2) × 17(2) × 31(2) × 41(2) × 257(3) × 65537(5) × 61681(5) × 414721(6) × 4278255361(10) × 44479210368001(14) (temps de calcul : 13,576072 s)

M₁₆₁ = 2¹⁶¹ − 1 = 2923003274661805836407369665432566039311865085951(49) =
47(2) × 127(3) × 1289(4) × 178481(6) × 3188767(7) × 45076044553(11) × 14808607715315782481(20) (temps de calcul : 129,128352 s)

M₁₆₂ = 2¹⁶² − 1 = 5846006549323611672814739330865132078623730171903(49) =
3(1) × 3(1) × 3(1) × 3(1) × 3(1) × 7(1) × 19(2) × 73(2) × 163(3) × 2593(4) × 87211(5) × 262657(6) × 135433(6) × 71119(5) × 272010961(9) × 97685839(8) (temps de calcul : 2,461799 s)

M₁₆₃ = 2¹⁶³ − 1 = 11692013098647223345629478661730264157247460343807(50) =
150287(6) × 704161(6) × 110211473(9) × 27669118297(11) × 36230454570129675721(20) (temps de calcul : 89,678750 s)

M₁₆₄ = 2¹⁶⁴ − 1 = 23384026197294446691258957323460528314494920687615(50) =
3(1) × 5(1) × 83(2) × 13367(5) × 181549(6) × 10169(5) × 43249589(8) × 12112549(8) × 164511353(9) × 8831418697(10) (temps de calcul : 4,880545 s)

M₁₆₅ = 2¹⁶⁵ − 1 = 46768052394588893382517914646921056628989841375231(50) =
7(1) × 23(2) × 31(2) × 89(2) × 151(3) × 881(3) × 3191(4) × 599479(6) × 201961(6) × 2048568835297380486760231(25) (temps de calcul : 0,943280 s)

M₁₆₆ = 2¹⁶⁶ − 1 = 93536104789177786765035829293842113257979682750463(50) =
3(1) × 167(3) × 499(3) × 1163(4) × 2657(4) × 155377(6) × 13455809771(11) × 57912614113275649087721(23) (temps de calcul : 96,330702 s)

M₁₆₇ = 2¹⁶⁷ − 1 = 187072209578355573530071658587684226515959365500927(51) =
2349023(7) × 79638304766856507377778616296087448490695649(44) (temps de calcul : 3,242270 s)

M₁₆₈ = 2¹⁶⁸ − 1 = 374144419156711147060143317175368453031918731001855(51) =
3(1) × 3(1) × 5(1) × 7(1) × 7(1) × 13(2) × 17(2) × 29(2) × 43(2) × 113(3) × 127(3) × 241(3) × 337(3) × 1429(4) × 3361(4) × 5419(4) × 14449(5) × 15790321(8) × 88959882481(11) (temps de calcul : 1,213377 s)

M₁₆₉ = 2¹⁶⁹ − 1 = 748288838313422294120286634350736906063837462003711(51) =
4057(4) × 8191(4) × 6740339310641(13) × 3340762283952395329506327023033(31) (temps de calcul : 2527,257952 s)