## 3 A Faster Provable Sieving Algorithm in \(\ell_{p}\) Norm
### Improvement Using the Birthday Paradox  
We can obtain a better running time and space complexity if we use the birthday paradox to decrease the number of sampled vectors but obtain at least two vector pairs corresponding to the same lattice vector after the sieving iterations [26; 28]. For this, we have to ensure that the vectors are independent and identically distributed before step 12 of Algorithm 1. Thus, we incorporate the following modification, as discussed in [26]. Very briefly, the trick is to set aside many uniformly distributed vector pairs as centers for each sieving step, even before the sieving iterations begin. In each sieving iteration, the probability that a vector pair is not within the required distance of any center pair decreases. Now, if we sample enough vectors, then with a good probability at step 12, we have at least two vectors whose perturbation is in \(D_{1}\bigcup D_{2}\), implying that with a probability of at least \(1/2\), we obtain the shortest vector. In the analysis of [26], the authors simply stated that the required center pairs can be sampled uniformly at the beginning. In our linear sieving algorithm, we have an advantage. Unlike the AKS-style algorithms, in which the center pairs are selected and then the space is divided, in our case, we can divide the space a priori. We take advantage of this and conduct a number of random divisions of the space. Since in each iteration, the length of the vectors decreases, the size of the hypercubes also decreases, and this can be calculated. Thus, for each iteration we have a number of divisions of the space into hypercubes of a certain size. For this, we need to divide the axes into intervals of a fixed size. Simply by shifting the intervals in each axis, we can make this division random. Then, among the uniformly sampled vectors, we select a center for each hypercube. Assume we start with \(N\geq\frac{2}{q}(n^{3}k|\mathcal{C}|+n2^{\frac{c_{b}}{2}n})\) sampled pairs. After the initial sampling, for each of the \(k\) sieving iterations, we fix \(\Omega\Bigl{(}\frac{2n^{3}}{q}|\mathcal{C}|\Bigr{)}\) pairs to be used as center pairs in the following way. 1. Let \(R=\max_{i\in[N]}\|\mathbf{y}_{i}\|_{p}\). We maintain \(k\) lists of pairs, \(\mathcal{C}_{1},\mathcal{C}_{2},\ldots,\mathcal{C}_{k}\), where each list is similar to \((\mathcal{C})\), as described in Algorithm 2. In the \(i\)th list, we store the indices (co-ordinates of a corner) of translates of \(B_{n}^{(\infty)}(r_{i})\) that have a non-zero intersection with \(B_{n}^{(p)}(R_{i})\) where \(R_{i}=\gamma^{i-1}R+\xi\lambda\frac{1-\gamma^{i-1}}{1-\gamma}\) and \(r_{i}=\frac{\gamma R_{i}}{2n^{1/p}}\). For such a division, we can obtain \(O(|\mathcal{C}|)\) center pairs in each list. To meet our requirement, we maintain \(O(n^{3})\) such lists for each \(i\). We call these \(O(n^{3})\) lists the \"sibling lists\" of \(\mathcal{C}_{i}\). 2. For each \((\mathbf{e},\mathbf{y})\in S\) (where \(S\) is the set of sampled pairs), we first calculate \(\|\mathbf{y}\|_{p}\) to check in which list group it can potentially belong, say \(\mathcal{C}_{j}\). That is, \(C_{j}\) corresponds to the smallest hyperball containing \(\mathbf{y}\). Then, we map it to its index-tuple \(I_{\mathbf{y}}\), as has already been described before. We add \((\mathbf{e},\mathbf{y})\) to a list in \(C_{j}\) or any of its sibling lists if it was empty before. Since we sampled uniformly, this ensures we obtain the required number of (initially) fixed centers, and no other vector can be used as a center throughout the algorithm. Having set aside the centers, now we repeat the following sieving operations \(k\) times. For each vector pair \((\mathbf{e}_{1},\mathbf{y}_{1})\in S\), we can check which list (or its sibling lists) it can belong to from \(\|\mathbf{y}_{1}\|_{p}\). Then, if a center pair is found, we subtract as in step 15 of Algorithm 2. Otherwise, we discard it and consider it \"lost\". Let us call this modified sieving procedure **LinearSieveBirthday**.