Factoriser des grands entiers

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 formefermat é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


webmaster - à propos - Copyright 2007-2016. Tous droits réservés.