mersenneforum.org QS Lattice Siever
 Register FAQ Search Today's Posts Mark Forums Read

 2010-10-21, 14:49 #1 R.D. Silverman     "Bob Silverman" Nov 2003 North of Boston 22×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 (B2-B1). 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
2010-10-21, 15:08   #2
bsquared

"Ben"
Feb 2007

22×3×311 Posts

Quote:
 Originally Posted by R.D. Silverman 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 (B2-B1). 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
msieve processes multiple b's at a time, by storing the info necessary to change the roots of each prime from b to b as it sieves. But if I understand correctly, this is different from what you're talking about here; it is more of a sieving optimization. There is no reduced basis or special_q in msieve, that I know of.

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.

2010-10-21, 15:27   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

Quote:
 Originally Posted by bsquared msieve processes multiple b's at a time, by storing the info necessary to change the roots of each prime from b to b as it sieves. But if I understand correctly, this is different from what you're talking about here; it is more of a sieving optimization. There is no reduced basis or special_q in msieve, that I know of. 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.
I would first need to write a paper on the algorithm. What I am discussing
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.

2010-10-21, 16:06   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D5416 Posts

Quote:
 Originally Posted by R.D. Silverman 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 (B2-B1). 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
Note that we would need to make q(x) bivariate.....

2010-10-21, 16:16   #5
bsquared

"Ben"
Feb 2007

22×3×311 Posts

Quote:
 Originally Posted by R.D. Silverman I would first need to write a paper on the algorithm. What I am discussing is totally different from what you do.
I know, and I'm really excited about that! I'm tired of trying to eek out 1-2% improvements in my siqs code, so this is a great chance for me to try out something new that isn't (hopefully) as much of a stretch as implementing a NFS siever would be.

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).

2010-10-21, 16:24   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

Quote:
 Originally Posted by bsquared I know, and I'm really excited about that! I'm tired of trying to eek out 1-2% improvements in my siqs code, so this is a great chance for me to try out something new that isn't (hopefully) as much of a stretch as implementing a NFS siever would be.
It would be close. The only real difference would be in not having
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.

2010-10-21, 17:10   #7
bsquared

"Ben"
Feb 2007

373210 Posts

Quote:
 Originally Posted by R.D. Silverman It would be close. The only real difference would be in not having 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.
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.

2010-10-21, 17:52   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

750810 Posts

Quote:
 Originally Posted by bsquared 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.
Here is a sketch.

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.

 2010-10-21, 19:18 #9 jasonp Tribal Bullet     Oct 2004 32×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 blue-sky about QS, Colin Percival wrote in his blog about an idea to turn MPQS with an extremely small sieve interval into a subset-sum 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.
2010-10-21, 20:55   #10
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010101002 Posts

Quote:
 Originally Posted by jasonp 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 blue-sky about QS, Colin Percival wrote in his blog about an idea to turn MPQS with an extremely small sieve interval into a subset-sum 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.
I know about the Zhang result. It's applicability is somewhat limited and
AFAIK, noone has ever implemented it.

 2010-10-22, 00:15 #11 jasonp Tribal Bullet     Oct 2004 355510 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post chris2be8 Factoring 6 2018-02-06 17:22 pstach Factoring 1 2014-05-23 01:03 fivemack Programming 2 2012-12-16 01:07 Batalov Msieve 54 2010-01-13 19:45 fivemack Factoring 1 2008-01-18 13:47

All times are UTC. The time now is 21:24.

Thu Feb 2 21:24:19 UTC 2023 up 168 days, 18:52, 1 user, load averages: 1.02, 0.93, 0.87