## 3 A Faster Provable Sieving Algorithm in \(\ell_{p}\) Norm
### Linear Sieve  
In the initial AKS algorithm [21; 45] as well as in all its variants thereafter [27; 47; 48], in the sieving sub-routine, a space \(B_{n}^{(p)}(R)\) has been divided into sub-regions such that each sub-region is associated with a center. Then, given a vector, we map it to a sub-region and subtract it from the center so that we get a vector of length at most \(\gamma R\). We must aim to select these sub-regions such that we can (i) map a vector efficiently to a sub-region (ii) without increasing the number of centers \"too much\". The latter factor is determined by the number of divisions of \(B_{n}^{(p)}(R)\) into these sub-regions and directly contributes to the space (and hence time) complexity. In all the previous provable sieving algorithms, the sub-regions were small hyperballs (or parts of them) in \(\ell_{p}\) norm. In this paper, our sub-regions are hypercubes. The choice of this particular sub-region makes the mapping very efficient. First, let us note that, in contrast with the previous algorithms (except [49]), we divide the space a priori. This can be done by dividing each co-ordinate axis into intervals of length \(\frac{\gamma R}{\gamma^{1/p}}\) so that the distance between any two vectors in the resulting hypercube is at most \(\gamma R\). In an ordered list, we store an appropriate index (say, co-ordinates of one corner) of only those hypercubes which have a non-zero intersection with \(B_{n}^{(p)}(R)\). We can map a vector to a hypercube in \(O(n)\) time simply by looking at the intervals in which each of its co-ordinates belong. If the hypercube contains a center, then we subtract the vectors and store the difference; otherwise, we assign this vector as the center. An illustration is given in Figure 3.  
Figure 3: One iteration of the linear sieve in the \(\ell_{2}\) norm. **(a)** A number of vector pairs (solid black dots) with (Euclidean) length at most \(R\) are sampled. **(b)** The space is divided into a number of hypercubes with diagonal length \(r\), and each vector pair is mapped into a hypercube. **(c)** Within each hypercube, a subtraction operation (denoted by arrow) is performed between a center (red dot) and the remaining vector pairs, such that we obtain shorter lattice vectors in the next iteration. Figure 2: One iteration of the quadratic AKS sieve in the \(\ell_{2}\) norm. Each point represents a vector pair. The solid dots are the sampled ones, while the hollow dots are the unsampled ones. Among the sampled vector pairs, some are identified as centers (red dots) and the space is divided into a number of balls, centered around these red dots. Vector subtraction (denoted by arrow) is performed with the center pair in each ball, such that we obtain shorter lattice vectors in the next iteration. The following lemma gives a bound on the number of hypercubes or centers we obtain by this process. Such a volumetric argument can be found in [66]. Let \(\gamma\in(0,1),R\in\mathbb{R}_{\geq 1},1\leq p\leq\infty\) and \(r=\frac{\gamma R}{2n^{1/p}}\). The number of translates of \(B_{n}^{(\infty)}(r)\) required to cover \(B_{n}^{(p)}(R)\) is at most \(O\Big{(}\Big{(}2+\frac{2}{\gamma}\Big{)}^{n}\Big{)}\). Proof. : Let \(N_{h}\) be the number of translates of \(L=B_{n}^{(\infty)}(r)\) required to cover \(K=B_{n}^{(p)}(R)\). These translates are all within \(K\oplus 2L\). In addition, noting that \(L\subseteq\frac{m^{1/p}}{R}K\), we have  
\[N_{h}*\text{vol}(L)\leq\text{vol}(K+2L)\leq\Bigg{(}1+\frac{2 rn^{1/p}}{R}\Bigg{)} ^{n}\text{vol}(K)\]  
Plugging in the value of \(r\), we have \(N_{h}\leq(1+\gamma)^{n}\frac{\text{vol}(K)}{\text{vol}(L)}\). Using Fact 3, we have \(N_{h}\in O\Big{(}\Big{(}2+\frac{2}{\gamma}\Big{)}^{n}\Big{)}\). Note that the above lemma implies a sub-division where one hypercube is centered at the origin. Thus, along each axis, we can have the following \(2r\)-length intervals:  
\[\ldots[-5r,-3r),[-3r,-r),[-r,r),[r,3r),[3r,5r),\ldots\]  
We do not know whether this is the most optimal way of sub-dividing \(B_{n}^{(p)}(R)\) into smaller hypercubes.