Abstract
We give provable sieving algorithms for SVP and CVP, that works in l_p norm. Building on the randomized sieving framework of AKS (2001,2002) we introduce linear and mixed sieving procedures. This makes the sieving iterations (the most expensive part in AKS type sieving algorithms) faster. It also improves the overall running time when compared to algorithms like that of Blomer and Naewe, that works in all l_p norm. Even in the special case of Euclidean norm our running time (2^{2.25n+o(n)}) is better than that of List Sieve Birthday algorithm (2^{2.465n+o(n)}). The main idea of our algorithms is to divide the space into hypercubes such that each vector can be mapped very efficiently. This improves the running time complexity of each sieving iteration in AKS-style algorithms from (approximately) quadratic to linear in the number of input vectors.