Several Computational Problems In Lattice Theory

This thesis focuses on two fundamental and important computational problems in lattice theory: computing bases and lattice basis reduction. The first problem refers to that given a set of lattice generators, one computes a basis of the lattice spanned by the generators. The second problem refers to that given a basis of a lattice, one finds some good basis of this lattice, such as either the basis vectors have short length or the first several vectors form a small volume.The two computational problems have a close relationship and cross each other:lattice basis reduction is based on the promise that we have computed some basis; computing bases also occurs in the local process of reducing bases, and the reduction methods with appropriate modification can be used to find bases.As basic topics, these two problems have important and extensive applications. For example, basis Algorithms are very useful in finding multiplicative relations between units of algebraic number fields and computing their fundamental units [1–3]; lattice basis reduction is a strong toolbox for the cryptanalyst [4]. Therefore, it is of important theoretical value and practical significance to study these topics.In this dissertation, we first study systematically the algorithms for computing bases.The previous basis algorithms are not perfect: if the algorithm can output a basis with linear bound in length, then the best known time bound due to Nguyen and Stehl′e [5]is quadratic with respect to log ‖B0‖, where B0∈ Zm×ndenote the input matrix; if the algorithm has quasi-linear complexity with respect to log ‖B0‖, then it outputs a “big”basis, that is, the output basis has super-linear bound in length, which will result in the expensive cost in further basis reduction.By introducing new notions and new ideas, such as Euclid-swap, regular system,loose-reduction, blockwise-swap and so on, we obtain three quasi-linear basis algorithms whose output basis has linear bound in length. Under the assumption of standard integer and matrix multiplication, two of our algorithms have natural time bound O(mn4(log n +log ‖B0‖)2). Besides, we apply our basis algorithms to extending a primitive set into a lattice basis, in which the time is still quasi-linear and the output basis has linear bound in length. The work in this part is taken from my joint paper with Professor Phong Q.Nguyen in [6].Secondly, we discuss the properties of slide-reduced basis. Gama-Nguyen slide reduction algorithm [7] is currently the best SVP approximation algorithm in theory,which is essentially an algorithmic version of the classical Mordell’s inequality [8].By generalizing Schnorr’s approach [9], we prove the upper and lower bounds for the ratios ‖b*i‖/λi(L) and ‖bi‖/λi(L), where(b1, · · ·, bn) is a slide-reduced basis andλ1(L), · · ·, λn(L) denote the successive minima of the lattice L. That is, we characterise the reducedness of slide-reduced bases. The work in this part is taken from my papers[10,11].The third part of our work is to study algorithms for approximately solving the smallest volume problem [12,13]. We present a higher-dimensional generalization of GamaNguyen slide reduction algorithm [7] for approximating the shortest vector problem in a lattice. This generalization approximately solves the smallest volume problem by using a subroutine solving the exact problem in low dimension, such as the Dadush-Micciancio algorithm [13]. Moreover, our approximation factor corresponds to a new and natural inequality on Rankin’s constant. Our work here can be viewed as the continuation of Mordell’s inequality and Gama-Nguyen slide reduction algorithm. The work in this part is taken from my joint paper with Professor Phong Q. Nguyen in [14].