Greedy algorithm computing Minkowski reduced lattice bases with quadratic bit complexity of input vectors

DOI10.1007/s11401-011-0680-1zbMath1271.11119OpenAlexW1998578520MaRDI QIDQ1938739

Liqing Xu, Hao Chen

Publication date: 22 February 2013

Published in: Chinese Annals of Mathematics. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11401-011-0680-1

zbMATH Keywords

latticesuccessive minimagreedy reductionMinkowski reduced bases

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Number-theoretic algorithms; complexity (11Y16) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
• Minkowski reduction region for positive quadratic forms in seven variables
• A theorem due to Sandakova concerning positive quadratic forms
• An LLL Algorithm with Quadratic Complexity
• A sieve algorithm for the shortest lattice vector problem
• Algorithmic Number Theory