Resumen
In this work, we give provable sieving algorithms for the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices in l??
l
p
norm (1=??=8
1
=
p
=
8
). The running time we obtain is better than existing provable sieving algorithms. We give a new linear sieving procedure that works for all l??
l
p
norm (1=??=8
1
=
p
=
8
). The main idea is to divide the space into hypercubes such that each vector can be mapped efficiently to a sub-region. We achieve a time complexity of 22.751??+??(??)
2
2.751
n
+
o
(
n
)
, which is much less than the 23.849??+??(??)
2
3.849
n
+
o
(
n
)
complexity of the previous best algorithm. We also introduce a mixed sieving procedure, where a point is mapped to a hypercube within a ball and then a quadratic sieve is performed within each hypercube. This improves the running time, especially in the l2
l
2
norm, where we achieve a time complexity of 22.25??+??(??)
2
2.25
n
+
o
(
n
)
, while the List Sieve Birthday algorithm has a running time of 22.465??+??(??)
2
2.465
n
+
o
(
n
)
. We adopt our sieving techniques to approximation algorithms for SVP and CVP in l??
l
p
norm (1=??=8
1
=
p
=
8
) and show that our algorithm has a running time of 22.001??+??(??)
2
2.001
n
+
o
(
n
)
, while previous algorithms have a time complexity of 23.169??+??(??)
2
3.169
n
+
o
(
n
)
.