Faster algorithms for integer lattice basis reduction
Arne Storjohann · 1996
The well known L³-reduction algorithm of Lov'asz transforms a given integer lattice basis b1 ; b2 ; : : : ; bn 2 ZZ n into a reduced basis. The cost of L 3 -reduction is O(n 4 log Bo) arithmetic operations with integers bounded in length by O(n log Bo) bits. Here, Bo bounds the Euclidean length of the input vectors, that is, Bo jb1 j 2 ; jb2 j 2 ; : : : ; jbn j 2 . We present a simple modification of the L³-reduction algorithm that requires only O(n³ log Bo) arithmetic operations with integers of the same length. We gain a further speedup by combining our new approach with Schonhage's modification of the L³-reduction algorithm and incorporating fast matrix mutliplication techniques. The result is an algorithm for semi-reduction that requires O(n 2:381 log Bo ) arithmetic operations with integers of the same length.