Segment LLL reduction of lattice bases using modular arithmetic

DOI10.3390/A3030224MaRDI QIDQ1662551zbMATH OpenOpenAlexFDO

Authors Sanjay Mehrotra, Zhifeng Li

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a3030224

zbMATH Keywords

fast matrix multiplicationlatticeLLL basis reductionmodular arithmeticreduced basissegmentssuccessive minima

Mathematics Subject Classification ID

Matrices, determinants in number theory (11C20) Number-theoretic algorithms; complexity (11Y16) Numerical algorithms for computer arithmetic, etc. (65Y04) Data encryption (aspects in computer science) (68P25)

Review text

Summary: The algorithm of Lenstra, Lenstra, and Lovász (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}\).

Recommendations

• scientific article; zbMATH DE number 1852137
• A modification of the LLL reduction algorithm
• Fast LLL-type lattice reduction
• Progress on LLL and lattice reduction
• Faster LLL-type Reduction of Lattice Bases

Cites work

• A hierarchy of polynomial time lattice basis reduction algorithms
• A more efficient algorithm for lattice basis reduction
• Factoring polynomials with rational coefficients
• Fast LLL-type lattice reduction
• Fast multiplication of large numbers
• Floating-Point LLL Revisited
• Floating-Point LLL: Theoretical and Practical Aspects
• scientific article; zbMATH DE number 3909733 (Why is no real title available?)
• scientific article; zbMATH DE number 108109 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• scientific article; zbMATH DE number 1361466 (Why is no real title available?)
• scientific article; zbMATH DE number 1852137 (Why is no real title available?)
• scientific article; zbMATH DE number 1852138 (Why is no real title available?)
• scientific article; zbMATH DE number 3333393 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Matrix multiplication via arithmetic progressions
• The Generalized Basis Reduction Algorithm
• The shortest vector in a lattice is hard to approximate to within some constant

Cited in

(7)

• Fast LLL-type lattice reduction
• Faster LLL-type Reduction of Lattice Bases
• LLL reducing with the most significant bits
• scientific article; zbMATH DE number 1852137 (Why is no real title available?)
• scientific article; zbMATH DE number 1852138 (Why is no real title available?)
• Progress on LLL and lattice reduction
• Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices

This page was built for publication: Segment LLL reduction of lattice bases using modular arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662551)