Abstract | ||
---|---|---|
The algorithm of Lenstra, Lenstra, and Lovasz (LLL) transforms a given integer lattice basis into a reduced basis. Storjohann improved the worst case complexity of LLL algorithms by a factor of O (n) using modular arithmetic. Koy and Schnorr developed a segment-LLL basis reduction algorithm that generates lattice basis satisfying a weaker condition than the LLL reduced basis with O (n) improvement than the LLL algorithm. In this paper we combine Storjohann's modular arithmetic approach with the segment-LLL approach to further improve the worst case complexity of the segment-LLL algorithms by a factor of n(0.5). |
Year | DOI | Venue |
---|---|---|
2010 | 10.3390/a3030224 | ALGORITHMS |
Keywords | Field | DocType |
Lattice, LLL basis reduction, reduced basis, successive minima, segments, modular arithmetic, fast matrix multiplication | Discrete mathematics,Lattice (order),Modular arithmetic,Integer lattice,Worst-case complexity,Lattice reduction,Mathematics | Journal |
Volume | Issue | ISSN |
3 | 3 | 1999-4893 |
Citations | PageRank | References |
2 | 0.38 | 10 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sanjay Mehrotra | 1 | 521 | 77.18 |
ZhiFeng Li | 2 | 1073 | 55.45 |