LLL reducing with the most significant bits. (English) Zbl 1325.68298
Nabeshima, Katsusuke (ed.), Proceedings of the 39th international symposium on symbolic and algebraic computation, ISSAC 2014, Kobe, Japan, July 23–25, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2501-1). 367-374 (2014).
MSC:
| 68W30 | Symbolic computation and algebraic computation |
| 11H06 | Lattices and convex bodies (number-theoretic aspects) |
| 11Y16 | Number-theoretic algorithms; complexity |
Software:
JordanReferences:
| [1] | J. Bi, J.-S. Coron, J.-C. Faugère, P. Nguyen, G. Renault, and R. Zeitoun. Rounding and chaining LLL: Finding faster small roots of univariate polynomial congruences. In Proc. PKC’14, Buenos Aires, Argentina, LNCS 8383, 160-168. Springer, 2014. |
| [2] | J. Buchmann. Reducing Lattice Bases by Means of Approximations. In Proc. ANTS, LNCS 877, 160-168. Springer, 1994. · Zbl 0834.11065 |
| [3] | X.-W. Chang and C. C. Paige. Componentwise perturbation analyses for the QR factorization. Numer. Math., 88:319-345, 2001. · Zbl 0989.65049 |
| [4] | X.-W. Chang, D. Stehlé, and G. Villard. Perturbation analysis of the QR factor R in the context of LLL lattice basis reduction. Math. Comp., 81(279):1487-1511, 2012. · Zbl 1260.11082 |
| [5] | H. Cohen. A Course in Computational Algebraic Number Theory, volume 138 of Graduate Texts in Mathematics. Springer, Berlin, 1996. |
| [6] | N. Higham. Accuracy and Stability of Numerical Algorithms. SIAM, 2nd edition, 2002. · Zbl 1011.65010 |
| [7] | M. van Hoeij and A. Novocin. Gradual sub-lattice reduction and a new complexity for factoring polynomials. Algorithmica, 63(3):616-633, 2012. Preliminary version: Proc. LATIN, 539-553, 2010. 10.1007/978-3-642-12200-2_47 · Zbl 1191.11035 |
| [8] | E. Kaltofen. On the complexity of finding short vectors in integer lattices computer algebra. In Proc. EUROCAL, LNCS 162, 236-244. Springer, 1983. · Zbl 0546.68022 |
| [9] | B. A. Lamacchia. Basis reduction algorithms and subset sum problems. Technical report, SM thesis, Massachusetts Inst. Technol, 1991. |
| [10] | A. Lenstra, H. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261(4):515-534, 1982. · Zbl 0488.12001 |
| [11] | I. Morel, D. Stehlé, and G. Villard. From an LLL-reduced basis to another. ACM Commun. Comput. Algebra, 42(3):142-143, February 2009. ISSAC’08 poster. 10.1145/1504347.1504358 |
| [12] | I. Morel, D. Stehlé, and G. Villard. H-LLL: Using Householder inside LLL. In Proc. ISSAC, Seoul, Republic of Korea, 271-278. ACM, 2009. 10.1145/1576702.1576740 |
| [13] | H. Najafi, M. Jafari, and M.-O. Damen. On adaptive lattice reduction of correlated fading channels. IEEE Trans. Commun., 59.(5):1224-1227, 2011. |
| [14] | P. Nguyen and D. Stehlé. An LLL algorithm with quadratic complexity. SIAM J. Comput., 39(3):874-903, 2009. Preliminary version: Proc. EUROCRYPT, LNCS 3494, 215-233, 2005. 10.1137/070705702 · Zbl 1214.11139 |
| [15] | A. Novocin, D. Stehlé, and G. Villard. An LLL-reduction algorithm with quasi-linear time complexity: extended abstract. In Proc. STOC, San Jose, USA, 403-412. ACM, 2011. 10.1145/1993636.1993691 · Zbl 1288.68294 |
| [16] | A. Schönhage. Factorization of univariate integer polynomials by Diophantine approximation and an improved basis reduction algorithm. In Proceedings of ICALP, LNCS 172, 436-447. Springer, 1984. · Zbl 0569.68030 |
| [17] | A. van der Sluis. Condition numbers and equilibration of matrices. Numer. Math., 14:14-23, 1969. · Zbl 0182.48906 |
| [18] | A. Storjohann. The shifted number system for fast linear algebra on integer matrices. J. Compl., 21(4):609-650, 2005. 10.1016/j.jco.2005.04.002 · Zbl 1101.68045 |
| [19] | H. Zha. A componentwise perturbation analysis of the QR decomposition. SIAM J. Matrix Anal. Appl., 14(4):1124-1131, 1993. 10.1137/0614076 · Zbl 0787.65014 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
