mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > NFS@Home

Reply
 
Thread Tools
Old 2015-01-27, 16:36   #1
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default Ideas for the future beyond just-keep-encrunching

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 is offline   Reply With Quote
Old 2015-01-27, 17:10   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by pinhodecarlos View Post
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.

Last fiddled with by Dubslow on 2015-01-27 at 17:47
Dubslow is offline   Reply With Quote
Old 2015-01-29, 17:55   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

25·331 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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.
xilman is online now   Reply With Quote
Old 2015-01-30, 05:10   #4
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

22·821 Posts
Default

Quote:
Originally Posted by xilman View Post
... 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.
RichD is offline   Reply With Quote
Old 2015-01-30, 09:06   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

25·331 Posts
Default

Quote:
Originally Posted by RichD View Post
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.

Last fiddled with by xilman on 2015-01-30 at 09:12 Reason: Add proviso
xilman is online now   Reply With Quote
Old 2015-01-30, 21:01   #6
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

22·11·47 Posts
Default

I agree that BOINC block Wiedemann is very worthy of serious exploration.
frmky is offline   Reply With Quote
Old 2015-01-30, 21:52   #7
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

5·7·139 Posts
Default

Quote:
Originally Posted by frmky View Post
I agree that BOINC block Wiedemann is very worthy of serious exploration.
Ok, lets do it.
pinhodecarlos is online now   Reply With Quote
Old 2015-01-30, 22:04   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

25×331 Posts
Default

Quote:
Originally Posted by pinhodecarlos View Post
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.
xilman is online now   Reply With Quote
Old 2015-01-31, 02:59   #9
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

22×821 Posts
Default

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
RichD is offline   Reply With Quote
Old 2015-01-31, 03:10   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

A nice paper; they modified cado-nfs :)
jasonp is offline   Reply With Quote
Old 2015-02-01, 09:31   #11
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5,821 Posts
Default

Quote:
Originally Posted by RichD View Post
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?
henryzz is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some ideas regarding NFS... paul0 Factoring 3 2015-03-14 19:55
I broke ECM-Fermat...or my PC IDEAS? petrw1 PrimeNet 6 2013-04-27 22:55
two ideas for NPLB Mini-Geek No Prime Left Behind 16 2008-03-01 23:32
GROUP IDEAS TTn 15k Search 15 2003-09-23 16:28
Domain name ideas... Xyzzy Lounge 17 2003-03-24 16:20

All times are UTC. The time now is 15:57.

Fri Mar 5 15:57:03 UTC 2021 up 92 days, 12:08, 0 users, load averages: 2.01, 2.39, 2.31

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.