Lattice sieving

Lattice sieving is a technique for finding smooth values of a bivariate polynomial ${\displaystyle f(a,b)}$ over a large region. It is almost exclusively used in conjunction with the number field sieve. The original idea of the lattice sieve came from John Pollard.^[1]

The algorithm implicitly involves the ideal structure of the number field of the polynomial; it takes advantage of the theorem^{Which one?} that any prime ideal above some rational prime p can be written as ${\displaystyle p\mathbb {Z} [\alpha ]+(u+v\alpha )\mathbb {Z} [\alpha ]}$. One then picks many prime numbers q of an appropriate size, usually just above the factor base limit, and proceeds by

For each q, list the prime ideals above q by factorising the polynomial f(a,b) over ${\displaystyle GF(q)}$

For each of these prime ideals, which are called 'special ${\displaystyle {\mathfrak {q}}}$'s, construct a reduced basis ${\displaystyle \mathbf {x} ,\mathbf {y} }$ for the lattice L generated by ${\displaystyle {\mathfrak {q}}}$; set a two-dimensional array called the sieve region to zero.

For each prime ideal ${\displaystyle {\mathfrak {p}}}$ in the factor base, construct a reduced basis ${\displaystyle \mathbf {x} _{\mathfrak {p}},\mathbf {y} _{\mathfrak {p}}}$ for the sublattice of L generated by${\displaystyle {\mathfrak {pq}}}$

For each element of that sublattice lying within a sufficiently large sieve region, add ${\displaystyle \log |{\mathfrak {p}}|}$ to that entry.

Read out all the entries in the sieve region with a large enough value

For the number field sieve application, it is necessary for two polynomials both to have smooth values; this is handled by running the inner loop over both polynomials, whilst the special-q can be taken from either side.