Fast LLL-type lattice reduction
| Autor: | Claus-Peter Schnorr |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Discrete mathematics
Local LLL-reduction Floating point QR-decomposition Integer lattice Floating point errors QR decomposition Theoretical Computer Science Computer Science Applications Householder transformation Length defect SLLL-reduction Segments Computational Theory and Mathematics Householder reflection Iterated function Lattice (order) Factorization of polynomials LLL-reduction Lattice reduction Arithmetic Mathematics Information Systems |
| Zdroj: | Information and Computation. 204(1):1-25 |
| ISSN: | 0890-5401 |
| DOI: | 10.1016/j.ic.2005.04.004 |
| Popis: | We modify the concept of LLL-reduction of lattice bases in the sense of Lenstra, Lenstra, Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982) 515-534 towards a faster reduction algorithm. We organize LLL-reduction in segments of the basis. Our SLLL-bases approximate the successive minima of the lattice in nearly the same way as LLL-bases. For integer lattices of dimension n given by a basis of length 2^O^(^n^), SLLL-reduction runs in O(n^5^ ^+^@e) bit operations for every @e>0, compared to O(n^7^ ^+^@e) for the original LLL and to O(n^6^ ^+^@e) for the LLL-algorithms of Schnorr, A more efficient algorithm for lattice reduction, Journal of Algorithm, 9 (1988) 47-62 and Storjohann, Faster Algorithms for Integer Lattice Basis Reduction. TR 249, Swiss Federal Institute of Technology, ETH-Zurich, Department of Computer Science, Zurich, Switzerland, July 1996. We present an even faster algorithm for SLLL-reduction via iterated subsegments running in O(n^3log n) arithmetic steps. Householder reflections are shown to provide better accuracy than Gram-Schmidt for orthogonalizing LLL-bases in floating point arithmetic. . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect