Storage efficient algorithm for Hermite normal form using LLL

DOI10.1016/j.laa.2020.12.022zbMath1473.15041OpenAlexW3115251311MaRDI QIDQ2229458

Hyang-Sook Lee, Gook Hwa Cho, Yoonjeong Kim, Seongan Lim

Publication date: 17 February 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2020.12.022

zbMATH Keywords

Hermite normal formLLL algorithm

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Matrices of integers (15B36) Matrices, determinants in number theory (11C20)

Cites Work

• Generating shorter bases for hard random lattices
• Probabilistic analyses of the plain multiple gcd algorithm
• Fast computation of Hermite normal forms of random integer matrices
• Factoring polynomials with rational coefficients
• A linear space algorithm for computing the hermite normal form
• Hermite Normal Form Computation Using Modulo Determinant Arithmetic
• Extended GCD and Hermite Normal Form Algorithms via Lattice Basis Reduction
• Short Bases of Lattices over Number Fields
• Two Fast Parallel GCD Algorithms of Many Integers
• Computing Hermite Normal Form Faster via Solving System of Linear Equations
• An LLL-reduction algorithm with quasi-linear time complexity
• An Introduction to Mathematical Cryptography
• Algorithmic Number Theory
• Unnamed Item
• Unnamed Item