The LLL algorithm using fast givens
Wen Zhang, Yimin Wei, Sanzheng Qiao · IEEE Asia-Pacific Conference on Synthetic Aperture Radar · 2011
1 Introduction The LLL algorithm originated from Lenstra, Lenstra, and L. Lovasz [3] is a lattice basis reduction method. The complexity of the problem of lattice basis reduction is know to be nonpolynomial in general. It is shown in [3] that their lattice basis reduction algorithm has polynomial complexity when the basis vectors are integer or rational. In their paper, the basis reduction algorithm is used to develop the first polynomial time algorithm for factorizing polynomials with rational coefficients. Besides, the LLL algorithm has been widely used in many fields of computer science and mathematics, particularly in cryptology and communications [6].