mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > NFSNET Discussion

 
 
Thread Tools
Old 2003-12-02, 12:56   #1
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22×32×281 Posts
Smile 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
xilman is offline  
Old 2003-12-08, 20:37   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

263F16 Posts
Default

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
ewmayer is offline  
Old 2003-12-08, 20:53   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

979110 Posts
Default

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
ewmayer is offline  
Old 2003-12-08, 21:08   #4
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

20728 Posts
Default

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.
Wacky is offline  
Old 2003-12-08, 22:16   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,791 Posts
Default

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?
ewmayer is offline  
Old 2003-12-09, 10:00   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22·32·281 Posts
Default

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
xilman is offline  
Old 2003-12-09, 15:37   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

979110 Posts
Default

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.
ewmayer is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Big factors Jeff Gilchrist Wagstaff PRP Search 10 2013-04-07 11:07
Mp: factors of p-1 and p+1 paulunderwood Miscellaneous Math 10 2013-02-13 20:35
Missing factors at the 'Known Factors' page MatWur-S530113 PrimeNet 11 2009-01-21 19:08
New factors on F12 or bug jocelynl Factoring 2 2004-10-31 02:55
New factors? Yogi Math 9 2004-10-26 17:14

All times are UTC. The time now is 00:49.

Sat Oct 24 00:49:21 UTC 2020 up 43 days, 22 hrs, 0 users, load averages: 0.98, 1.25, 1.31

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.