20031202, 12:56  #1 
Bamboozled!
"ð’‰ºð’ŒŒð’‡·ð’†·ð’€"
May 2003
Down not across
11×17×59 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 primeindex 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^7571. 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 
20031208, 20:37  #2 
∂^{2}ω=0
Sep 2002
RepÃºblica de California
26634_{8} Posts 
Congratulations on the new latest factorization!
It's obvious that neither the p1 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 
20031208, 20:53  #3 
∂^{2}ω=0
Sep 2002
RepÃºblica de California
2^{2}·3·7·139 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 20031208 at 20:54 
20031208, 21:08  #4  
Jun 2003
The Texas Hill Country
10001000001_{2} Posts 
Quote:


20031208, 22:16  #5  
∂^{2}ω=0
Sep 2002
RepÃºblica de California
2^{2}×3×7×139 Posts 
Quote:


20031209, 10:00  #6  
Bamboozled!
"ð’‰ºð’ŒŒð’‡·ð’†·ð’€"
May 2003
Down not across
11·17·59 Posts 
Quote:
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^7571, 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 

20031209, 15:37  #7 
∂^{2}ω=0
Sep 2002
RepÃºblica de California
10110110011100_{2} Posts 
Thanks for the clarification, Paul  that was how I understood the SNFS algorithm to work.
And of course with the primeexponent Mersennes, algebraic factors aren't an issue. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Big factors  Jeff Gilchrist  Wagstaff PRP Search  10  20130407 11:07 
Mp: factors of p1 and p+1  paulunderwood  Miscellaneous Math  10  20130213 20:35 
Missing factors at the 'Known Factors' page  MatWurS530113  PrimeNet  11  20090121 19:08 
New factors on F12 or bug  jocelynl  Factoring  2  20041031 02:55 
New factors?  Yogi  Math  9  20041026 17:14 