Abstract
For two dimensional lattices, a Gaussian basis achieves all two successive minima. For dimension larger than two, constructing a pairwise Gaussian basis is useful to compute short vectors of the lattice. For three dimensional lattices, Semaev showed that one can convert a pairwise Gaussian basis to a basis achieving all three successive minima by one simple reduction. A pairwise Gaussian basis can be obtained from a given basis by executing Gauss algorithm for each pair of basis vectors repeatedly until it returns a pairwise Gaussian basis. In this article, we prove a necessary and sufficient condition for a pairwise Gaussian basis to achieve the first k successive minima for three dimensional lattices for each k ∈ {1, 2, 3} by modifying Semaev’s condition. Our condition directly checks whether a pairwise Gaussian basis contains the first k shortest independent vectors for three dimensional lattices. LLL is the most basic lattice basis reduction algorithm and we study how to use LLL to compute a pairwise Gaussian basis. For δ ≥ 0.9, we prove that LLL(δ) with an additional simple reduction turns any basis for a three dimensional lattice into a pairwise SV-reduced basis. By using this, we convert an LLL reduced basis to a pairwise Gaussian basis in a few simple reductions. Our result suggests that the LLL algorithm is quite effective to compute a basis with all three successive minima for three dimensional lattices.
Original language | English |
---|---|
Pages (from-to) | 1047-1065 |
Number of pages | 19 |
Journal | Journal of the Korean Mathematical Society |
Volume | 59 |
Issue number | 6 |
DOIs | |
State | Published - Nov 2022 |
Bibliographical note
Funding Information:Acknowledgments. Hyang-Sook Lee was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT) (No. NRF-2021R1A2C1094821) and partially supported by the Basic Science Research Program through the NRF funded by the Ministry of Education (Grant No. 2019R1A6A1A11051177). Seongan Lim was supported by the NRF of Korea (Grant Number: 2016R1D1A1B01008562).
Publisher Copyright:
© 2022 Korean Mathematical Society.
Keywords
- Lattice
- lattice basis reduction
- LLL
- pairwise-Gaussian basis