mersenneforum.org The factors of M757
 Register FAQ Search Today's Posts Mark Forums Read

 2003-12-02, 12:56 #1 xilman Bamboozled!     "ð’‰ºð’ŒŒð’‡·ð’†·ð’€­" May 2003 Down not across 22×2,663 Posts The factors of M757 Less than an hour ago, this appeared in a window on my workstation: Original number had 213 digits: 13752482059206622184516110319504078523243712131392474512308817064826925562339964 32157638160851187604400926673771338223960482503058695991668529363734439720161301 88795692624533425489999025582244971978683298161118487 Probable prime factor 1 has 79 digits: 5722137022002067824248227975095857749151312827809388406962346253182128916964593 Probable prime factor 2 has 134 digits: 24033821640983508088736273403005965446689002356344332130565066643193813901119771 090424269412054543072714914742665677774247325292327559 Back on 31st August, the NFSNET clients changed over to working on the 2_757M project. 124 days later, we have the factors above. A full announcement will be made later this week, but here's an overview of what we did. The number 2,757- was chosen because it's both a Cunningham number and a prime-index Mersenne number. The composite cofactor had 213 digits but because we used SNFS and couldn't exploit the known factorization, we had to factor the full 228 digits of 2^757-1. The sieving phase began on 31st August and finished on 13th October, using 13745WU of sieving effort. The filtering and merging of the 76.7M relations began the same day and finished on 28th October with the production of a matrix with slightly over 7.522 million rows and columns. Linear algebra on that matrix took 32 days 16 hours total elapsed time, with 26d 11h recorded in the many log files along the way. The 6d 5h discrepancy is accounted for by time lost to crashes and to scheduled downtime on the cluster at Microsoft Research in Cambridge. The actual cpu time was about 7600 hours (i.e. 30 cpus at about 40% loading). We were fortunate in that the factors were found on the first dependency, which took 157 minutes on a 2.53GHz P4 machine. This was the hardest factorization yet completed by NFSNET, just pipping 10,227- which completed three months ago. The current project, 2,811-, is even harder but is still running along smoothly. As always, thanks are due to all the people who contributed their machine cycles and their enthusiasm. Further, we acknowledge the contribution made by CWI in providing us with their NFS code for us to use and to redistribute in a modified form. Paul
 2003-12-08, 20:37 #2 ewmayer ∂2ω=0     Sep 2002 RepÃºblica de California 265528 Posts Congratulations on the new latest factorization! It's obvious that neither the p-1 nor p+1 method could have found the p79, since: p79 - 1 = 2^4.13.757.1229897.54286614780461303.1380765008073205793.394201037959710813849206239443089 p79 + 1 = 2.3^2.19.47.7432993.2324637841.185510276424547.111057345764905462413172936544652769659794471
 2003-12-08, 20:53 #3 ewmayer ∂2ω=0     Sep 2002 RepÃºblica de California 2·5,813 Posts p.s.: To those who may not closely follow such factorizations, note that the above inout number in Paul's message is not 2^757 - 1, it's that number with the two easily found small factors (9815263 and 561595591) divided out. But - doesn't SNFS usually work on the undivided number, even if leaving the small factors in makes for a larger (but algebraically suitable for SNFS) form? Paul? Last fiddled with by ewmayer on 2003-12-08 at 20:54
2003-12-08, 21:08   #4
Wacky

Jun 2003
The Texas Hill Country

21018 Posts

Quote:
 Originally posted by ewmayer But - doesn't SNFS usually work on the undivided number, even if leaving the small factors in makes for a larger (but algebraically suitable for SNFS) form? Paul?
The polynomials are chosen on the basis of the simple form of the undivided number. However, all of the modular arithmetic is done on the basis of the smaller composite factor.

2003-12-08, 22:16   #5
ewmayer
2ω=0

Sep 2002
RepÃºblica de California

2×5,813 Posts

Quote:
 Originally posted by Wacky The polynomials are chosen on the basis of the simple form of the undivided number. However, all of the modular arithmetic is done on the basis of the smaller composite factor.
For numbers of special form like the Mersennes and Fermats, wouldn't it be faster to do modular arithmetic using the Crandall/Fagin DWTand the full number?

2003-12-09, 10:00   #6
xilman
Bamboozled!

"ð’‰ºð’ŒŒð’‡·ð’†·ð’€­"
May 2003
Down not across

22×2,663 Posts

Quote:
 Originally posted by ewmayer For numbers of special form like the Mersennes and Fermats, wouldn't it be faster to do modular arithmetic using the Crandall/Fagin DWTand the full number?
Yes but.

The but is that only a trivial amount of arithmetic is done modulo N. Virtually all the computation takes place in the siever where the limits are largely set by memory access speeds and, as a secondary consideration, single and double precision integer arithmetic.

To answer the original question: we were unable to exploit the factors of M757 and had to factor the full 2^757-1, apart from the entirely negligible speedup already noted.

Sometimes it's possible to exploit known factors. If more than a third or so of the number has been factored (from c200 to c130, for instance) it will usually be quicker to factor the small cofactor with GNFS than the entire number with SNFS. Sometimes algebraic factorizations can be exploited. For example, we would not factor 2^802+1 itself but factor (2^401 + 2^201 + 1) and (2^401 - 2^201 + 1) individually, since each of those quantities can be represented as a simple polynomial with a known root.

Paul

 2003-12-09, 15:37 #7 ewmayer ∂2ω=0     Sep 2002 RepÃºblica de California 2·5,813 Posts Thanks for the clarification, Paul - that was how I understood the SNFS algorithm to work. And of course with the prime-exponent Mersennes, algebraic factors aren't an issue.

 Similar Threads Thread Thread Starter Forum Replies Last Post Jeff Gilchrist Wagstaff PRP Search 10 2013-04-07 11:07 paulunderwood Miscellaneous Math 10 2013-02-13 20:35 MatWur-S530113 PrimeNet 11 2009-01-21 19:08 jocelynl Factoring 2 2004-10-31 02:55 Yogi Math 9 2004-10-26 17:14

All times are UTC. The time now is 14:14.

Thu Apr 22 14:14:34 UTC 2021 up 14 days, 8:55, 0 users, load averages: 1.95, 2.20, 2.40