Block Reduced Lattice Bases and Successive Minima

DOI10.1017/S0963548300001371zbMath0845.11025MaRDI QIDQ4325334

Claus Peter Schnorr

Publication date: 30 March 1995

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

latticessuccessive minimainteger programming problemsblock reduced basesconstruction of a nearby lattice pointcritical block reduced bases

Mathematics Subject Classification ID

Integer programming (90C10) Number-theoretic algorithms; complexity (11Y16) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Related Items

Bounding basis reduction properties, Towards faster polynomial-time lattice reduction, A Tale of Three Signatures: Practical Attack of ECDSA with wNAF, Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes, Unnamed Item, PotLLL: a polynomial time version of LLL with deep insertions, Explicit Hard Instances of the Shortest Vector Problem, An optimal, stable continued fraction algorithm for arbitrary dimension, Non-standard approaches to integer programming, Sampling methods for shortest vectors, closest vectors and successive minima, Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes, A new parallel lattice reduction algorithm for BKZ reduced bases, SLIDE REDUCTION, SUCCESSIVE MINIMA AND SEVERAL APPLICATIONS

Cites Work

• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• On Lovász' lattice reduction and the nearest lattice point problem
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Improved low-density subset sum algorithms
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming