Modified LLL algorithms.

详细信息   

• 作者：Zhou ; Tianyang.
• 学历：Master
• 年：2006
• 毕业院校：McGill University
• 专业：Computer Science.
• ISBN：9780494285411
• CBH：MR28541
• Country：Canada
• 语种：English
• FileSize：3426226
• Pages：93

文摘

Lattice basis reduction arises from many applications, such as cryptography, communications, GPS and so on. This thesis is concerned with the widely used LLL reduction. We cast it as a QRZ matrix factorization for real bases. Based on the matrix factorization, we first give the real version of the LLL algorithm (the original LLL algorithm is for integer bases). Then we propose three modified algorithms to improve the computational efficiency, while the reduced matrices satisfy the LLL-reduced criteria. The first modified algorithm, to be referred to as MLLLPIVOT, uses a block pivoting strategy. The second one, to be called MLLLINSERT, uses a greedy insertion strategy. The last one, to be called MLLLLAZY, uses a "lazy" size-reduction strategy. Extensive simulation results are given to show the improvements and different performance of the three algorithms. In addition, numerical stability of the LLL algorithm and the three modified algorithms is considered. The simulations indicate that on average the computational efficiency (measured by CPU time) of the four algorithms have the increasing order: LLL < MLLLPIVOT < MLLLINSERT < MLLLLAZY, and the four algorithms are backward numerically stable in most cases, and in some extreme cases, the numerical stability of these algorithms is in an opposite order. Furthermore, we also give the complexity analysis of LLL, MLLLINSERT and MLLLLAZY under the assumption of using exact arithmetic.