Abstract | ||
---|---|---|
As a typical application, the Lenstra-Lenstra-Lovasz lattice basis reduction algorithm (LLL) is used to compute a reduced basis of the orthogonal lattice for a given integer matrix, via reducing a special kind of lattice bases. With such bases in input, we propose a new technique for bounding from above the number of iterations required by the LLL algorithm. The main technical ingredient is a variant of the classical LLL potential, which could prove useful to understand the behavior of LLL for other families of input bases. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1145/3208976.3209013 | ISSAC'18: PROCEEDINGS OF THE 2018 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION |
Keywords | DocType | Volume |
Lattice basis reduction, LLL, orthogonal lattice, kernel lattice | Conference | abs/1805.03418 |
Citations | PageRank | References |
0 | 0.34 | 11 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jingwei Chen | 1 | 60 | 11.58 |
Damien Stehlé | 2 | 1269 | 73.95 |
Gilles Villard | 3 | 565 | 48.04 |