Algorithms to construct Minkowski reduced and Hermite reduced lattice bases

DOI10.1016/0304-3975(85)90067-2zbMath0601.68034OpenAlexW2057728026MaRDI QIDQ1081304

Bettina Helfrich

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90067-2

zbMATH Keywords

basis reductionclosest lattice point

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Related Items

A hierarchy of polynomial time lattice basis reduction algorithms, Scalable revocable identity-based signature over lattices in the standard model, A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors, Finding a shortest vector in a two-dimensional lattice modulo m, Efficient computation of multidimensional theta functions, New orthogonality criterion for shortest vector of lattices and its applications, Greedy algorithm computing Minkowski reduced lattice bases with quadratic bit complexity of input vectors, Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems, A variational principle in the parametric geometry of numbers, On lattice-based algebraic feedback shift registers synthesis for multisequences, Computing theta functions in quasi-linear time in genus two and above, Sieve algorithms for the shortest vector problem are practical, Algorithms for the Shortest and Closest Lattice Vector Problems, Geodesic continued fractions and LLL, La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász, Fast LLL-type lattice reduction, A Digital Signature Scheme Based on CVP  ∞, Parallel Cholesky-based reduction for the weighted integer least squares problem, Improvements in the analysis of Kannan's CVP algorithm, Sampling methods for shortest vectors, closest vectors and successive minima, Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes

Cites Work

• On Lovász' lattice reduction and the nearest lattice point problem
• Factoring polynomials with rational coefficients
• An Introduction to the Geometry of Numbers
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Solving low-density subset sum problems
• Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
• Worst-case complexity bounds for algorithms in the theory of integral quadratic forms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item