QS Lattice Siever

[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

[bsquared]

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.

[R.D. Silverman]

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.

[R.D. Silverman]

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

[bsquared]

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

[R.D. Silverman]

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.

[bsquared]

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.

[R.D. Silverman]

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.

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

[R.D. Silverman]

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.

[jasonp]

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?