Lattice basis reduction: Improved practical algorithms and solving subset sum problems

DOI10.1007/BF01581144zbMath0829.90099WikidataQ57567988 ScholiaQ57567988MaRDI QIDQ1340057

Claus Peter Schnorr, M. Euchner

Publication date: 11 December 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

subset sum; lattice basis reduction; block Korkin- Zolotarev reduction; floating point \(L^ 3\)-algorithm

Mathematics Subject Classification ID

90C10: Integer programming

90C27: Combinatorial optimization

11Y16: Number-theoretic algorithms; complexity

Related Items

Hermite’s Constant and Lattice Algorithms, Cryptographic Functions from Worst-Case Complexity Assumptions, Predicting Lattice Reduction, A public key cryptosystem based on three new provable problems, Another 80-dimensional extremal lattice, Topics in computational algebraic number theory, Approximate polynomial GCD over integers, Non-standard approaches to integer programming, Factoring polynomials and the knapsack problem, Probability method for cryptanalysis of general multivariate modular linear equation, Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures, Reduced complexity \(K\) -best sphere decoder design for MIMO systems, Solving market split problems with heuristical lattice reduction, Lattice-based algorithms for number partitioning in the hard phase, Low-density attack revisited, Cryptanalysis of a quadratic compact knapsack public-key cryptosystem, MLAMBDA: a modified LAMBDA method for integer least-squares estimation, Reduction of Smith normal form transformation matrices, A relative van Hoeij algorithm over number fields, Algorithms for the Shortest and Closest Lattice Vector Problems, Better Key Sizes (and Attacks) for LWE-Based Encryption, Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices, A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices, Sieve algorithms for the shortest vector problem are practical, Rigorous and Efficient Short Lattice Vectors Enumeration, Analysis of PSLQ, an integer relation finding algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Improved low-density subset sum algorithms
• Simultaneous reduction of a lattice basis and its reciprocal basis
• Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
• Integer Programming with a Fixed Number of Variables
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
• Solving low-density subset sum problems
• Minkowski's Convex Body Theorem and Integer Programming
• A knapsack-type public key cryptosystem based on arithmetic in finite fields
• The Generalized Basis Reduction Algorithm
• Factoring Integers and Computing Discrete Logarithms via Diophantine Approximation
• A more efficient algorithm for lattice basis reduction