Title | ||
---|---|---|
A Parametric Version Of Lll And Some Consequences: Parametric Shortest And Closest Vector Problems |
Abstract | ||
---|---|---|
Given a parametric lattice with a basis given by polynomials in Z[t], we give an algorithm to construct an LLL-reduced basis whose elements are eventually quasi-polynomial in t: that is, they are given by formulas that are piecewise polynomial in t (for sufficiently large t), such that each piece is given by a congruence class modulo a period. As a consequence, we show that there are parametric solutions of the shortest vector problem and closest vector problem that are also eventually quasi-polynomial in t. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1137/20M1327422 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
lattices, LLL algorithm, shortest vector problem, parametric lattices | Journal | 34 |
Issue | ISSN | Citations |
4 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tristram Bogart | 1 | 13 | 3.54 |
John Goodrick | 2 | 26 | 7.57 |
Kevin M. Woods | 3 | 25 | 6.04 |