N-Dimensional LLL Reduction Algorithm with Pivoted Reflection
The Lenstra-Lenstra-Lovász (LLL) lattice reduction algorithm and many of its variants have been widely used by cryptography, multiple-input-multiple-output (MIMO) communication systems and carrier phase positioning in global navigation satellite system (GNSS) to solve the integer least squares (ILS)...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-01-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1424-8220/18/1/283 |
| _version_ | 1828136301998637056 |
|---|---|
| author | Zhongliang Deng Di Zhu Lu Yin |
| author_facet | Zhongliang Deng Di Zhu Lu Yin |
| author_sort | Zhongliang Deng |
| collection | DOAJ |
| description | The Lenstra-Lenstra-Lovász (LLL) lattice reduction algorithm and many of its variants have been widely used by cryptography, multiple-input-multiple-output (MIMO) communication systems and carrier phase positioning in global navigation satellite system (GNSS) to solve the integer least squares (ILS) problem. In this paper, we propose an n-dimensional LLL reduction algorithm (n-LLL), expanding the Lovász condition in LLL algorithm to n-dimensional space in order to obtain a further reduced basis. We also introduce pivoted Householder reflection into the algorithm to optimize the reduction time. For an m-order positive definite matrix, analysis shows that the n-LLL reduction algorithm will converge within finite steps and always produce better results than the original LLL reduction algorithm with n > 2. The simulations clearly prove that n-LLL is better than the original LLL in reducing the condition number of an ill-conditioned input matrix with 39% improvement on average for typical cases, which can significantly reduce the searching space for solving ILS problem. The simulation results also show that the pivoted reflection has significantly declined the number of swaps in the algorithm by 57%, making n-LLL a more practical reduction algorithm. |
| first_indexed | 2024-04-11T18:01:45Z |
| format | Article |
| id | doaj.art-41d2568b343b4074958344f57ae12cf5 |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-04-11T18:01:45Z |
| publishDate | 2018-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-41d2568b343b4074958344f57ae12cf52022-12-22T04:10:27ZengMDPI AGSensors1424-82202018-01-0118128310.3390/s18010283s18010283N-Dimensional LLL Reduction Algorithm with Pivoted ReflectionZhongliang Deng0Di Zhu1Lu Yin2School of Electronic Engineering, Beijing University of Posts and Telecommunications, No. 10 Xitucheng Road, Beijing 100876, ChinaSchool of Electronic Engineering, Beijing University of Posts and Telecommunications, No. 10 Xitucheng Road, Beijing 100876, ChinaSchool of Electronic Engineering, Beijing University of Posts and Telecommunications, No. 10 Xitucheng Road, Beijing 100876, ChinaThe Lenstra-Lenstra-Lovász (LLL) lattice reduction algorithm and many of its variants have been widely used by cryptography, multiple-input-multiple-output (MIMO) communication systems and carrier phase positioning in global navigation satellite system (GNSS) to solve the integer least squares (ILS) problem. In this paper, we propose an n-dimensional LLL reduction algorithm (n-LLL), expanding the Lovász condition in LLL algorithm to n-dimensional space in order to obtain a further reduced basis. We also introduce pivoted Householder reflection into the algorithm to optimize the reduction time. For an m-order positive definite matrix, analysis shows that the n-LLL reduction algorithm will converge within finite steps and always produce better results than the original LLL reduction algorithm with n > 2. The simulations clearly prove that n-LLL is better than the original LLL in reducing the condition number of an ill-conditioned input matrix with 39% improvement on average for typical cases, which can significantly reduce the searching space for solving ILS problem. The simulation results also show that the pivoted reflection has significantly declined the number of swaps in the algorithm by 57%, making n-LLL a more practical reduction algorithm.http://www.mdpi.com/1424-8220/18/1/283LLL reductionpivoted reflectioninteger least squares (ILS)global navigation satellite system (GNSS) |
| spellingShingle | Zhongliang Deng Di Zhu Lu Yin N-Dimensional LLL Reduction Algorithm with Pivoted Reflection Sensors LLL reduction pivoted reflection integer least squares (ILS) global navigation satellite system (GNSS) |
| title | N-Dimensional LLL Reduction Algorithm with Pivoted Reflection |
| title_full | N-Dimensional LLL Reduction Algorithm with Pivoted Reflection |
| title_fullStr | N-Dimensional LLL Reduction Algorithm with Pivoted Reflection |
| title_full_unstemmed | N-Dimensional LLL Reduction Algorithm with Pivoted Reflection |
| title_short | N-Dimensional LLL Reduction Algorithm with Pivoted Reflection |
| title_sort | n dimensional lll reduction algorithm with pivoted reflection |
| topic | LLL reduction pivoted reflection integer least squares (ILS) global navigation satellite system (GNSS) |
| url | http://www.mdpi.com/1424-8220/18/1/283 |
| work_keys_str_mv | AT zhongliangdeng ndimensionallllreductionalgorithmwithpivotedreflection AT dizhu ndimensionallllreductionalgorithmwithpivotedreflection AT luyin ndimensionallllreductionalgorithmwithpivotedreflection |