20090915, 11:53  #1 
Sep 2009
2·3·163 Posts 
BOINC NFS sieving  RSALS
Hello everybody
This post is for introducing a BOINCbased ( http://boinc.berkeley.edu/ ) project using the ggnfs siever. First of all, a bit of history: As you may already know, a 512bit public RSA key used in the TI83+ calculators was recently factored in less than 3 months of CPU time by a single desktop computer. See http://www.ticalc.org/archives/news/...45/145154.html . On that occasion, many people in the TIZ80 and TI68k programming communities realized that factoring 512bit (~154 or 155 digits) composite integers whose factors were bound to be large (and it turned out that they were: 75 to 79 digits) was MUCH easier than we thought... so we decided to give it a try with multiple computers. We started sieving another 512bit RSA key in a distributed manner. At first, people reserved ranges manually, but Godzil had the idea of making a BOINC project that would run the sieving phase. This way, we could leverage BOINC's capabilities for distributing Work Units, for checking the results... and have a potentially large number of participants, thanks to BOINC's easy install and attaching to a project. Therefore, a few days later, squalyl successfully ported to BOINC one of the ggnfs executables ( https://www.unsads.com/scm/svn/squal...fslasieve4e.c , guest / guest) , and we added the BOINC client as just another participant (manual reservation of ranges in a shared topic) on August 12th. Since then, the BOINC project was attached to by more than 500 computers totaling more than 1000 cores. Together, these computers sieved about 12.5 512bit integers in four weeks (including more than one day of server downtime), the remainder of the 13th integer being sieved manually. jasonp was somehow made aware of the effort, and suggested us to get in touch with the thriving factoring community over at mersenneforum: hence this post It was delayed for more than a week because squalyl is currently on holiday. Currently, some people have detached from the grid after the RSA numbers were factored. We're sieving seven 150160 digit xyyx numbers, we may try out other integer families. 3 are sieved with type: gnfs (1 completely factored) and 4 with type: snfs (thanks fivemack and XYYXF). The RSALS grid will run out of WUs very shortly, I have to try using msieve on the results produced by "type: snfs" sieving before filling in new WUs. As written above, the BOINC grid can happily cooperate with manual sieving. Below is our current wish/todo list for the BOINC project, the tools and the host. A significant part of that list probably belongs to a centralized place that can be used by all projects that would like to use gnfslasieve* for sieving whatever integers they feel like. * consolidate the quick porting to BOINC of the ggnfs executables (e.g. more graceful suspend & restart of a WU  done by frmky, it seems)  we know this is certainly a good place for finding help for this task ; * port to BOINC other gnfslasieve4I* executables (this should be easy  done by frmky, it seems); * provide 64bit ggnfs Linux and Windows binaries (partially done by frmky); * provide MacOS X x86 and x8664 binaries; * compress result data on the client side (with gzip, bzip2 or maybe xz) before sending it: very low additional CPU cost on the client, but divides the result footprint by more than two; * review/modify validator contributed by FloppusMaximus (for the RSA keys, the BOINC project used the bitwise comparison validator, on 2+ instances of the same WU... for the latest xyyxf numbers, we switched to a quorum of 1); * provide an embedeverything executable that autodetects the platform and uses the most optimized code the platform can handle (Pentium4, Core 2, AMD64, etc.): the current binaries use a least common denominator instruction set; * MacOS X PPC binaries (?); * a web interface to submit integers (with mandatory description) and to allow screening of the numbers (this may be unnecessary, if we settle on a particular ); * use multiple servers, e.g. one for the database and 1+ for results storage. Feel free to comment on the wish list and add new wishes 
20090915, 12:06  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·3·7·89 Posts 
Quote:
suited to GNFS. Would you like a list? 

20090915, 13:00  #3 
Sep 2009
2^{2} Posts 
Yes. that would be helpful.
Was any GNFS polynomial search started? 
20090915, 14:23  #4  
"Bob Silverman"
Nov 2003
North of Boston
1D34_{16} Posts 
Quote:
2,980+ 2,956+ 2,1040+ 2,1099+ 2,899 2,935 2,2074M 2,2098M 2,1714M 2,1754M 2,1910M 3,538+ 12,266+ 5,416+ 5,418+ 5,382+ 10,308+ 6,358+ 10,278+ 5,391 10,286+ 11,275 5,805L 7,721L 5,785L 5,430+ etc. AFAIK, no poly serach has been done on any of them. 

20090915, 15:01  #5 
Sep 2009
3D2_{16} Posts 
In the NFS@home thread, frmky wrote that he planned on doing mostly Cunningham composites. I guess we'll leave this family of integers to NFS@home, because there's little sense in having two ggnfsBOINC projects for the same family of numbers
Otherwise, thanks for the list. Could someone please give us an estimation of: * where's the split point for using either the 14e or 15e sievers (I've seen the rule of thumb "if there are more than 6000 or less than 2000, use another siever", but I don't know to how many digits that usually translates) ? * how many relations are necessary for 160+digit "type: gnfs" and "type: snfs" numbers (maybe there's a general rule of thumb) ? * how much time takes the sieving of 10K values of q for gnfs and snfs integers of various sizes (again, maybe there is a general rule of thumb such as "things become about n times slower each time p digits are added") That should definitely help us sizing the integers we want to tackle. Thanks in advance Last fiddled with by debrouxl on 20090915 at 15:47 
20090915, 16:25  #6 
(loop (#_fork))
Feb 2006
Cambridge, England
2·7·461 Posts 
I will give you some numbers, but it's really best to figure these out for yourself.
For an SNFS of difficulty 228, I'm using siever 14e and Code:
lpbr: 30 mfbr: 60 lpba: 30 mfba: 60 alim: 50000000 rlim: 50000000 alambda: 2.6 rlambda: 2.6 For a GNFS of 163 digits, bdodson and I used siever 15e and Code:
lpbr: 30 lpba: 30 mfbr: 60 mfba: 60 rlambda: 2.6 alambda: 2.6 alim: 80000000 rlim: 80000000 My next two postings will have attached (in gnumeric format; you can get gnumeric for Windows from http://projects.gnome.org/gnumeric/downloads.shtml) the spreadsheets describing pretty much all the GNFS and SNFS factorisations I've done; that's about the best idea I can give you of what sort of parameters work nicely. 
20090915, 16:27  #7 
(loop (#_fork))
Feb 2006
Cambridge, England
14466_{8} Posts 
GNFS runs
These are done by me, by Bruce Dodson collaborating with me, and by MersenneForum regulars collaborating with me.Attachment 4132
Last fiddled with by fivemack on 20090915 at 16:28 
20090915, 16:28  #8 
(loop (#_fork))
Feb 2006
Cambridge, England
2·7·461 Posts 
SNFS runs
As above

20090915, 16:30  #9 
Jun 2005
lehigh.edu
2^{10} Posts 

20090915, 16:50  #10 
(loop (#_fork))
Feb 2006
Cambridge, England
1100100110110_{2} Posts 
I think an interesting project for rsals as presently constituted would be to extend further the aliquot sequences that Zimmermann has been running (http://www.loria.fr/~zimmerma/records/aliquot.html)  this gives you a set of eight C140+ numbers on the go at any time.
If you want something immediate, XYYX 104^105+105^104 by SNFS (use 14e, sieve with r, polynomial is Code:
n: 1476751614801141705317174463336507013805741126786182830083806701472861935954782093161906034398577180964708724093457618440954780474984506432502287083845660046759647636037 type: snfs skew: 0.39 c5: 105 c0: 1 Y1: 2785962590401641140642702303409576416015625 Y0: 2278768068754756124569999328766699927240704 alim: 33554431 rlim: 33554431 lpbr: 29 lpba: 29 mfbr: 58 mfba: 58 alambda: 2.6 rlambda: 2.6 might also be interesting. 
20090915, 16:56  #11 
(loop (#_fork))
Feb 2006
Cambridge, England
14466_{8} Posts 
GNFSworthy Cunningham numbers
As far as I know there's been no polynomial selection done on any of these.
(lines are ID, GNFS difficulty, SNFS difficulty; filtered by 160180 digits and GNFS difficulty less than 0.6* SNFS difficulty so they're clearly better GNFS candidates) Code:
2,2074M 159.22 312.17 5,391 160.65 273.30 10,278+ 161.50 278.00 6,358+ 162.52 278.58 5,442+ 167.73 285.18 6,368+ 170.77 286.36 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
BOINC NFS sieving  NFS@Home  frmky  NFS@Home  1930  20220809 18:17 
BOINC  Unregistered  Information & Answers  6  20100921 03:31 
BOINC.BE  BATKrikke  Teams  2  20100305 18:57 
Boinc  Xentar  Sierpinski/Riesel Base 5  4  20090425 10:26 
BOINC?  masser  Sierpinski/Riesel Base 5  1  20090209 01:10 