{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:38:48Z","timestamp":1760243928035,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2010,7,12]],"date-time":"2010-07-12T00:00:00Z","timestamp":1278892800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The algorithm of Lenstra, Lenstra, and Lov\u00e1sz (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\u2019s modular arithmetic approach with the segment-LLL approach to further improve the worst case complexity of the segment-LLL algorithms by a factor of n0.5.<\/jats:p>","DOI":"10.3390\/a3030224","type":"journal-article","created":{"date-parts":[[2010,7,12]],"date-time":"2010-07-12T11:37:07Z","timestamp":1278934627000},"page":"224-243","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Segment LLL Reduction of Lattice Bases Using Modular Arithmetic"],"prefix":"10.3390","volume":"3","author":[{"given":"Sanjay","family":"Mehrotra","sequence":"first","affiliation":[{"name":"Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208, USA"}]},{"given":"Zhifeng","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208, USA"}]}],"member":"1968","published-online":{"date-parts":[[2010,7,12]]},"reference":[{"key":"ref_1","unstructured":"Cassels, J.W.S. (1971). An Introduction to the Geometry of Numbers, Springer-Verlag."},{"key":"ref_2","unstructured":"Dwork, C. Lattices and their application to cryptography. Availible online: http:\/\/www.dim.uchile.cl\/m\u0303kiwi\/topicos\/00\/dwork-lattice-lectures.ps."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","article-title":"Integer programming with a fixed number of variables","volume":"8","author":"Lenstra","year":"1983","journal-title":"Math. Operat. Res."},{"key":"ref_4","unstructured":"Ajtai, M. (, January May). The shortest vector problem in L2 is NP-hard for randomized reductions. Proceedings of the 30th ACM Symposium on Theory of Computing, Dallas, TX, USA."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2008","DOI":"10.1137\/S0097539700373039","article-title":"The shortest vector in a lattice is hard to approximate to within some constant","volume":"30","author":"Micciancio","year":"2001","journal-title":"SIAM J. Comput."},{"key":"ref_6","unstructured":"van Emde Boas, P. (1981). Another NP-complete partition problem and the complexity of computing short vectors in lattices, University of Amsterdam. Technical report MI-UvA-81-04."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref_8","first-page":"436","article-title":"Factorization of univariate integer polynomials by diophantine approximation and improved lattice basis reduction algorithm","volume":"LNCS 172","year":"1984","journal-title":"Proceedings of 11th Colloquium Automata, Languages and Programming"},{"key":"ref_9","unstructured":"Kannan, R. (, January May). Improved algorithms for integer programming and related lattice problems. Proceedings of the 15th Annual ACM Symposium On Theory of Computing, Boston, MA, USA."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","article-title":"A hierarchy of polynomial time lattice basis reduction algorithms","volume":"53","author":"Schnorr","year":"1987","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","first-page":"81","article-title":"Segment LLL-reduction with floating point orthogonalization","volume":"2146","author":"Koy","year":"2001","journal-title":"LNCS"},{"key":"ref_12","first-page":"279","article-title":"Second letter to Jacobi","volume":"40","author":"Hermite","year":"1850","journal-title":"Crelle J."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0196-6774(88)90004-1","article-title":"A more efficient algorithm for lattice basis reduction","volume":"9","author":"Schnorr","year":"1988","journal-title":"J. Algorithms"},{"key":"ref_14","unstructured":"Storjohann, A. (1996). Faster Algorithms for Integer Lattice Basis Reduction, Swiss Federal Institute of Technology. Technical Report 249."},{"key":"ref_15","unstructured":"Schnorr, C.P. (1992). Block Korkin-Zolotarev Bases and Suceessive Minima, University of California at Berkley. Technical Report 92-063."},{"key":"ref_16","first-page":"215","article-title":"Floating-point LLL revisited","volume":"3494","author":"Nguyen","year":"2005","journal-title":"LCNS"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2005.04.004","article-title":"Fast LLL-type lattice reduction","volume":"204","author":"Schnorr","year":"2006","journal-title":"Inf. Comput."},{"key":"ref_18","unstructured":"Kaib, M., and Ritter, H. Block Reduction for Arbitrary Norms. Availible online: http:\/\/www.mi.informatik.uni-frankfurt.de\/research\/papers.html."},{"key":"ref_19","first-page":"754","article-title":"The generalized basis reduction algorithm","volume":"17","author":"Scarf","year":"1992","journal-title":"Math. Operat. Res."},{"key":"ref_20","first-page":"67","article-title":"Segment LLL-reduction of lattice bases","volume":"2146","author":"Koy","year":"2001","journal-title":"LNCS"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Geddes, K.O., Czapor, S.R., and Labahn, G. (1992). Algorithms for Computer Algebra, Kluwer.","DOI":"10.1007\/b102438"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Coppersmith","year":"1990","journal-title":"J. Symbol. Comput."},{"key":"ref_23","unstructured":"Stehl\u00e9, D. (2009). The LLL Algorithm, Springer-verlag. Chapter 5."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Strassen","year":"1971","journal-title":"Computing"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/3\/3\/224\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:02:54Z","timestamp":1760220174000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/3\/3\/224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,12]]},"references-count":24,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2010,9]]}},"alternative-id":["a3030224"],"URL":"https:\/\/doi.org\/10.3390\/a3030224","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2010,7,12]]}}}