Computing an LLL-reduced basis of the orthogonal latice

DOI10.1145/3208976.3209013MaRDI QIDQ5120187zbMATH OpenOpenAlexFDO

Authors Jingwei Chen, Damien Stehlé, Gilles Villard

Publication date 9 September 2020

Published in Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.03418

zbMATH Keywords

kernel latticelattice basis reductionLLLorthogonal lattice

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Symbolic computation and algebraic computation (68W30)

Abstract: As a typical application, the Lenstra-Lenstra-Lovasz lattice basis reduction algorithm (LLL) is used to compute a reduced basis of the orthogonal lattice for a given integer matrix, via reducing a special kind of lattice bases. With such bases in input, we propose a new technique for bounding from above the number of iterations required by the LLL algorithm. The main technical ingredient is a variant of the classical LLL potential, which could prove useful to understand the behavior of LLL for other families of input bases.

Recommendations

• Fast LLL-type lattice reduction
• Faster LLL-type Reduction of Lattice Bases
• An LLL algorithm with quadratic complexity
• An upper bound on the average number of iterations of the LLL algorithm
• scientific article; zbMATH DE number 3958726

Cited in

(6)

• An upper bound on the average number of iterations of the LLL algorithm
• On abelian points of varieties intersecting subgroups in a torus
• scientific article; zbMATH DE number 1852138 (Why is no real title available?)
• Probabilistic Analyses of Lattice Reduction Algorithms
• Computing a lattice basis from a system of generating vectors
• Sieve algorithms for some orthogonal integer lattices

This page was built for publication: Computing an LLL-reduced basis of the orthogonal latice

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