Wednesday, July 28, 2004

More fun with factorization

Using the tables at the Cunningham Project, one can factor M1279-1, where M1279=2^1279-1 is the 15th Mersenne Prime.

? M1279=2^1279-1;
? isprime(M1279)
%50 = 1
? print(factor((M1279-1)/(a*b*c*d*e*f*z*y*x*w*v)))
[2, 1; 3, 3; 7, 1; 19, 1; 73, 1; 1279, 1; 5113, 1; 17467, 1; 66457, 1; 102241, 1; 228479, 1; 48544121, 1; 56409643, 1; 212885833, 1]

? [a,b,c,d,e,f,v,w,x,y,z]
%51 = [ 28435302301212461494420074814087, 1329628131546931497103420134367, 84462210560148142953097, 4205268574191396793, 2849881972114740679, 581211581673454706767349073071710126567, 4856686864845032704799031665030860909072721381346530375665783654750574941128789505171, 13952598148481, 203525545766301306933226271929, 69779014917427, 8970948423964301024591994817 ]

The large factor (v=48566...171) factors v-1 = 32670537017659 * 30745017857595820376423803727 *372195264810848171907297121582928687 * smaller_factors

No such luck with the next Mersenne prime M2203, where we get stuck with C217 factor of 2^1101+1.

With M2281, we again get pretty lucky to obtain a complete factorization of M2281-1:

2 * 3 * 3 * 5 * 5 * 7 * 11 * 13 * 17 * 31 * 41 * 61 * 151 * 191 * 229 * 241 * 331 * 457 * 571 * 761 * 1217 * 1321 * 2281 * 4561 * 32377 * 54721 * 61681 * 90289 * 131101 * 148961 * 160969 * 174763 * 185821 * 247381 * 524287 * 525313 * 1101811 * 1212847 * 160465489 * 420778751 * 3996146881 * 4562284561 * 9036489073 * 30327152671 * 275415303169 * 24517014940753 * 1457772869697961 * 276696631250953741 * 2416923620660807201 * 3011347479614249131 * 1491477035689218775711 * P23 * 25349242986637720573561 * 29034057164920993379000074993 * P29 * 3435950210316335724157758000789490561 * P38 * P51 * P170

[P23= 23480412082098913326841 ]
[P29= 64326196787727903551977150861 ]
[P38= 15653990705896313547269237220041169361 ]
[P51= 153787279330237476887106331233239525756635010497681 ]
[P170= 51049903050598156013062477654241640657829025002976204451060261008689478158715729745160924860467530309657376827104233308157772350164622158651187694109112727796663977157921 ]

using the automated cunningham factor calculator. Unfortunately P170-1 does not factor easily. It has small factors 2*2*2*2*2*3*5*19*23*41, nontrivial factors 57872616793 and 271819582242082307 and a left over 135 digit composite 377341463808543326355616919094375236137049329420738596924600642749151360224737826546584980131240115699417216932276614698618252847357337.

It is fun to google search some of these numbers to see who else has replicated these results.

No comments :