The LLL algorithm using fast givens

1 Introduction: The LLL algorithm originated from Lenstra, Lenstra, and L. Lovász [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]. © 2011 KIEES.