Before you start... - Page 4

KyleAskine · 2012-07-25, 22:57

I just want to say that I am interested.

However I can bring nothing to the project other than buying hardware to do whatever you guys tell it to do :)

debrouxl · 2012-07-26, 05:54

The server used for RSALS is ancient, and costs a fair bit of money to squalyl. NFS@Home has a better server and more users, it makes sense to merge RSALS into NFS@Home

Greg Childers, squalyl and I, (Cc William Lipp, the main provider of numbers for about two years, I recently gave a breather to OddPerfect because RSALS had emptied the queue of OddPerfect/Brent/Cyclotomic a^n-1 numbers ready for NFS), have already discussed the possibility several months ago, but we couldn't do it at the time.

jasonp · 2012-07-26, 11:28

To correct a previous post about CADO-NFS, the code was mostly written by full-time faculty, plus contributions from their students. Paul reports that they do accept outside contributions as long as they are licensed as LGPL; Shi Bai's polyselect code is an example of an outside contribution.

Also, the authors are gearing up to factor RSA896, and have started polynomial selection already. I think offers to collaborate on RSA896 would be well received...

bai · 2012-07-26, 11:36

Quote:

Paul reports that they do accept outside contributions as long as they are licensed as LGPL

And here are some ways to make suggestions/contributions. The preferred way is to send/discuss them to/on the cado-nfs-discuss list here. This is perhaps the most efficient way as every CADO-NFS developers can see them. Applying patches, or opening developer accounts, can be done for people who suggest nice additions. Direct e-mail also works, though (still) mailing list has some benefits such as its contents being archived

bai · 2012-07-26, 12:16

Quote:

Originally Posted by debrouxl

Should stage 1 and stage 2 of polynomial selection be separated ? I mean, collecting all stage 1 hits, then keeping several hundreds / thousands / dozens of thousands of the best hits, and run the full stage 2 (root sieve, etc.) on these hits separately.
This way, if the polynomial selection algorithms / parameters are tuned as a result of post-processing the first dozens of core-years, we could boil the best stage 1 hits multiple times.

I think this is a matter of trade-off between the speed and the approximation level of the score function. Perhaps similar to jasonp's, I prefer to only do size-optimization for a few top (in terms of a rough-but-fast score function) raw polynomials and only do root optimization for a few top (in terms of a finer-but-slower score function) size-optimized polynomial.

Dubslow · 2012-07-26, 22:39

Well, then it seems to me there's a clear path forward.

1) As jasonp has already sort-of volunteered to do, we can use slightly modified Msieve poly-select Stage 1 (plus a tiny part of Stage 2, IIUC) in tandem with NFS@Home. We can then take the top few polys from that and run a proper Stage 2 on those candidates by coordinating here (like a Team Sieve, except poly stage 2).

2) It's likely that by the time we've spent enough time selecting, RSA-896 will have been factored by Zimmermann et. al. Presumably, RSA-1024 is in their sights as well, so any development on the siever in the next few years should make it useable to sieve RSA-1024. Perhaps Messrs. Bai or Kruppa could comment on the siever? To this end, I believe that GGNFS should be considered EOL and siever developers should move to CADO.

3) NFS@Home/Zimmermann et. al./this forum should be, between the three groups, more than enough to sieve RSA-1024 is a reasonable amount of time.

4) jasonp, I'm not sure the state of Msieve's filtering/LA, but even if you can't upgrade those in the necessary time, CADO could probably handle it by then. Of course we'd need a huge cluster for the LA, but given the importance of factoring RSA-1024, that should be at least doable.

5) Factors!

A) 1 yr for poly select
B) 2-3 yrs for sieving
C) 1 yr LA

Optimistic goal: End of 2016. Less optimistic goal: end of 2018. Before 2020 is certainly well within the collective capabilities of everyone mentioned.

PS Does CADO use GGNFS' poly/relation format, or one of its own?

debrouxl · 2012-07-27, 10:42

2016 seems optimistic, at least to me

