ON PAIRWISE GAUSSIAN BASES AND LLL ALGORITHM FOR THREE DIMENSIONAL LATTICES
- 주제(키워드) Lattice , pairwise-Gaussian basis , lattice basis reduction , LLL
- 주제(기타) Mathematics, Applied; Mathematics
- 설명문(일반) [Kim, Kitae; Lim, Seongan; Yie, Ikkwon] Inha Univ, Dept Math, Incheon 22212, South Korea; [Lee, Hyang-Sook] Ewha Womans Univ, Dept Math, Seoul 03760, South Korea; [Park, Jeongeun] Katholieke Univ Leuven, COSIC, Leuven, Belgium
- 관리정보기술 faculty
- 등재 SCIE, SCOPUS, KCI등재
- 발행기관 KOREAN MATHEMATICAL SOC
- 발행년도 2022
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000203111
- 본문언어 영어
- Published As https://doi.org/10.4134/JKMS.j210496
초록/요약
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 is an element of {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 delta >= 0.9, we prove that LLL(delta) 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.
more