Abstract | ||
---|---|---|
The algorithmic facet of euclidean lattices is a frequent to ol in computer science and mathematics. It mainly relies on the LLL reduction, making w orthwile efficiency improvements. Schnorr proved that the LLL algorithm can be speeded up if one computes approximations to the underlying Gram-Schmidt orthogonalisations. Without approximations, these computations dominate the cost of the reduction. Recently, classical too ls from the field of numerical anal- ysis have been revisited and improved in order to strengthenSchnorr's approach, and further reducing the costs. We describe these developments, and sho w especially how floating-point computations may be introduced at various levels in the redu ction process. |
Year | DOI | Venue |
---|---|---|
2010 | 10.3166/tsi.29.115-144 | Technique et Science Informatiques |
Keywords | Field | DocType |
gram-s chmidt orthogonalisation,floating-point arithmetic,mots-clés : réduction de réseau euclidien,analyse de perturbation. keywords: lattice reduction,arithmétique flottante,perturbation analysis.,lll,gram-schmidt orthogonalisation,orthogonalisation de gram-schmidt,analyse de perturbation. keywords:lattice reduction | Software tool,Perturbation method,Computer science,Algorithm,Humanities,Distributed computing | Journal |
Volume | Issue | Citations |
29 | 1 | 0 |
PageRank | References | Authors |
0.34 | 24 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ivan Morel | 1 | 3 | 0.76 |
Damien Stehlé | 2 | 1269 | 73.95 |
Gilles Villard | 3 | 565 | 48.04 |