Ideas for the future beyond just-keep-encrunching

[Dubslow]

If people really wanted a full on challenge.... one possible idea is attempting to try our collective hand at the multiple (S)NFS factory technique.

Considering the amount of data involved (not to mention the massive linear algebra involved), it may not necessarily be a good idea to numbers quite as large as the original paper, but I imagine there's some other Cunningham tables that have several holes with smaller size numbers compared to 2-?

Or is this a complete pipe dream? I'm not really sure.

[Dubslow]

Originally Posted by pinhodecarlos

They want a BOINC challenge, that's it. They don't care which application (siever).

I know, but why not make it a challenge for the forum as well.

My original train of thought was, as per other discussion, "the challenge should really be 16e (not that they care of course, but logistically for us, increased sieving for a challenge would only further strain 14e and 15e)... what's a good challenge for 16e?" which led to what I suggested.

Edit: It arguably has several other merits as well. For one, it would be a true return to mathematical research, which arguably NFS@Home hasn't really been doing of late (the LA hasn't really been pushing any boundaries). Additionally, it could be publicized thusly "not just another BOINC challenge, actual, specific new research, and we need your help!"

Of course, we'd need several forumites with a suitably strong background to lead the effort, not to mention frmky and resources for linear algebra, but it is an idea.

[xilman]

Originally Posted by Dubslow

If people really wanted a full on challenge.... one possible idea is attempting to try our collective hand at the multiple (S)NFS factory technique.

Considering the amount of data involved (not to mention the massive linear algebra involved), it may not necessarily be a good idea to numbers quite as large as the original paper, but I imagine there's some other Cunningham tables that have several holes with smaller size numbers compared to 2-?

Or is this a complete pipe dream? I'm not really sure.

It's undoubtedly possible, but there are a lot of buts ...

I've looked into the idea. Here are some of the things to consider.

• For it to be remotely close to being real research, the integers would need to be kilobit-sized or more.
  
• All the candidates would need extensive pre-testing with ECM. You're looking at a few thousand core years for this stage alone.
  
• Sieving will take several thousand core years on machines which can allocate perhaps a gigabyte of RAM per core.
  
• Data storage will run into a substantial fraction of a petabyte. Call it several dozen 2TB disks and/or three years non-stop transfer over a 1Mbyte/s (approx 10Mbs after overheads).
  
• Several matrices, each with several hundred million rows and columns, will need processing.
  
• The project management requirements will be onerous and, at times, tedious. Someone (in practice a team of several well coordinated people) has to manage all that data, monitor system health, ensure data backups, provide hand-holding, write ad-hoc scripts, solve problems as they arrive, and so on.
  
• The project as a whole is likely to take several years from start to completion.

So, not impossible, but certainly non-trivial.

It's easy to see how some portions could be parallelized: ECM and sieving over BOINC); data collection at multiple sites terminated with a significant sneakernet transfer to a central site; a management team spread over several sites in several time zones.

The LA is certainly non-trivial. We could perhaps ask for favours but no guarantees could be made.


If a somewhat less trivial challenge is required, why not work out how to run blocked Wiedemann over BOINC? That would definitely be of research interest and of practical use in the future.

A substantially less trivial challenge woud be to run polynomial selection for RSA-1024 over BOINC. Something like a thousand GPU-years should be enough.

[RichD]

Originally Posted by xilman

... how to run blocked Wiedemann over BOINC? That would definitely be of research interest and of practical use in the future.

... run polynomial selection for RSA-1024 over BOINC.

I like these two ideas.

[xilman]

Originally Posted by RichD

I like these two ideas.

So do I, which is why I suggested them ...

To be serious, the BOINC block Wiedemann idea is far better in my view, as long as it is possible to do with decent efficiency, both computational and non-computational. It is very far from clear how to do that.

It would create a tool with long-lasting value whereas finding polynomials only allows the factorization of a single integer which, although giving bragging rights within a small community, is unlikely to be of any greater significance.

[frmky]

I agree that BOINC block Wiedemann is very worthy of serious exploration.

[pinhodecarlos]

Originally Posted by frmky

I agree that BOINC block Wiedemann is very worthy of serious exploration.

Ok, lets do it.

[xilman]

Originally Posted by pinhodecarlos

Ok, lets do it.

In that case, I suggest

a) that you read up on BW;
b) get hold of the current cado-nfs code base and investigate the bwc directory in some detail
c) suggest how the Berlekamp-Massey implementation can be modified so that the other two phases can be split over a significantly large number of systems.

[RichD]

Found this publication interesting (I just read the summary), using CUDA and implementing BW on a GPU cluster.

http://onlinelibrary.wiley.com/doi/1....2896/abstract

[jasonp]

A nice paper; they modified cado-nfs :)

[henryzz]

Originally Posted by RichD

Found this publication interesting (I just read the summary), using CUDA and implementing BW on a GPU cluster.

http://onlinelibrary.wiley.com/doi/1....2896/abstract

Has anyone found a free version of this paper?