Skip to main content
4 of 4
formatting
Gerry Myerson
  • 39.9k
  • 10
  • 186
  • 247

Lattice Sieving in Number Field Sieve

I am currently going through Pollard's article on Lattice Sieving and have a few confusions. Firstly, how to figure that $C$ and $D$ in the two-dimensional array so that every $(c,d)$ pair corresponds to a lattice element $(a,b)$ because if I consider $ c \in [-C,C]$ and $d \in [1,D]$ where $C$ is to be chosen greater than $D$; there are many combinations of type $cV_1 + dV_2$ which go outside the lattice. Here, $V_1$ and $V_2$ are the reduced basis of the lattice.

Pollard, J.M., The lattice sieve, Lenstra, A. K. (ed.) et al., The development of the number field sieve. Berlin: Springer-Verlag. Lect. Notes Math. 1554, 43-49 (1993). ZBL0806.11066, doi: 10.1007/BFb0091538.

Secondly, this 2-D array can't cover entire $L(q)$, so aren't we missing a lot of smooth pairs?