Segment LLL reduction of lattice bases using modular arithmetic

Sanjay Mehrotra*, Zhifeng Li

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

The algorithm of Lenstra, Lenstra, and Lov́asz (LLL) transforms a given integer lattice basis into a reduced basis. Storjohann improved the worst case complexity of LLL algorithms by a factor of O(n) using modular arithmetic. Koy and Schnorr developed a segment-LLL basis reduction algorithm that generates lattice basis satisfying a weaker condition than the LLL reduced basis with O(n) improvement than the LLL algorithm. In this paper we combine Storjohann's modular arithmetic approach with the segment-LLL approach to further improve the worst case complexity of the segment-LLL algorithms by a factor of n 0:5.

Original languageEnglish (US)
Pages (from-to)224-243
Number of pages20
JournalAlgorithms
Volume3
Issue number3
DOIs
StatePublished - Sep 2010

Keywords

  • Fast matrix multiplication
  • LLL basis reduction
  • Lattice
  • Modular arithmetic
  • Reduced basis
  • Segments
  • Successive minima

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Numerical Analysis
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Segment LLL reduction of lattice bases using modular arithmetic'. Together they form a unique fingerprint.

  • Cite this