WLSS2?

frmky · 2008-05-20, 22:39

Hi,

I just started the postprocessing of 2,949+ in a single thread, and if left on this computer it will take 6 months to finish. Additional Lanczos threads on this computer actually slow it down. So, out of curiosity, I did a web search for Block Wiedemann, and found WLSS2 at ftp://ftp.cs.rpi.edu/pub/loboa. This is an implementation from the mid-90's and so I'm sure could be optimized for today's processors, but has anyone tried it? Would it be difficult to convert a small msieve matrix to their format and the solutions back to the msieve format just to do a quick test?

Greg

fivemack · 2008-05-27, 15:51

Do you not have the possibility of more sieving? I have now run a few examples with significant oversieving, and find that 10% more unique relations often makes for 20% fewer matrix rows and therefore 40% shorter matrix run-time; you have I believe hundreds of cores for sieving and one for post-processing.

I've collected WLSS2; it compiles but segfaults at once on my machine, unless you add

Code:

#include <unistd.h>
#include <time.h>

at the top of time.h. After that it compiles and doesn't work - it's not 64-bit safe. I'm poking around a bit to try to fix that.

However, since the documentation says that the minpoly routine runs in quadratic time, I suspect it will be useless for even very small msieve matrices - implementing Berlekamp-Massey with efficient FFT polynomial arithmetic over a cluster is about an MSc-project of work. I believe I've been pointed to a good recent paper (not the http://eprint.iacr.org/2007/205.pdf or http://www.loria.fr/~thome/php/dl.ph...papers/jsc.pdf one) on how to do it from this forum at one point, but I can't find it any more.

mkdube · 2013-04-05, 08:58

wlss2 compiles but not not run. Any body can suggest about the solution

jasonp · 2013-04-05, 14:36

If you want to get block Weidemann running, there is no reason to use anything other than CADO-NFS, since the implementation there is efficient and very actively maintained.

2008-05-20, 22:39	#1
frmky Jul 2003 So Cal 83A₁₆ Posts	WLSS2? Hi, I just started the postprocessing of 2,949+ in a single thread, and if left on this computer it will take 6 months to finish. Additional Lanczos threads on this computer actually slow it down. So, out of curiosity, I did a web search for Block Wiedemann, and found WLSS2 at ftp://ftp.cs.rpi.edu/pub/loboa. This is an implementation from the mid-90's and so I'm sure could be optimized for today's processors, but has anyone tried it? Would it be difficult to convert a small msieve matrix to their format and the solutions back to the msieve format just to do a quick test? Greg

2008-05-27, 15:51	#2
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	Do you not have the possibility of more sieving? I have now run a few examples with significant oversieving, and find that 10% more unique relations often makes for 20% fewer matrix rows and therefore 40% shorter matrix run-time; you have I believe hundreds of cores for sieving and one for post-processing. I've collected WLSS2; it compiles but segfaults at once on my machine, unless you add Code: #include <unistd.h> #include <time.h> at the top of time.h. After that it compiles and doesn't work - it's not 64-bit safe. I'm poking around a bit to try to fix that. However, since the documentation says that the minpoly routine runs in quadratic time, I suspect it will be useless for even very small msieve matrices - implementing Berlekamp-Massey with efficient FFT polynomial arithmetic over a cluster is about an MSc-project of work. I believe I've been pointed to a good recent paper (not the http://eprint.iacr.org/2007/205.pdf or http://www.loria.fr/~thome/php/dl.ph...papers/jsc.pdf one) on how to do it from this forum at one point, but I can't find it any more. Last fiddled with by fivemack on 2008-05-27 at 16:17

2013-04-05, 08:58	#3
mkdube Apr 2013 1 Posts	wlss2 wlss2 compiles but not not run. Any body can suggest about the solution

2013-04-05, 14:36	#4
jasonp Tribal Bullet Oct 2004 3,541 Posts	If you want to get block Weidemann running, there is no reason to use anything other than CADO-NFS, since the implementation there is efficient and very actively maintained.