An analysis of Seysen's lattice reduction algorithm

作者：Zhang Wei; Arnold Felix; Ma Xiaoli^*

来源：Signal Processing, 2008, 88(10): 2573-2577.

DOI：10.1016/j.sigpro.2008.04.008

• lattice reduction
• Seysen's algorithm
• Gaussian reduction
• the LLL algorithm

Lattice reduction (LR) techniques have been adopted to improve the performance and/or reduce the complexity in communications and cryptography. So far, the LLL algorithm has been considered almost exclusively for LR. In this paper, we focus on Seysen's algorithm to perform LR. We show that for a lattice in two dimensions, Seysen's algorithm gives the same reduced basis as the well-known Gaussian reduction algorithm (Lip to Signs). Furthermore, we prove that the Seysen's metric is upper bounded for lattices ill two dimensions after LR with Seysen's algorithm. Finally, we relate Seysen's metric to the orthogonality deficiency for general cases. Published by Elsevier B.V.

• 出版日期2008-10