Problème de factorisation
La décomposition en facteurs premiers de grands entiers (nombres composés de plusieurs dizaines de chiffres) est encore de nos jours 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 et 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 de ce nombre 30 031 ou encore de 4 294 967 297, le sixième nombre de Fermat.
Fermat avait conjecturé au 17ème siècle (vers 1640) que les nombres de la forme
étaient premiers. Cette conjecture se révéla fausse. Les 5 premiers nombres de Fermat sont effectivement premiers.
F0 = 3 ; F1 = 5 ; F2 = 17 ; F3 = 257 ; F4 = 65537.
Mais le sixième 4 294 967 297 ne l’est pas. C’est le mathématicien Euler qui, en 1733, près d’un siècle plus tard, montra que le sixième nombre de Fermat pouvait se factoriser en 2 termes.
En 1867, Landry trouve que le nombre de Mersenne M59 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 était premier, il lui faut encore plus de 1000 divisions pour y parvenir. Ce nombre est resté le plus grand nombre premier connu pendant 9 ans.
Le 7ème nombre de Fermat F6 = 274177 × 67280421310721 fut, quand à 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 20ème siècle, Frank Nelson Cole a donné la factorisation du nombre de Mersenne M67 = 267 − 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.
M67 = 193 707 721 × 761 838 257 287.
Le 8ème nombre de Fermat F7 = 2128 + 1 (composé de 39 chiffres) n’a, quand à 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 250000 secondes à mon meilleur programme pour le décomposer (sur un mac à 2ghz) :
2^128+1 = 340282366920938463463374607431768211457(39) =
59649589127497217(17) * 5704689200685129054721(22) * 1 Temps en seconde(s) : 251151.280743
De nos jour les meilleurs algorithmes le font en quelques secondes.
Factorisation des nombres de Mersenne
Voilà ce que l'on peut obtenir avec un ordinateur de particulier et quelques heures de programmation. Nous trouvons plusieurs algorithme sont à disposition sur le net, les plus triviaux ne mèment pas bien loin. Vous vous trouvez rapidement bloqué. Ne serais par les nombres de Mersenne qui sont premier. Il faut donc implanté un test de primilarité , j'ai choisi celui de Miller-Rabin, cela vous permet de ne pas avoir à tester, par votre algorithme de factorisation, les facteurs qui sont premiers.
Même avec ce test les résultats sont assez lents. M59 est un bon candidat pour tester des algorithmes. En effet sa factorisation est facilement accessible, mais tout même significative, du fait qu'il posséde seulement 2 facteurs premiers.
Nous appelerons l'algorithme "force brute", l'algorithme de division successives jusqu'à la racine carré du nombre tester.
Factorisation de M59 en force brute avec le test de Miller-Rabin
M_59 = 2^59-1 = 576460752303423487(18) =
179951(6) * 3203431780337(13) * Temps en seconde(s) : 3.014073
Factorisation de M59 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_59 = 2^59-1 = 576460752303423487(18) =
179951(6) * 3203431780337(13) * Temps en seconde(s) : 0.192607
avec cette méthode la factorisation de M67 devient accessible :
M_67 = 2^67-1 = 147573952589676412927(21) =
193707721(9) * 761838257287(12) * Temps en seconde(s) : 55.185544
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 280 fois plus long pour un petit facteur qui posséde seulement 3 chiffres de plus. De plus cette optimisation n'est valable que les nombre de Mersenne, c'est-à-dire pour p premier, et pas pour les autres valeurs de p.
Factorisation de M67 avec l'algorithme de rho pollard sans autre optimisation :
M_67 = 2^67-1 = 147573952589676412927(21) =
193707721(9) * 761838257287(12) * Temps en seconde(s) : 6.954788
Factorisation de M67 avec l'algorithme de rho pollard avec un algorithme de division rapide dans les divisions de rho Pollard :
M_67 = 2^67-1 = 147573952589676412927(21) =
193707721(9) * 761838257287(12) * Temps en seconde(s) : 1.870080
Factorisation des nombres de Mersenne à l'aide de l'algorithme de Brent Pollard et de la division rapide et du test de Miller-Rabin
Cette fois l'algorithme de brent pollard aidé de la division rapide pour les calculs modulo n peut nous permettre d'accéder à la factorisation des premiers nombres de Mersenne et des autres puissance, jusqu'au nombre 2169 − 1; excepté faite de 2122 − 1, 2137 − 1 et 2149 − 1 ces nombres sont des pseudos premiers composés de deux facteurs premiers dont les plus petits facteurs possédent au minimun 17 chiffres.
M_2 = 2^2-1 = 3(1) =
3(1) * 1 Temps en seconde(s) : 0.003421
M_3 = 2^3-1 = 7(1) =
7(1) * Temps en seconde(s) : 0.003405
M_4 = 2^4-1 = 15(2) =
3(1) * 5(1) * Temps en seconde(s) : 0.003376
M_5 = 2^5-1 = 31(2) =
31(2) * Temps en seconde(s) : 0.003448
M_6 = 2^6-1 = 63(2) =
3(1) * 3(1) * 7(1) * Temps en seconde(s) : 0.003367
M_7 = 2^7-1 = 127(3) =
127(3) * Temps en seconde(s) : 0.003398
M_8 = 2^8-1 = 255(3) =
3(1) * 5(1) * 17(2) * Temps en seconde(s) : 0.003388
M_9 = 2^9-1 = 511(3) =
7(1) * 73(2) * Temps en seconde(s) : 0.003426
M_10 = 2^10-1 = 1023(4) =
3(1) * 11(2) * 31(2) * Temps en seconde(s) : 0.003433
M_11 = 2^11-1 = 2047(4) =
23(2) * 89(2) * Temps en seconde(s) : 0.003474
M_12 = 2^12-1 = 4095(4) =
3(1) * 3(1) * 5(1) * 7(1) * 13(2) * Temps en seconde(s) : 0.003518
M_13 = 2^13-1 = 8191(4) =
8191(4) * Temps en seconde(s) : 0.005621
M_14 = 2^14-1 = 16383(5) =
3(1) * 43(2) * 127(3) * Temps en seconde(s) : 0.003677
M_15 = 2^15-1 = 32767(5) =
7(1) * 31(2) * 151(3) * Temps en seconde(s) : 0.003614
M_16 = 2^16-1 = 65535(5) =
3(1) * 5(1) * 17(2) * 257(3) * Temps en seconde(s) : 0.003527
M_17 = 2^17-1 = 131071(6) =
131071(6) * 1 PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER Temps en seconde(s) : 0.019437
M_18 = 2^18-1 = 262143(6) =
3(1) * 3(1) * 3(1) * 7(1) * 19(2) * 73(2) * Temps en seconde(s) : 0.003686
M_19 = 2^19-1 = 524287(6) =
524287(6) * 1 PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER Temps en seconde(s) : 0.022863
M_20 = 2^20-1 = 1048575(7) =
3(1) * 5(1) * 5(1) * 11(2) * 31(2) * 41(2) * Temps en seconde(s) : 0.003754
M_21 = 2^21-1 = 2097151(7) =
7(1) * 7(1) * 127(3) * 337(3) * Temps en seconde(s) : 0.003950
M_22 = 2^22-1 = 4194303(7) =
3(1) * 23(2) * 89(2) * 683(3) * Temps en seconde(s) : 0.003960
M_23 = 2^23-1 = 8388607(7) =
47(2) * 178481(6) * 1 Temps en seconde(s) : 0.012252
M_24 = 2^24-1 = 16777215(8) =
3(1) * 3(1) * 5(1) * 7(1) * 13(2) * 17(2) * 241(3) * Temps en seconde(s) : 0.003912
M_25 = 2^25-1 = 33554431(8) =
31(2) * 601(3) * 1801(4) * Temps en seconde(s) : 0.004751
M_26 = 2^26-1 = 67108863(8) =
3(1) * 2731(4) * 8191(4) * Temps en seconde(s) : 0.009366
M_27 = 2^27-1 = 134217727(9) =
7(1) * 73(2) * 262657(6) * 1 Temps en seconde(s) : 0.011082
M_28 = 2^28-1 = 268435455(9) =
3(1) * 5(1) * 29(2) * 43(2) * 113(3) * 127(3) * Temps en seconde(s) : 0.004298
M_29 = 2^29-1 = 536870911(9) =
233(3) * 1103(4) * 2089(4) * Temps en seconde(s) : 0.006115
M_30 = 2^30-1 = 1073741823(10) =
3(1) * 3(1) * 7(1) * 11(2) * 31(2) * 151(3) * 331(3) * Temps en seconde(s) : 0.004395
M_31 = 2^31-1 = 2147483647(10) =
2147483647(10) * 1 PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER Temps en seconde(s) : 0.067856
M_32 = 2^32-1 = 4294967295(10) =
3(1) * 5(1) * 17(2) * 257(3) * 65537(5) * Temps en seconde(s) : 0.006768
M_33 = 2^33-1 = 8589934591(10) =
7(1) * 23(2) * 89(2) * 599479(6) * Temps en seconde(s) : 0.007629
M_34 = 2^34-1 = 17179869183(11) =
3(1) * 43691(5) * 131071(6) * 1 Temps en seconde(s) : 0.040584
M_35 = 2^35-1 = 34359738367(11) =
31(2) * 71(2) * 127(3) * 122921(6) * 1 Temps en seconde(s) : 0.011421
M_36 = 2^36-1 = 68719476735(11) =
3(1) * 3(1) * 19(2) * 5(1) * 7(1) * 3(1) * 3(1) * 3(1) * 13(2) * 3(1) * 37(2) * 73(2) * 109(3) * Temps en seconde(s) : 0.010154
M_37 = 2^37-1 = 137438953471(12) =
223(3) * 616318177(9) * 1 Temps en seconde(s) : 0.032471
M_38 = 2^38-1 = 274877906943(12) =
3(1) * 524287(6) * 174763(6) * 1 Temps en seconde(s) : 0.052345
M_39 = 2^39-1 = 549755813887(12) =
7(1) * 79(2) * 8191(4) * 121369(6) * Temps en seconde(s) : 0.021484
M_40 = 2^40-1 = 1099511627775(13) =
3(1) * 5(1) * 5(1) * 11(2) * 17(2) * 31(2) * 41(2) * 61681(5) * 1 Temps en seconde(s) : 0.011037
M_41 = 2^41-1 = 2199023255551(13) =
13367(5) * 164511353(9) * 1 Temps en seconde(s) : 0.040871
M_42 = 2^42-1 = 4398046511103(13) =
3(1) * 3(1) * 7(1) * 7(1) * 43(2) * 127(3) * 337(3) * 5419(4) * Temps en seconde(s) : 0.006254
M_43 = 2^43-1 = 8796093022207(13) =
431(3) * 9719(4) * 2099863(7) * 1 Temps en seconde(s) : 0.031486
M_44 = 2^44-1 = 17592186044415(14) =
3(1) * 5(1) * 23(2) * 89(2) * 397(3) * 683(3) * 2113(4) * Temps en seconde(s) : 0.006772
M_45 = 2^45-1 = 35184372088831(14) =
7(1) * 31(2) * 73(2) * 151(3) * 631(3) * 23311(5) * Temps en seconde(s) : 0.010162
M_46 = 2^46-1 = 70368744177663(14) =
3(1) * 47(2) * 178481(6) * 2796203(7) * 1 Temps en seconde(s) : 0.060587
M_47 = 2^47-1 = 140737488355327(15) =
2351(4) * 4513(4) * 13264529(8) * 1 Temps en seconde(s) : 0.043228
M_48 = 2^48-1 = 281474976710655(15) =
3(1) * 13(2) * 5(1) * 3(1) * 7(1) * 3(1) * 3(1) * 241(3) * 97(2) * 17(2) * 257(3) * 673(3) * Temps en seconde(s) : 0.014543
M_49 = 2^49-1 = 562949953421311(15) =
127(3) * 4432676798593(13) * 1 Temps en seconde(s) : 0.049894
M_50 = 2^50-1 = 1125899906842623(16) =
3(1) * 11(2) * 3(1) * 31(2) * 251(3) * 601(3) * 1801(4) * 4051(4) * Temps en seconde(s) : 0.018363
M_51 = 2^51-1 = 2251799813685247(16) =
7(1) * 103(3) * 2143(4) * 11119(5) * 131071(6) * 1 Temps en seconde(s) : 0.044818
M_52 = 2^52-1 = 4503599627370495(16) =
3(1) * 5(1) * 53(2) * 157(3) * 1613(4) * 2731(4) * 8191(4) * Temps en seconde(s) : 0.013494
M_53 = 2^53-1 = 9007199254740991(16) =
6361(4) * 69431(5) * 20394401(8) * 1 Temps en seconde(s) : 0.075092
M_54 = 2^54-1 = 18014398509481983(17) =
3(1) * 3(1) * 3(1) * 3(1) * 7(1) * 19(2) * 73(2) * 87211(5) * 262657(6) * 1 Temps en seconde(s) : 0.046612
M_55 = 2^55-1 = 36028797018963967(17) =
23(2) * 31(2) * 89(2) * 881(3) * 3191(4) * 201961(6) * 1 Temps en seconde(s) : 0.021523
M_56 = 2^56-1 = 72057594037927935(17) =
3(1) * 5(1) * 17(2) * 29(2) * 43(2) * 113(3) * 127(3) * 15790321(8) * 1 Temps en seconde(s) : 0.027449
M_57 = 2^57-1 = 144115188075855871(18) =
7(1) * 32377(5) * 524287(6) * 1212847(7) * 1 Temps en seconde(s) : 0.103639
M_58 = 2^58-1 = 288230376151711743(18) =
3(1) * 59(2) * 233(3) * 1103(4) * 2089(4) * 3033169(7) * 1 Temps en seconde(s) : 0.024562
M_59 = 2^59-1 = 576460752303423487(18) =
179951(6) * 3203431780337(13) * 1 Temps en seconde(s) : 0.143974
M_60 = 2^60-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 en seconde(s) : 0.008499
M_61 = 2^61-1 = 2305843009213693951(19) =
2305843009213693951(19) * 1 PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER Temps en seconde(s) : 0.356570
M_62 = 2^62-1 = 4611686018427387903(19) =
3(1) * 715827883(9) * 2147483647(10) * 1 Temps en seconde(s) : 3.634923
M_63 = 2^63-1 = 9223372036854775807(19) =
7(1) * 7(1) * 73(2) * 127(3) * 337(3) * 92737(5) * 649657(6) * 1 Temps en seconde(s) : 0.046332
M_64 = 2^64-1 = 18446744073709551615(20) =
3(1) * 5(1) * 17(2) * 257(3) * 641(3) * 65537(5) * 6700417(7) * 1 Temps en seconde(s) : 0.071602
M_65 = 2^65-1 = 36893488147419103231(20) =
31(2) * 8191(4) * 145295143558111(15) * 1 Temps en seconde(s) : 0.114911
M_66 = 2^66-1 = 73786976294838206463(20) =
3(1) * 3(1) * 7(1) * 23(2) * 67(2) * 89(2) * 683(3) * 20857(5) * 599479(6) * 1 Temps en seconde(s) : 0.042356
M_67 = 2^67-1 = 147573952589676412927(21) =
193707721(9) * 761838257287(12) * 1 Temps en seconde(s) : 5.206143
M_68 = 2^68-1 = 295147905179352825855(21) =
3(1) * 5(1) * 137(3) * 953(3) * 131071(6) * 43691(5) * 26317(5) * Temps en seconde(s) : 0.077998
M_69 = 2^69-1 = 590295810358705651711(21) =
7(1) * 47(2) * 178481(6) * 10052678938039(14) * 1 Temps en seconde(s) : 0.126579
M_70 = 2^70-1 = 1180591620717411303423(22) =
3(1) * 11(2) * 31(2) * 43(2) * 71(2) * 127(3) * 281(3) * 86171(5) * 122921(6) * 1 Temps en seconde(s) : 0.048207
M_71 = 2^71-1 = 2361183241434822606847(22) =
228479(6) * 48544121(8) * 212885833(9) * 1 Temps en seconde(s) : 0.441938
M_72 = 2^72-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 en seconde(s) : 0.012349
M_73 = 2^73-1 = 9444732965739290427391(22) =
439(3) * 2298041(7) * 9361973132609(13) * 1 Temps en seconde(s) : 0.169009
M_74 = 2^74-1 = 18889465931478580854783(23) =
3(1) * 223(3) * 1777(4) * 25781083(8) * 616318177(9) * 1 Temps en seconde(s) : 1.688764
M_75 = 2^75-1 = 37778931862957161709567(23) =
7(1) * 31(2) * 151(3) * 601(3) * 1801(4) * 100801(6) * 10567201(8) * 1 Temps en seconde(s) : 0.061874
M_76 = 2^76-1 = 75557863725914323419135(23) =
3(1) * 5(1) * 229(3) * 457(3) * 525313(6) * 524287(6) * 174763(6) * 1 Temps en seconde(s) : 0.145446
M_77 = 2^77-1 = 151115727451828646838271(24) =
23(2) * 89(2) * 127(3) * 581283643249112959(18) * 1 Temps en seconde(s) : 0.154349
M_78 = 2^78-1 = 302231454903657293676543(24) =
3(1) * 3(1) * 7(1) * 79(2) * 2731(4) * 8191(4) * 121369(6) * 22366891(8) * 1 Temps en seconde(s) : 0.117375
M_79 = 2^79-1 = 604462909807314587353087(24) =
2687(4) * 202029703(9) * 1113491139767(13) * 1 Temps en seconde(s) : 2.256905
M_80 = 2^80-1 = 1208925819614629174706175(25) =
3(1) * 5(1) * 5(1) * 11(2) * 17(2) * 31(2) * 41(2) * 257(3) * 61681(5) * 4278255361(10) * 1 Temps en seconde(s) : 0.066193
M_81 = 2^81-1 = 2417851639229258349412351(25) =
7(1) * 73(2) * 2593(4) * 71119(5) * 262657(6) * 97685839(8) * 1 Temps en seconde(s) : 0.165829
M_82 = 2^82-1 = 4835703278458516698824703(25) =
3(1) * 83(2) * 13367(5) * 164511353(9) * 8831418697(10) * 1 Temps en seconde(s) : 0.626556
M_83 = 2^83-1 = 9671406556917033397649407(25) =
167(3) * 57912614113275649087721(23) * 1 Temps en seconde(s) : 0.293461
M_84 = 2^84-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 en seconde(s) : 0.031094
M_85 = 2^85-1 = 38685626227668133590597631(26) =
31(2) * 131071(6) * 9520972806333758431(19) * 1 Temps en seconde(s) : 0.229431
M_86 = 2^86-1 = 77371252455336267181195263(26) =
3(1) * 431(3) * 9719(4) * 2099863(7) * 2932031007403(13) * 1 Temps en seconde(s) : 0.377058
M_87 = 2^87-1 = 154742504910672534362390527(27) =
7(1) * 233(3) * 1103(4) * 2089(4) * 4177(4) * 9857737155463(13) * 1 Temps en seconde(s) : 0.115468
M_88 = 2^88-1 = 309485009821345068724781055(27) =
3(1) * 5(1) * 17(2) * 23(2) * 89(2) * 353(3) * 397(3) * 683(3) * 2113(4) * 2931542417(10) * 1 Temps en seconde(s) : 0.055248
M_89 = 2^89-1 = 618970019642690137449562111(27) =
618970019642690137449562111(27) * 1 PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER Temps en seconde(s) : 1.110623
M_90 = 2^90-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) * 1 Temps en seconde(s) : 0.051574
M_91 = 2^91-1 = 2475880078570760549798248447(28) =
127(3) * 911(3) * 8191(4) * 112901153(9) * 23140471537(11) * 1 Temps en seconde(s) : 2.328416
M_92 = 2^92-1 = 4951760157141521099596496895(28) =
3(1) * 5(1) * 47(2) * 277(3) * 1013(4) * 1657(4) * 178481(6) * 30269(5) * 2796203(7) * 1 Temps en seconde(s) : 0.101921
M_93 = 2^93-1 = 9903520314283042199192993791(28) =
7(1) * 2147483647(10) * 658812288653553079(18) * 1 Temps en seconde(s) : 14.295108
M_94 = 2^94-1 = 19807040628566084398385987583(29) =
3(1) * 283(3) * 2351(4) * 4513(4) * 13264529(8) * 165768537521(12) * 1 Temps en seconde(s) : 0.579194
M_95 = 2^95-1 = 39614081257132168796771975167(29) =
31(2) * 191(3) * 524287(6) * 420778751(9) * 30327152671(11) * 1 Temps en seconde(s) : 2.670889
M_96 = 2^96-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) * 1 Temps en seconde(s) : 0.062759
M_97 = 2^97-1 = 158456325028528675187087900671(30) =
11447(5) * 13842607235828485645766393(26) * 1 Temps en seconde(s) : 0.441701
M_98 = 2^98-1 = 316912650057057350374175801343(30) =
3(1) * 43(2) * 127(3) * 4363953127297(13) * 4432676798593(13) * 1 Temps en seconde(s) : 109.166679
M_99 = 2^99-1 = 633825300114114700748351602687(30) =
7(1) * 23(2) * 73(2) * 89(2) * 199(3) * 153649(6) * 599479(6) * 33057806959(11) * 1 Temps en seconde(s) : 0.228902
M_100 = 2^100-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) * 1 Temps en seconde(s) : 0.055150
M_101 = 2^101-1 = 2535301200456458802993406410751(31) =
7432339208719(13) * 341117531003194129(18) * 1 Temps en seconde(s) : 339.596614
M_102 = 2^102-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) * 1 Temps en seconde(s) : 0.109578
M_103 = 2^103-1 = 10141204801825835211973625643007(32) =
2550183799(10) * 3976656429941438590393(22) * 1 Temps en seconde(s) : 14.061908
M_104 = 2^104-1 = 20282409603651670423947251286015(32) =
3(1) * 5(1) * 17(2) * 53(2) * 157(3) * 1613(4) * 2731(4) * 8191(4) * 858001(6) * 308761441(9) * 1 Temps en seconde(s) : 0.217423
M_105 = 2^105-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) * 1 Temps en seconde(s) : 0.116471
M_106 = 2^106-1 = 81129638414606681695789005144063(32) =
3(1) * 107(3) * 6361(4) * 69431(5) * 20394401(8) * 28059810762433(14) * 1 Temps en seconde(s) : 1.452694
M_107 = 2^107-1 = 162259276829213363391578010288127(33) =
162259276829213363391578010288127(33) * 1 PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER Temps en seconde(s) : 1.910127
M_108 = 2^108-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 en seconde(s) : 0.273271
M_109 = 2^109-1 = 649037107316853453566312041152511(33) =
745988807(9) * 870035986098720987332873(24) * 1 Temps en seconde(s) : 10.680712
M_110 = 2^110-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) * 1 Temps en seconde(s) : 0.114724
M_111 = 2^111-1 = 2596148429267413814265248164610047(34) =
7(1) * 223(3) * 321679(6) * 26295457(8) * 616318177(9) * 319020217(9) * 1 Temps en seconde(s) : 2.167669
M_112 = 2^112-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) * 1 Temps en seconde(s) : 0.577667
M_113 = 2^113-1 = 10384593717069655257060992658440191(35) =
3391(4) * 65993(5) * 23279(5) * 1868569(7) * 1066818132868207(16) * 1 Temps en seconde(s) : 0.453087
M_114 = 2^114-1 = 20769187434139310514121985316880383(35) =
3(1) * 3(1) * 7(1) * 571(3) * 32377(5) * 174763(6) * 1212847(7) * 524287(6) * 160465489(9) * 1 Temps en seconde(s) : 0.476220
M_115 = 2^115-1 = 41538374868278621028243970633760767(35) =
31(2) * 47(2) * 14951(5) * 4036961(7) * 178481(6) * 2646507710984041(16) * 1 Temps en seconde(s) : 0.410467
M_116 = 2^116-1 = 83076749736557242056487941267521535(35) =
3(1) * 5(1) * 59(2) * 233(3) * 1103(4) * 2089(4) * 3033169(7) * 107367629(9) * 536903681(9) * 1 Temps en seconde(s) : 1.224905
M_117 = 2^117-1 = 166153499473114484112975882535043071(36) =
7(1) * 73(2) * 79(2) * 937(3) * 8191(4) * 6553(4) * 121369(6) * 86113(5) * 7830118297(10) * 1 Temps en seconde(s) : 0.234257
M_118 = 2^118-1 = 332306998946228968225951765070086143(36) =
3(1) * 2833(4) * 37171(5) * 179951(6) * 1824726041(10) * 3203431780337(13) * 1 Temps en seconde(s) : 3.958981
M_119 = 2^119-1 = 664613997892457936451903530140172287(36) =
127(3) * 239(3) * 131071(6) * 20231(5) * 62983048367(11) * 131105292137(12) * 1 Temps en seconde(s) : 83.686294
M_120 = 2^120-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) * 1 Temps en seconde(s) : 0.146708
M_121 = 2^121-1 = 2658455991569831745807614120560689151(37) =
23(2) * 89(2) * 727(3) * 1786393878363164227858270210279(31) * 1 Temps en seconde(s) : 0.700558
M_123 = 2^123-1 = 10633823966279326983230456482242756607(38) =
7(1) * 13367(5) * 3887047(7) * 164511353(9) * 177722253954175633(18) * 1 Temps en seconde(s) : 1.523651
M_124 = 2^124-1 = 21267647932558653966460912964485513215(38) =
3(1) * 5(1) * 5581(4) * 49477(5) * 8681(4) * 384773(6) * 715827883(9) * 2147483647(10) * 1 Temps en seconde(s) : 1.650659
M_125 = 2^125-1 = 42535295865117307932921825928971026431(38) =
31(2) * 601(3) * 1801(4) * 269089806001(12) * 4710883168879506001(19) * 1 Temps en seconde(s) : 134.247035
M_126 = 2^126-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) * 1 Temps en seconde(s) : 0.351213
M_127 = 2^127-1 = 170141183460469231731687303715884105727(39) =
170141183460469231731687303715884105727(39) * 1 PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER PREMIER Temps en seconde(s) : 3.194471
M_128 = 2^128-1 = 340282366920938463463374607431768211455(39) =
3(1) * 5(1) * 17(2) * 257(3) * 641(3) * 65537(5) * 274177(6) * 6700417(7) * 67280421310721(14) * 1 Temps en seconde(s) : 0.818332
M_129 = 2^129-1 = 680564733841876926926749214863536422911(39) =
7(1) * 431(3) * 9719(4) * 2099863(7) * 11053036065049294753459639(26) * 1 Temps en seconde(s) : 0.757458
M_130 = 2^130-1 = 1361129467683753853853498429727072845823(40) =
3(1) * 11(2) * 31(2) * 131(3) * 2731(4) * 8191(4) * 409891(6) * 7623851(7) * 145295143558111(15) * 1 Temps en seconde(s) : 0.963254
M_131 = 2^131-1 = 2722258935367507707706996859454145691647(40) =
263(3) * 10350794431055162386718619237468234569(38) * 1 Temps en seconde(s) : 1.214412
M_132 = 2^132-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) * 1 Temps en seconde(s) : 0.289144
M_133 = 2^133-1 = 10889035741470030830827987437816582766591(41) =
127(3) * 524287(6) * 163537220852725398851434325720959(33) * 1 Temps en seconde(s) : 1.313349
M_134 = 2^134-1 = 21778071482940061661655974875633165533183(41) =
3(1) * 7327657(7) * 193707721(9) * 761838257287(12) * 6713103182899(13) * 1 Temps en seconde(s) : 111.577564
M_135 = 2^135-1 = 43556142965880123323311949751266331066367(41) =
7(1) * 31(2) * 73(2) * 151(3) * 271(3) * 631(3) * 23311(5) * 348031(6) * 262657(6) * 49971617830801(14) * 1 Temps en seconde(s) : 0.361143
M_136 = 2^136-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) * 1 Temps en seconde(s) : 0.423485
M_138 = 2^138-1 = 348449143727040986586495598010130648530943(42) =
3(1) * 3(1) * 7(1) * 47(2) * 139(3) * 178481(6) * 2796203(7) * 168749965921(12) * 10052678938039(14) * 1 Temps en seconde(s) : 28.462524
M_139 = 2^139-1 = 696898287454081973172991196020261297061887(42) =
5625767248687(13) * 123876132205208335762278423601(30) * 1 Temps en seconde(s) : 2058.215868
M_140 = 2^140-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) * 1 Temps en seconde(s) : 0.345962
M_141 = 2^141-1 = 2787593149816327892691964784081045188247551(43) =
7(1) * 2351(4) * 4513(4) * 13264529(8) * 4375578271(10) * 646675035253258729(18) * 1 Temps en seconde(s) : 16.111745
M_142 = 2^142-1 = 5575186299632655785383929568162090376495103(43) =
3(1) * 228479(6) * 212885833(9) * 56409643(8) * 48544121(8) * 13952598148481(14) * 1 Temps en seconde(s) : 3.720195
M_143 = 2^143-1 = 11150372599265311570767859136324180752990207(44) =
23(2) * 89(2) * 8191(4) * 724153(6) * 158822951431(12) * 5782172113400990737(19) * 1 Temps en seconde(s) : 66.241051
M_144 = 2^144-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) * 1 Temps en seconde(s) : 0.154265
M_145 = 2^145-1 = 44601490397061246283071436545296723011960831(44) =
31(2) * 233(3) * 1103(4) * 2089(4) * 2679895157783862814690027494144991(34) * 1 Temps en seconde(s) : 0.936695
M_146 = 2^146-1 = 89202980794122492566142873090593446023921663(44) =
3(1) * 439(3) * 1753(4) * 2298041(7) * 9361973132609(13) * 1795918038741070627(19) * 1 Temps en seconde(s) : 1148.264036
M_147 = 2^147-1 = 178405961588244985132285746181186892047843327(45) =
7(1) * 7(1) * 7(1) * 127(3) * 337(3) * 4432676798593(13) * 2741672362528725535068727(25) * 1 Temps en seconde(s) : 482.217768
M_148 = 2^148-1 = 356811923176489970264571492362373784095686655(45) =
3(1) * 5(1) * 149(3) * 223(3) * 593(3) * 1777(4) * 25781083(8) * 184481113(9) * 231769777(9) * 616318177(9) * 1 Temps en seconde(s) : 3.468503
M_150 = 2^150-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) * 1 Temps en seconde(s) : 0.870632
M_151 = 2^151-1 = 2854495385411919762116571938898990272765493247(46) =
18121(5) * 165799(6) * 55871(5) * 2332951(7) * 7289088383388253664437433(25) * 1 Temps en seconde(s) : 1.759978
M_152 = 2^152-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) * 1 Temps en seconde(s) : 0.663364
M_153 = 2^153-1 = 11417981541647679048466287755595961091061972991(47) =
7(1) * 73(2) * 103(3) * 919(3) * 2143(4) * 11119(5) * 131071(6) * 75582488424179347083438319(26) * 1 Temps en seconde(s) : 0.660849
M_154 = 2^154-1 = 22835963083295358096932575511191922182123945983(47) =
3(1) * 23(2) * 43(2) * 89(2) * 127(3) * 617(3) * 683(3) * 78233(5) * 35532364099(11) * 581283643249112959(18) * 1 Temps en seconde(s) : 58.571867
M_155 = 2^155-1 = 45671926166590716193865151022383844364247891967(47) =
31(2) * 31(2) * 311(3) * 11471(5) * 73471(5) * 4649919401(10) * 2147483647(10) * 18158209813151(14) * 1 Temps en seconde(s) : 14.068695
M_156 = 2^156-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) * 1 Temps en seconde(s) : 0.211030
M_157 = 2^157-1 = 182687704666362864775460604089535377456991567871(48) =
852133201(9) * 60726444167(11) * 1654058017289(13) * 2134387368610417(16) * 1 Temps en seconde(s) : 428.819124
M_158 = 2^158-1 = 365375409332725729550921208179070754913983135743(48) =
3(1) * 2687(4) * 202029703(9) * 1113491139767(13) * 201487636602438195784363(24) * 1 Temps en seconde(s) : 157.165306
M_159 = 2^159-1 = 730750818665451459101842416358141509827966271487(48) =
7(1) * 6679(4) * 69431(5) * 6361(4) * 540701761(9) * 13960201(8) * 20394401(8) * 229890275929(12) * 1 Temps en seconde(s) : 6.160888
M_160 = 2^160-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) * 1 Temps en seconde(s) : 13.576072
M_161 = 2^161-1 = 2923003274661805836407369665432566039311865085951(49) =
47(2) * 127(3) * 1289(4) * 178481(6) * 3188767(7) * 45076044553(11) * 14808607715315782481(20) * 1 Temps en seconde(s) : 129.128352
M_162 = 2^162-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) * 1 Temps en seconde(s) : 2.461799
M_163 = 2^163-1 = 11692013098647223345629478661730264157247460343807(50) =
150287(6) * 704161(6) * 110211473(9) * 27669118297(11) * 36230454570129675721(20) * 1 Temps en seconde(s) : 89.678750
M_164 = 2^164-1 = 23384026197294446691258957323460528314494920687615(50) =
3(1) * 5(1) * 83(2) * 13367(5) * 181549(6) * 10169(5) * 43249589(8) * 12112549(8) * 164511353(9) * 8831418697(10) * 1 Temps en seconde(s) : 4.880545
M_165 = 2^165-1 = 46768052394588893382517914646921056628989841375231(50) =
7(1) * 23(2) * 31(2) * 89(2) * 151(3) * 881(3) * 3191(4) * 599479(6) * 201961(6) * 2048568835297380486760231(25) * 1 Temps en seconde(s) : 0.943280
M_166 = 2^166-1 = 93536104789177786765035829293842113257979682750463(50) =
3(1) * 167(3) * 499(3) * 1163(4) * 2657(4) * 155377(6) * 13455809771(11) * 57912614113275649087721(23) * 1 Temps en seconde(s) : 96.330702
M_167 = 2^167-1 = 187072209578355573530071658587684226515959365500927(51) =
2349023(7) * 79638304766856507377778616296087448490695649(44) * 1 Temps en seconde(s) : 3.242270
M_168 = 2^168-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) * 1 Temps en seconde(s) : 1.213377
M_169 = 2^169-1 = 748288838313422294120286634350736906063837462003711(51) =
4057(4) * 8191(4) * 6740339310641(13) * 3340762283952395329506327023033(31) * 1 Temps en seconde(s) : 2527.257952