The construction of greedy SVP LLL algorithm

Abstract

LLL algorithm is an algorithm used to compute the approximation of the shortest nonzero vector in a basis of lattice. Terms of reduction size and the exchanging process are the important steps in the LLL algorithm. In 1994, Schnoor and Euchner modified this LLL algorithm which later named LLL Deep insertion algorithm, where the exchanging proses in this algorithm scheme was comparing the projection in the orthogonal complement after done a certain vector reduction. This paper provides a new variant of LLL algorithm which is named Greedy SVP LLL algorithm, that is, purely comparing the-b j length (norm) of lattice vector with the-b length of lattice vector, for i = 1,2,2,...,j - 1, along with the vector insertion process conducted greedily. Thereafter, the calculation of the number of operation and testing for all three algoritms are conducted experimentally.