mersenneforum.org BOINC NFS sieving - RSALS
 Register FAQ Search Today's Posts Mark Forums Read

 2009-09-15, 11:53 #1 debrouxl     Sep 2009 977 Posts BOINC NFS sieving - RSALS Hello everybody This post is for introducing a BOINC-based ( http://boinc.berkeley.edu/ ) project using the ggnfs siever. First of all, a bit of history: As you may already know, a 512-bit public RSA key used in the TI-83+ 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 TI-Z80 and TI-68k programming communities realized that factoring 512-bit (~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 512-bit 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...fs-lasieve4e.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 512-bit 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 150-160 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 gnfs-lasieve* 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 gnfs-lasieve4I* executables (this should be easy - done by frmky, it seems); * provide 64-bit ggnfs Linux and Windows binaries (partially done by frmky); * provide MacOS X x86 and x86-64 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 embed-everything executable that auto-detects 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
2009-09-15, 12:06   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by debrouxl Hello everybody This post is for introducing a BOINC-based ( http://boinc.berkeley.edu/ ) project using the ggnfs siever.
Of course there are some nice Cunningham numbers that are well
suited to GNFS. Would you like a list?

 2009-09-15, 13:00 #3 squalyl   Sep 2009 1002 Posts Yes. that would be helpful. Was any GNFS polynomial search started?
2009-09-15, 14:23   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by squalyl Yes. that would be helpful. Was any GNFS polynomial search started?
Here are some of them:

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.

 2009-09-15, 15:01 #5 debrouxl     Sep 2009 97710 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 ggnfs-BOINC 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 2009-09-15 at 15:47
 2009-09-15, 16:25 #6 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 23·797 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 and expecting the run to take about 4000 CPU-hours 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 and the sieving run took about 10000 CPU-hours. 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.
2009-09-15, 16:27   #7
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

23×797 Posts
GNFS runs

These are done by me, by Bruce Dodson collaborating with me, and by MersenneForum regulars collaborating with me.Attachment 4132
Attached Files
 gnfs-runs.gnumeric.gz (35.2 KB, 174 views)

Last fiddled with by fivemack on 2009-09-15 at 16:28

2009-09-15, 16:28   #8
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

637610 Posts
SNFS runs

As above
Attached Files
 snfs-runs.gnumeric.gz (19.9 KB, 146 views)

2009-09-15, 16:30   #9
bdodson

Jun 2005
lehigh.edu

102410 Posts

Quote:
 Originally Posted by R.D. Silverman Here are some of them: 12,266+ AFAIK, no poly [search] has been done on any of them.
This one's snfs, index divisible by 7. -bd

 2009-09-15, 16:50 #10 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 23×797 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 10kQ takes about 40 minutes and you'll need to do about the range 18M..40M) might also be interesting.
 2009-09-15, 16:56 #11 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 23·797 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 160-180 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

 Similar Threads Thread Thread Starter Forum Replies Last Post frmky NFS@Home 1828 2020-11-14 04:57 Unregistered Information & Answers 6 2010-09-21 03:31 BATKrikke Teams 2 2010-03-05 18:57 Xentar Sierpinski/Riesel Base 5 4 2009-04-25 10:26 masser Sierpinski/Riesel Base 5 1 2009-02-09 01:10

All times are UTC. The time now is 02:17.

Sun Dec 6 02:17:57 UTC 2020 up 2 days, 22:29, 0 users, load averages: 1.99, 1.99, 2.20