An LLL-reduction algorithm with quasi-linear time complexity, extended abstract

DOI10.1145/1993636.1993691MaRDI QIDQ5419110zbMATH OpenOpenAlexFDO

Authors Andrew Novocin, Damien Stehlé, Gilles Villard

Publication date 5 June 2014

Published in Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1993636.1993691

zbMATH Keywords

Euclidean latticeLLL lattice basis reduction

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• An LLL algorithm with quadratic complexity
• A hierarchy of polynomial time lattice basis reduction algorithms
• Faster LLL-type Reduction of Lattice Bases
• Fast LLL-type lattice reduction
• scientific article; zbMATH DE number 1852137

Cited in

(21)

• On the computation of the HNF of a module over the ring of integers of a number field
• Fast reduction of algebraic lattices over cyclotomic fields
• Revisiting orthogonal lattice attacks on approximate common divisor problems
• On the quantum complexity of the continuous hidden subgroup problem
• Towards faster polynomial-time lattice reduction
• Storage efficient algorithm for Hermite normal form using LLL
• Bounding basis reduction properties
• Analysis of the upper bound on the complexity of LLL algorithm
• Perturbation analysis of the QR factor R in the context of LLL lattice basis reduction
• PotLLL: a polynomial time version of LLL with deep insertions
• On the modular inversion hidden number problem
• LLL for ideal lattices: re-evaluation of the security of Gentry-Halevi's FHE scheme
• Constructing totally p-adic numbers of small height
• A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation
• Deterministic factoring with oracles
• Fast practical lattice reduction through iterated compression
• Factoring sparse polynomials fast
• An experimental comparison of some LLL-type lattice basis reduction algorithms
• Towards a modern LLL implementation
• Modular polynomials on Hilbert surfaces
• Optimal systems of fundamental \(S\)-units for LLL-reduction

This page was built for publication: An LLL-reduction algorithm with quasi-linear time complexity, extended abstract

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