Derivation Algorithm Of LLL Algorithm And Its Application

This paper is written in two parts. In the first part, we introduce LLL algorithm. In1982, A.K.Lenstra, H.W.Lenstra.Jr and L.Lovasz proposed the LLL algorithm. Because of the great efficient and simplicity, the LLL algorithm is considered to be one of the greatest breakthroughs about the NP problem as well as one of the most striking achievements in the field of algorithmics. Inspired by the LLL algorithm, many faster and more exact algorithm has been proposed, which led to breakthroughs in fields as diverse as computer algebra, cryptology, and algorithmic number theory. The first part of this paper reviews the idea of LLL algorithm, analyzes the complexity of the algorithm and introduces its variants and applications.In the second part we discuss the explicit factorization of3nr-th cyclotomic polynomials over finite field. We show that all irreducible factors of3nr-th cyclotomic polynomials can be obtained easily from irreducible factors of cyclotomic polynomials of small orders. In particular, we obtain the explicit factorization of3nr-th,3n·5-th and3n·7-th cyclotomic polynomials over finite fields.