mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   NFS@Home (https://www.mersenneforum.org/forumdisplay.php?f=98)
-   -   BOINC NFS sieving - NFS@Home (https://www.mersenneforum.org/showthread.php?t=12388)

frmky 2009-09-11 19:04

[QUOTE=R.D. Silverman;189463]
Does anyone envision it attempting (say) the RSA-768 effort that is
now underway?
[/QUOTE]

The big restriction with BOINC is that the application needs to run on commonly deployed hardware. Today, that [URL="http://infoworld.com/windows-pulse"]appears to be[/URL] a dual core computer with 2-3 GB of memory. I can specify that a work unit not be sent to a computer with less than X MB of memory, so in principle it [B]is[/B] feasible as long as the memory use of the siever can be kept in the Win32 limit of 3GB per process. Of course, though, I want to exercise the infrastructure and grow a userbase with more reasonable targets first. :smile:

frmky 2009-09-11 20:57

The first factors are in. 2,2214L factors as

87-digit prime factor:
650129030757448838848987009049036364296974617097033424890396170500076127717454884707697

104-digit prime factor:
11946827680341235646112762882603877501599655320760206302298918228497279186673314456312477897500132634593

Greg

debrouxl 2009-09-11 21:05

FWIW, for the 512-bit RSA keys of rsals, each WU (gnfs-lasieve4I14e, 32-bit) usually took less than 150 MB of RAM.

frmky: nice :smile:
How much raw CPU time for gnfs and for msieve ?

frmky 2009-09-11 21:23

[QUOTE=debrouxl;189535]
How much raw CPU time for gnfs and for msieve ?[/QUOTE]
The community contributed about 140 days of CPU time to the sieving. msieve took 2 days to do the filtering, linear algebra, and square roots. For reference, this was about as difficult as 492-bit RSA would be, so a bit easier than RSA-512.

The sieving for 5,353+ is nearly done. For that one, the community has contributed about 2 years of CPU time. For reference, that is about as difficult as 547-bit RSA would be.

fivemack 2009-09-11 23:38

[QUOTE=R.D. Silverman;189463]
However, I don't see NFS@HOME as being a leading edge research tool.
Does anyone envision it attempting (say) the RSA-768 effort that is
now underway?
[/QUOTE]

As I presume you're intending to point out, there are two hard parts of the RSA-768 effort: software development for the matrix-production step ([url]http://cado.gforge.inria.fr/workshop/slides/montgomery.pdf[/url] gives a decent idea of the problems involved, though with perhaps a bit much concentration on the square-root step which is likely to be practical using direct methods on the large shared-memory supercomputer that you'd need anyway for the matrix), and grantsmanship to get access to a machine big enough and fast enough (the slides mention a 256GB 64 x Power5 box at SARA and mention that that might not be enough) to solve the ~300M^2 matrix in reasonable time. If anyone can do that, the Lenstra-CADO-Montgomery-Aoki team can - it's pretty much all the people who've worked on serious-scale GNFS lined up in the same direction.

The sieving is however (as I've heard attributed, but not citably, to Churchill) a matter of applying increasingly great resources to a well-understood problem. [url]http://ludwig-sun1.unil.ch/~hstockin/crypto/[/url] has information about one of the grant requests for doing the sieving, on a grid;

[quote]
Resources required per job:

* x86 or x86-64 processor (preferred)
* 1GB RAM, 600MB swap, 450MB disk
* Operating system: Linux (preferred), FreeBSD, Windows
* Ownership: Jens Franke, Thorsten Kleinjung, Free Software Foundation, GPL v2, LGPL

Expected timelines: The expected timeline depends on the resources that would be available. We can start any moment. We expect that we need between 1500 and 2500 CPU years (depending on the type of processor used).
[/quote]

2500 CPU-years is eminently reasonable for a popular BOINC project, it would take a month or so for PrimeGrid as currently constituted.

Batalov 2009-09-12 00:11

[quote=frmky;189531]The first factors are in. 2,2214L [/quote]
Too easy, Greg!
Congratulations, great stuff!

R.D. Silverman 2009-09-12 02:49

[QUOTE=fivemack;189542]As I presume you're intending to point out, there are two hard parts of the RSA-768 effort: software development for the matrix-production step ([url]http://cado.gforge.inria.fr/workshop/slides/montgomery.pdf[/url] gives a decent idea of the problems involved, though with perhaps a bit much concentration on the square-root step which is likely to be practical using direct methods on the large shared-memory supercomputer that you'd need anyway for the matrix), and grantsmanship to get access to a machine big enough and fast enough .[/QUOTE]


The U.S. government gives access grants to large scale compute projects.
The grants are for the 80,000+ node (yes, 80,000 CPUs) supercomputer
at Oakridge. I suspect that this machine is big enough/fast enough.

frmky 2009-09-12 04:10

[QUOTE=R.D. Silverman;189559]The U.S. government gives access grants to large scale compute projects.
[/QUOTE]
I have had one small but successful NSF Teragrid grant. I certainly wouldn't be opposed to going for another. :smile:

10metreh 2009-09-12 06:40

Could you quickly (a few hours) put an end to the c141 that is blocking aliquot sequence 4788? No-one seems to want to find a poly.

henryzz 2009-09-12 06:44

[quote=10metreh;189570]Could you quickly (a few hours) put an end to the c141 that is blocking aliquot sequence 4788? No-one seems to want to find a poly.[/quote]
i was planning to do the poly search but i got distracted by my birthday
TBH it would take me a while to do a large enough poly search
if anyone fancies doing it quickly feel free

XYYXF 2009-09-12 14:21

[QUOTE=debrouxl;189277]Batalov: yeah, I'll easily admit that I haven't picked a lot of theory :redface:
Someone suggested a 149-digit xyyxf number at
[url]http://www.unitedti.org/index.php?showtopic=8888&view=findpost&p=135938[/url] (and later posts), so I just tried several other 150-160 digit numbers from the "wanted" list of that project, and wanted to feed them to the rsals grid so as to prevent starvation (and therefore people detaching, weakening the grid).[/QUOTE]Hey people,

since I'm the coordinator of this project, please let me know if some new results appear :-)


All times are UTC. The time now is 12:50.

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