IIUC the orders of magnitude, as RSA-1024 is deemed about a thousand times harder than RSA-768 is, we're talking about something between 100K and 1M core-years...
Polynomial selection and sieving, which can be divided in almost arbitrarily small chunks and spread all over the world "almost effortlessly" thanks to BOINC, are not that troublesome, even though sieving RSA-1024 will require huge amounts of RAM per core, and thereby reduce the set of computers a lot.
The real issue, the massive pain, is the fantastically huge LA job, on a grid of clusters, after collecting SAN-class amounts of data.

And BTW, the RSA-768 paper indicated, if memory serves me, something along the lines of "future larger efforts of that sort would benefit from full-time professional supervision". Before starting sieving on a large scale, I think that the issue of which organizations will pay several full-time sysadmin positions for years needs to be resolved

Xyzzy · 2012-07-27, 13:30

All of the super mods had their pay doubled earlier this year.

Just sayin'

jasonp · 2012-07-27, 14:32

Dubslow, it's a little early to want a schedule from me; I have a day job for that. Suffice it to say that the current code is utterly inadequate (as in by a factor of 100) for any postprocessing task of this magnitude.

Debrouxl, if you want I can give you commit access to the Msieve SVN repository if you want to add some kind of BOINC support. The priority on the rest of the changes for effective distributed poly selection will increase if I see a grid waiting on them. I'd prefer we start on RSA896 as a test to get things up and running, that way the computation will be useful to Paul's group.

One year is much too long for polynomial selection; you want it to take at most 5% of the total time, so budget 3 wall-clock months for it.

Dubslow · 2012-07-27, 15:18

Quote:

Originally Posted by jasonp

Dubslow, it's a little early to want a schedule from me; I have a day job for that. Suffice it to say that the current code is utterly inadequate (as in by a factor of 100) for any postprocessing task of this magnitude.

It'll be years before that's an issue.

Quote:

Originally Posted by jasonp

Debrouxl, if you want I can give you commit access to the Msieve SVN repository if you want to add some kind of BOINC support. The priority on the rest of the changes for effective distributed poly selection will increase if I see a grid waiting on them. I'd prefer we start on RSA896 as a test to get things up and running, that way the computation will be useful to Paul's group.

Neat! I may or may not be useful in this regard.

Quote:

Originally Posted by jasonp

One year is much too long for polynomial selection; you want it to take at most 5% of the total time, so budget 3 wall-clock months for it.

Neat!

debrouxl · 2012-07-28, 05:58

Quote:

Debrouxl, if you want I can give you commit access to the Msieve SVN repository if you want to add some kind of BOINC support.

I appreciate the trust, but I strongly doubt I have either the knowledge of the msieve code base, or the time, to add some kind of BOINC support

In the short term, RSALS needs either switching to another server and performing maintenance (because the current server is expensive), or fully merging into NFS@Home (and benefiting from 64-bit and MacOS X sievers) then shutting down...

2012-07-26, 22:39	#39
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts	Well, then it seems to me there's a clear path forward. 1) As jasonp has already sort-of volunteered to do, we can use slightly modified Msieve poly-select Stage 1 (plus a tiny part of Stage 2, IIUC) in tandem with NFS@Home. We can then take the top few polys from that and run a proper Stage 2 on those candidates by coordinating here (like a Team Sieve, except poly stage 2). 2) It's likely that by the time we've spent enough time selecting, RSA-896 will have been factored by Zimmermann et. al. Presumably, RSA-1024 is in their sights as well, so any development on the siever in the next few years should make it useable to sieve RSA-1024. Perhaps Messrs. Bai or Kruppa could comment on the siever? To this end, I believe that GGNFS should be considered EOL and siever developers should move to CADO. 3) NFS@Home/Zimmermann et. al./this forum should be, between the three groups, more than enough to sieve RSA-1024 is a reasonable amount of time. 4) jasonp, I'm not sure the state of Msieve's filtering/LA, but even if you can't upgrade those in the necessary time, CADO could probably handle it by then. Of course we'd need a huge cluster for the LA, but given the importance of factoring RSA-1024, that should be at least doable. 5) Factors! A) 1 yr for poly select B) 2-3 yrs for sieving C) 1 yr LA Optimistic goal: End of 2016. Less optimistic goal: end of 2018. Before 2020 is certainly well within the collective capabilities of everyone mentioned. PS Does CADO use GGNFS' poly/relation format, or one of its own? Last fiddled with by Dubslow on 2012-07-26 at 22:43

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Where should I start?	christian_	Information & Answers	9	2016-01-22 19:28
Where to start	Jellyfish420	Homework Help	46	2013-02-06 13:51
How to start?	Thomas11	Lone Mersenne Hunters	29	2008-12-21 13:47
how to start with P-1?	ValerieVonck	Marin's Mersenne-aries	8	2006-04-29 22:21
How to start?	OmbooHankvald	Factoring	15	2005-09-03 13:42

