KMS Chongqing Institute of Green and Intelligent Technology, CAS
Computing an LLL-reduced basis of the orthogonal lattice | |
Chen, Jingwei1; Stehlé, Damien2; Villard, Gilles2 | |
2018 | |
摘要 | As a typical application, the Lenstra-Lenstra-Lovász 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. © 2018 Association for Computing Machinery. |
语种 | 英语 |
DOI | 10.1145/3208976.3209013 |
会议(录)名称 | 43rd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2018 |
页码 | 263-270 |
收录类别 | EI |
会议地点 | New York, NY, United states |
会议日期 | July 16, 2018 - July 19, 2018 |