20101021, 14:49  #1 
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 
QS Lattice Siever
Has anyone ever looked at writting a QS lattice siever?
QS normally implements a line sieve in the (b,a) plane. It processes M < a < M one b at a time. But there is n reason why it couldn't do what NFS does. Sieve over M < a < M for (say) B1 < b < B2 all at once. The sieve area would be (2M x (B2B1). We would sieve only those points such that q(x), the value of the quadratic polynomial was divisible by a chosen special_q. After sieving B1 < b < B2, we then move to B2 < B < B3, etc. You would solve q(x) = 0 mod special_q (generally there would be two roots r1, r2). You then construct a reduced basis for (q, r1) and one for (q, r2), than lattice sieve over the region as NFS does. You would sieve twice; once for each root. If I can find the time (I am very busy with real work and improving my NFS siever) I may even write a paper on the technique. Meanwhile, I toss out the idea as food for thought for anyone who might want to tackle this. (Perhaps a joint paper??) Bob 
20101021, 15:08  #2  
"Ben"
Feb 2007
2^{2}×3×311 Posts 
Quote:
I'm willing to spend time writing code to try it out, but I would need some more info/coaching on several things  how to do the basis reduction, for instance. I'm also pretty busy, so I may not be the best candidate if you want to write something short term. 

20101021, 15:27  #3  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 
Quote:
is totally different from what you do. The technique I propose here would sieve over lattice points where the norm of q(x) is a priori divisible by the special_q, making it much more likely to be smooth with respect to the factor base. It could easily add 20 to 30 digits in the same amount of time. 

20101021, 16:06  #4  
"Bob Silverman"
Nov 2003
North of Boston
1D54_{16} Posts 
Quote:


20101021, 16:16  #5  
"Ben"
Feb 2007
2^{2}×3×311 Posts 
Quote:
I'm willing to write code when it gets to that point or to test out ideas as they occur to you (if you want help with that sort of thing). 

20101021, 16:24  #6  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
to deal with two different factor bases, and not having to deal with algebraic number theory, (esp.) in the square root phase. They would have many common elements. 

20101021, 17:10  #7 
"Ben"
Feb 2007
3732_{10} Posts 
I'm aware that there will be a learning curve, but it sound like it won't be as steep as the one to an NFS lattice siever would be. This sound to me like a good half way point, and I'm excited about the possibilities.

20101021, 17:52  #8  
"Bob Silverman"
Nov 2003
North of Boston
7508_{10} Posts 
Quote:
Construct a polynomial q(x,y) = Ax^2 + 2Bxy + Cy^2 whose discriminant is a multiple of N. Set x = 1 (say) and solve q(x,y) = 0 mod q. There will be two roots, r1, r2. Find reduced lattices for [q r1][0 1] and [q r2][0 1]. This yields two sets of vectors V1, V2, and W1, W2. Now lattice sieve as in NFS. This will give a whole slew of points (e,f) such that (x,y) = eV1 + f V2 will have q(x,y) divisible by q. We now hope that q(x,y)/q is smooth with respect to the factor base. Repeat for the W1, W2 vectors. Now try a new special q. REPEAT. 

20101021, 19:18  #9 
Tribal Bullet
Oct 2004
3^{2}×5×79 Posts 
I think there might be some related ideas in this paper, in that one can sieve over a degree 4 polynomial whose coefficients might be small, depending on the exact form of N, and lattice sieving can be used here too. If memory serves the coefficients would have to be extremely small to be competitive with ordinary QS.
While we're doing bluesky about QS, Colin Percival wrote in his blog about an idea to turn MPQS with an extremely small sieve interval into a subsetsum problem. The idea is that if the large primes in the factor base are much larger than the sieve interval, most will hit once or twice across tens of thousands of different b values. I actually implemented his idea in an experimental msieve version, and it can complete the same amount of sieving in half the time, but it requires massive amounts of memory and the relation rate drops by 4x compared to the parametrization in the production QS code. 
20101021, 20:55  #10  
"Bob Silverman"
Nov 2003
North of Boston
1110101010100_{2} Posts 
Quote:
AFAIK, noone has ever implemented it. 

20101022, 00:15  #11 
Tribal Bullet
Oct 2004
3555_{10} Posts 
I agree that Zhang's method per se won't help much here, but the paper goes through the process of converting the input number into a homogeneous polynomial which can be sieved over a lattice just like we know how to do. I only bring it up because their analysis of the size of the norms involved implies that you'd be better off using QS for almost any input. So what chance do we have splitting N into fewer than three pieces?

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Compiling 64 bit lattice siever on gcc 4.8.5  chris2be8  Factoring  6  20180206 17:22 
OpenCL accellerated lattice siever  pstach  Factoring  1  20140523 01:03 
Shape of a CUDA lattice siever  fivemack  Programming  2  20121216 01:07 
Msieve / lattice siever with degree 7/8 poly  Batalov  Msieve  54  20100113 19:45 
ggnfs lattice siever misses some primes  fivemack  Factoring  1  20080118 13:47 