scientific article; zbMATH DE number 3870586

From MaRDI portal
Publication:3336683





[For the entire collection see Zbl 0532.00010.] The paper presents a refined analysis of the short vector construction in integral lattices by \textit{A. K. Lenstra, H. W. Lenstra jun.} and \textit{L. Lovász} [Math. Ann. 261, 515-534 (1982; Zbl 0488.12001)]. This analysis improves the exponent of the asymptotical running-time by one, in case classical integer arithmetic is used. Another improvement is achieved by performing the vector operations modulo a sufficiently large integer. The latter is strongly suggested for implementations of the algorithm. Work on improving the algorithm when it is applied to lattices arising from rational polynomial factorization is reported by \textit{A. Schönhage} [Lect. Notes Comput. Sci. 172, 436-447 (1984)] and on improving the quality of the approximation by \textit{C. P. Schnorr} (manuscript, 1984).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3336683)