View Single Post
Old 2004-05-25, 16:36   #2
xilman's Avatar
May 2003
Down not across

1068610 Posts

Originally Posted by JHansen

I (think) I have understood how the line siever works, but I have no clue of how the lattice siever works. Could someone please explain to me (and the rest of the group ) how the lattice siever works?

I have tried the CWI line siever and Jens Franke's lattice siever. His siever seems to be faster. Is this due to the implementation or is there a theoretical reason for the lattice siever to be faster?

Best regards
Jes Hansen
I'll try, but please keep in mind that my explanation is (deliberately) handwaving and glosses over important detail.

If you know how the line siever works, you know then how the norms of each polynomial which are divisible by a specific prime are equally separated along the sieving line. (Handwaving warning: I mean prime ideal or, if you're happier with this phrasing, there is one such series per root of the polynomial mod p).

Right, now fix a large prime, one bigger than any in the factorbase for a particular polynomial. Call it q. Better, call it special_q because we've chosen it to be special. Now, you will again agree that norms divisible by this special-q are regularly separated in the sieving region, right? That is, they form a lattice.

The clever bit of the lattice sieve is to transform the polynomials or, entirely equivalent, the coordinate system of the sieving rectangle so that these lattice points become adjacent in the transformed system. Now sieve the transformed region with the factorbase primes. You know, a priori, that all the norms are divisible by a large prime and so, after that prime is divided out, the norm will be smaller by a factor of special-q and so (handwaving again) more likely to be smooth. Smooth is good, so you are more likely to get a relation.

That's the handwaving reason why the lattice sieve is likely to be faster than the line sieve. It completely glosses over some features which damage its performance. For a start, reducing the norm of one polynomial is likely, in practice, to increase the norm of the other. To some extent this can be counteracted by using special-q on the polynomial which typically has the greater norm. Another source of inefficiency is the requirement for the coordinate transformations for each special-q.

It's my belief that Jens Franke's lattice siever gains most of its speed over the CWI line siever from implementational differences. It has assembly language support for various x86 systems whereas the CWI siever uses much more general purpose code. The lattice siever's use of a very fast mpqs for factoring 2-large prime candidates probably outperforms the CWI-siever's use of rho and squfof, though I haven't evaluated that area in any detail.

Some of the speed increase, though, probably does come from it using the lattice sieve. Again, I haven't tried to disentangle the effects and to quantify them.

Down sides of the lattice sieve become apparent when you consider the post-sieving phases. First off, a prime can be a special-q and also a regular large prime for a different special-q and vice versa. That is, duplicate relations are almost inevitable when using a lattice sieve. The dups have to be identified and rejected. This takes computation and storage and, in a distributed computation, comms bandwidth. It also means that the raw relations/second measure isn't quite such a good measure of efficiency as it is for the line siever. Worse, the number of duplicates increases as the number of relations grows (another view of the birthday paradox) and so the effective rate of relation production falls as the computation proceeds.

Something that tends to hit the linear algebra phase is that the special-q primes act in many ways as if they were factor base primes. That is, they tend to make the matrix larger and denser compared with the relations found by a line sieve with the same factorbases. However, the argument can be turned on its head: by using a large effective factor base one can use a smaller real factorbase and so speed up the sieving without losing relations. Think about it, and you'll see that this is another way of phrasing the paragraph above beginning "The clever bit ..."

Hope this helps.

xilman is offline