TY - JOUR
T1 - ON PAIRWISE GAUSSIAN BASES AND LLL ALGORITHM FOR THREE DIMENSIONAL LATTICES
AU - Kim, Kitae
AU - Lee, Hyang Sook
AU - Lim, Seongan
AU - Park, Jeongeun
AU - Yie, Ikkwon
N1 - 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.
PY - 2022/11
Y1 - 2022/11
N2 - 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.
AB - 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.
KW - Lattice
KW - lattice basis reduction
KW - LLL
KW - pairwise-Gaussian basis
UR - http://www.scopus.com/inward/record.url?scp=85141433365&partnerID=8YFLogxK
U2 - 10.4134/JKMS.j210496
DO - 10.4134/JKMS.j210496
M3 - Article
AN - SCOPUS:85141433365
SN - 0304-9914
VL - 59
SP - 1047
EP - 1065
JO - Journal of the Korean Mathematical Society
JF - Journal of the Korean Mathematical Society
IS - 6
ER -