BOINC NFS sieving - RSALS

[debrouxl]

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

[R.D. Silverman]

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?

[squalyl]

Yes. that would be helpful.
Was any GNFS polynomial search started?

[R.D. Silverman]

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.

[debrouxl]

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

[fivemack]

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

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

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.

[fivemack]

These are done by me, by Bruce Dodson collaborating with me, and by MersenneForum regulars collaborating with me.Attachment 4132

[fivemack]

As above

[bdodson]

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

[fivemack]

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

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.

[fivemack]

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)

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