ON PAIRWISE GAUSSIAN BASES AND LLL ALGORITHM FOR THREE DIMENSIONAL LATTICES

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

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)1047-1065
Number of pages19
JournalJournal of the Korean Mathematical Society
Volume59
Issue number6
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'ON PAIRWISE GAUSSIAN BASES AND LLL ALGORITHM FOR THREE DIMENSIONAL LATTICES'. Together they form a unique fingerprint.

Cite this