Journal of the
Korean Mathematical Society JKMS

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\in\{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\ge 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.

Keywords: Lattice, pairwise-Gaussian basis, lattice basis reduction, LLL

MSC numbers: Primary 58B34, 58J42, 81T75

Supported by: 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).