2012-07-25, 22:57	#34
KyleAskine Oct 2011 Maryland 2×5×29 Posts	I just want to say that I am interested. However I can bring nothing to the project other than buying hardware to do whatever you guys tell it to do :)

2012-07-26, 05:54	#35
debrouxl Sep 2009 11×89 Posts	The server used for RSALS is ancient, and costs a fair bit of money to squalyl. NFS@Home has a better server and more users, it makes sense to merge RSALS into NFS@Home Greg Childers, squalyl and I, (Cc William Lipp, the main provider of numbers for about two years, I recently gave a breather to OddPerfect because RSALS had emptied the queue of OddPerfect/Brent/Cyclotomic a^n-1 numbers ready for NFS), have already discussed the possibility several months ago, but we couldn't do it at the time.

2012-07-26, 11:28	#36
jasonp Tribal Bullet Oct 2004 3²×5×79 Posts	To correct a previous post about CADO-NFS, the code was mostly written by full-time faculty, plus contributions from their students. Paul reports that they do accept outside contributions as long as they are licensed as LGPL; Shi Bai's polyselect code is an example of an outside contribution. Also, the authors are gearing up to factor RSA896, and have started polynomial selection already. I think offers to collaborate on RSA896 would be well received...

2012-07-27, 10:42	#40
debrouxl Sep 2009 11·89 Posts	2016 seems optimistic, at least to me IIUC the orders of magnitude, as RSA-1024 is deemed about a thousand times harder than RSA-768 is, we're talking about something between 100K and 1M core-years... Polynomial selection and sieving, which can be divided in almost arbitrarily small chunks and spread all over the world "almost effortlessly" thanks to BOINC, are not that troublesome, even though sieving RSA-1024 will require huge amounts of RAM per core, and thereby reduce the set of computers a lot. The real issue, the massive pain, is the fantastically huge LA job, on a grid of clusters, after collecting SAN-class amounts of data. And BTW, the RSA-768 paper indicated, if memory serves me, something along the lines of "future larger efforts of that sort would benefit from full-time professional supervision". Before starting sieving on a large scale, I think that the issue of which organizations will pay several full-time sysadmin positions for years needs to be resolved

2012-07-27, 13:30	#41
Xyzzy Aug 2002 2×7×13×47 Posts	All of the super mods had their pay doubled earlier this year. Just sayin'

2012-07-27, 14:32	#42
jasonp Tribal Bullet Oct 2004 3²·5·79 Posts	Dubslow, it's a little early to want a schedule from me; I have a day job for that. Suffice it to say that the current code is utterly inadequate (as in by a factor of 100) for any postprocessing task of this magnitude. Debrouxl, if you want I can give you commit access to the Msieve SVN repository if you want to add some kind of BOINC support. The priority on the rest of the changes for effective distributed poly selection will increase if I see a grid waiting on them. I'd prefer we start on RSA896 as a test to get things up and running, that way the computation will be useful to Paul's group. One year is much too long for polynomial selection; you want it to take at most 5% of the total time, so budget 3 wall-clock months for it.