Random lattices, threshold phenomena and efficient reduction algorithms.

DOI10.1016/S0304-3975(01)00251-1zbMath1061.11069MaRDI QIDQ1853481

Ali Akhavi

Publication date: 21 January 2003

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Combinatorial probability (60C05) Number-theoretic algorithms; complexity (11Y16)

Related Items

Fast LLL-type lattice reduction ⋮ Parallel Cholesky-based reduction for the weighted integer least squares problem ⋮ Speeding-Up Lattice Reduction with Random Projections (Extended Abstract) ⋮ On the reduction of a random basis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring polynomials and the knapsack problem
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Lattice reduction: a toolbox for the cryptoanalyst
• An upper bound on the average number of iterations of the LLL algorithm
• La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász
• Integer Programming with a Fixed Number of Variables
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Minkowski Reduction of Integral Matrices
• On the Asymptotic Evaluation of a Class of Multiple Integrals Involving a Parameter