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

Publisher Copyright:
© 2022 Korean Mathematical Society.

Keywords

  • LLL
  • Lattice
  • lattice basis reduction
  • 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