# Journal of theKorean Mathematical SocietyJKMS

ISSN(Print) 0304-9914 ISSN(Online) 2234-3008

## Article

HOME ALL ARTICLES View

J. Korean Math. Soc. 2022; 59(6): 1047-1065

Online first article October 26, 2022      Printed November 1, 2022

https://doi.org/10.4134/JKMS.j210496

## On Pairwise Gaussian bases and LLL algorithm for three dimensional lattices

Kitae Kim, Hyang-Sook Lee, Seongan Lim, Jeongeun Park, Ikkwon Yie

Inha University; Ewha Womans University; Inha University; KU Leuven; Inha University

### 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\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).