Simultaneous Factoring
Just a thought.
I see that NFSNET is now doing 5,307+, having just sieved 5,307. I not that it is possible to do BOTH of them at the same time and save 25% of the run time. For each number, we need to sieve the norms of two polynomials. This is a total of "four sieve procedures" for the two numbers. But one of the sieves is the SAME for both numbers. The linear polynomial is the same for both numbers. At the cost of some additional memory it should be possible to do both numbers at once. You would need to sieve the linear polynomial only once. This would save 25%. Perhaps NFSNET should look into this for their siever. Bob 
[QUOTE=R.D. Silverman]Just a thought.
I see that NFSNET is now doing 5,307+, having just sieved 5,307. I not that it is possible to do BOTH of them at the same time and save 25% of the run time. For each number, we need to sieve the norms of two polynomials. This is a total of "four sieve procedures" for the two numbers. But one of the sieves is the SAME for both numbers. The linear polynomial is the same for both numbers. At the cost of some additional memory it should be possible to do both numbers at once. You would need to sieve the linear polynomial only once. This would save 25%. Perhaps NFSNET should look into this for their siever. Bob[/QUOTE]A nice idea! I'll think about it. Paul 
I once mentioned the same idea to Peter Montgomery, he replied that a certain Bob Silverman :wink: mentioned it almost ten years earlier. He also told me that this idea is not implemented in the CWI siever, however multiple polynomial NFS for factoring [I]one[/I] number is. Maybe the code could be adapted to the manynumbersatonce idea.
He also mentioned another nice trick to use symmetry in the algebraic polynomial: for even polynomials, F(a,b) is smooth iff F(a,b) is, so the algebraic side only needs to sieve nonnegative values. For symmetric polynomials (same coefficients lefttoright as righttoleft), F(a,b) is smooth iff F(b,a) is, though this symmetry seems harder to exploit. He said these tricks are not implemented in the CWI siever, either. Alex 
[QUOTE=akruppa]I once mentioned the same idea to Peter Montgomery, he replied that a certain Bob Silverman :wink: mentioned it almost ten years earlier. He also told me that this idea is not implemented in the CWI siever, however multiple polynomial NFS for factoring [I]one[/I] number is. Maybe the code could be adapted to the manynumbersatonce idea.
He also mentioned another nice trick to use symmetry in the algebraic polynomial: for even polynomials, F(a,b) is smooth iff F(a,b) is, so the algebraic side only needs to sieve nonnegative values. For symmetric polynomials (same coefficients lefttoright as righttoleft), F(a,b) is smooth iff F(b,a) is, though this symmetry seems harder to exploit. He said these tricks are not implemented in the CWI siever, either. Alex[/QUOTE] Hi, I was aware of the symmetry tricks as well; I had even suggested one or two to Peter some time ago. I looked into implementing one of the simpler ones (you discussed it above) and concluded that you needed too much memory and saving of state information to be effective. Bob 
I hope it is alright to bump this 9yearold topic. I am wondering if the situation is any different, here in the future. Is it?

Yes: manylinearsides factorisation has been implemented by the EPFL group and used to collect half a dozen largestSNFS records in succession.
[url]http://eprint.iacr.org/2014/653.pdf[/url] 
All times are UTC. The time now is 22:40. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.