Abstract | ||
---|---|---|
Let B be a basis of a Euclidean lattice, and B an approximation thereof. We give a sufficient condition on the closeness between B and B so that an LLL-reducing transformation U for B remains valid for B. Further, we analyse an efficient reduction algorithm when B is itself a small deformation of an LLL-reduced basis. Applications include speeding-up reduction by keeping only the most significant bits of B, reducing a basis that is only approximately known, and efficiently batching LLL reductions for closely related inputs. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1145/2608628.2608645 | ISSAC |
Keywords | Field | DocType |
algorithms,lll,numerical linear algebra,lattice basis reduction,numerical algorithms and problems,floating point arithmetic | Discrete mathematics,Combinatorics,Lattice (order),Closeness,Floating point,Euclidean geometry,Mathematics,Lattice reduction | Conference |
Citations | PageRank | References |
3 | 0.42 | 11 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Saruchi | 1 | 3 | 0.42 |
Ivan Morel | 2 | 3 | 0.76 |
Damien Stehlé | 3 | 1269 | 73.95 |
Gilles Villard | 4 | 565 | 48.04 |