{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:59:57Z","timestamp":1760061597181},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,7]]},"DOI":"10.1007\/s00453-011-9500-y","type":"journal-article","created":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T16:13:49Z","timestamp":1298996029000},"page":"616-633","source":"Crossref","is-referenced-by-count":4,"title":["Gradual Sub-lattice Reduction and a New Complexity for\u00a0Factoring Polynomials"],"prefix":"10.1007","volume":"63","author":[{"given":"Mark","family":"van Hoeij","sequence":"first","affiliation":[]},{"given":"Andrew","family":"Novocin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,3,1]]},"reference":[{"key":"9500_CR1","first-page":"284","volume-title":"Proceedings of the 30th Symposium on the Theory of Computing (STOC 1998)","author":"M. Ajtai","year":"1998","unstructured":"Ajtai, M.: The shortest vector problem in l 2 is NP-hard for randomized reductions (extended abstract). In: Proceedings of the 30th Symposium on the Theory of Computing (STOC 1998), pp. 284\u2013293. ACM, New York (1998)"},{"issue":"1\u20133","key":"9500_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(02)00616-3","volume":"297","author":"A. Akhavi","year":"2003","unstructured":"Akhavi, A.: The optimal LLL algorithm is still polynomial in fixed dimension. Theor. Comput. Sci. 297(1\u20133), 3\u201323 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9500_CR3","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1016\/j.jsc.2003.09.003","volume":"37","author":"K. Belabas","year":"2004","unstructured":"Belabas, K.: A relative van Hoeij algorithm over number fields. J. Symb. Comput. 37(5), 641\u2013668 (2004)","journal-title":"J. Symb. Comput."},{"key":"9500_CR4","doi-asserted-by":"crossref","first-page":"15","DOI":"10.5802\/jtnb.655","volume":"21","author":"K. Belabas","year":"2009","unstructured":"Belabas, K., van Hoeij, M., Kl\u00fcners, J., Steel, A.: Factoring polynomials over global fields. J. Th\u00e9or. Nr. Bordx. 21, 15\u201339 (2009)","journal-title":"J. Th\u00e9or. Nr. Bordx."},{"key":"9500_CR5","unstructured":"Bright, C.: Vector rational number reconstruction. Master\u2019s thesis, University of Waterloo, 2009"},{"issue":"4","key":"9500_CR6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s001459900030","volume":"10","author":"D. Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J.\u00a0Cryptol. 10(4), 233\u2013260 (1997)","journal-title":"J.\u00a0Cryptol."},{"key":"9500_CR7","first-page":"235","volume-title":"Modern Computer Algebra","author":"J. Gathen von\u00a0zur","year":"2003","unstructured":"von\u00a0zur Gathen, J., Gerhardt, J.: Modern Computer Algebra, 2nd edn., pp. 235\u2013242, 432\u2013437. Cambridge University Press, Cambridge (2003)","edition":"2"},{"key":"9500_CR8","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1515\/form.2003.009","volume":"15","author":"D. Goldstein","year":"2003","unstructured":"Goldstein, D., Mayer, A.: On the equidistribution of Hecke points. Forum Math. 15, 165\u2013189 (2003)","journal-title":"Forum Math."},{"key":"9500_CR9","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/978-3-642-02295-1_6","volume-title":"The LLL Algorithm: Survey and Applications","author":"G. Hanrot","year":"2009","unstructured":"Hanrot, G.: LLL: a tool for effective Diophantine approximation. In: Nguyen, P.Q., Vall\u00e9e, B. (eds.) The LLL Algorithm: Survey and Applications, pp. 215\u2013264 (2009)"},{"key":"9500_CR10","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0022-314X(01)92763-5","volume":"95","author":"M. Hoeij Van","year":"2002","unstructured":"Van Hoeij, M.: Factoring polynomials and the knapsack problem. J. Number Theory 95, 167\u2013189 (2002)","journal-title":"J. Number Theory"},{"key":"9500_CR11","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1023\/A:1011214926272","volume":"23","author":"N.A. Howgrave-Graham","year":"2001","unstructured":"Howgrave-Graham, N.A., Smart, N.P.: Lattice attacks on digital signature schemes. Des. Codes Cryptogr. 23, 283\u2013290 (2001)","journal-title":"Des. Codes Cryptogr."},{"key":"9500_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/3-540-12868-9_107","volume-title":"Proceedings of European Conference on Computer Algebra 1983 EUROCAL\u201983","author":"E. Kaltofen","year":"1983","unstructured":"Kaltofen, E.: On the complexity of finding short vectors in integer lattices. In: Proceedings of European Conference on Computer Algebra 1983 EUROCAL\u201983. Lecture Notes in Computer Science, vol. 162, pp. 236\u2013244. Springer, Berlin (1983)"},{"key":"9500_CR13","first-page":"191","volume-title":"Proceedings of the 16th Symposium on the Theory of Computing (STOC 1984)","author":"R. Kannan","year":"1984","unstructured":"Kannan, R., Lenstra, A.K., Lov\u00e1sz, L.: Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. In: Proceedings of the 16th Symposium on the Theory of Computing (STOC 1984), pp. 191\u2013200. ACM, New York (1984)"},{"key":"9500_CR14","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W. Jr., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"9500_CR15","first-page":"37","volume-title":"Proceedings of the Third European Congress of Mathematics","author":"H.W. Lenstra Jr.","year":"2000","unstructured":"Lenstra, H.W. Jr.: Flags and lattice basis reduction. In: Proceedings of the Third European Congress of Mathematics, vol.\u00a01, pp. 37\u201351. Birkh\u00e4user, Basel (2000)"},{"key":"9500_CR16","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970203","volume-title":"An Algorithmic Theory of Numbers, Graphs and Convexity","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L.: An Algorithmic Theory of Numbers, Graphs and Convexity. CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, Philadelphia (1986)"},{"issue":"6","key":"9500_CR17","doi-asserted-by":"crossref","first-page":"2008","DOI":"10.1137\/S0097539700373039","volume":"30","author":"D. Micciancio","year":"2001","unstructured":"Micciancio, D.: The shortest vector problem is NP-hard to approximate to within some constant. SIAM J. Comput. 30(6), 2008\u20132035 (2001)","journal-title":"SIAM J. Comput."},{"key":"9500_CR18","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1145\/1576702.1576740","volume-title":"Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation (ISSAC\u201909)","author":"I. Morel","year":"2009","unstructured":"Morel, I., Stehl\u00e9, D., Villard, G.: H-LLL: using Householder inside LLL. In: Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation (ISSAC\u201909), pp. 271\u2013278. ACM, New York (2009)"},{"key":"9500_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/11426639_13","volume-title":"Proceedings of Eurocrypt 2005","author":"P.Q. Nguyen","year":"2005","unstructured":"Nguyen, P.Q., Stehl\u00e9, D.: Floating-point LLL revisited. In: Proceedings of Eurocrypt 2005. Lecture Notes in Computer Science, vol. 3494, pp. 215\u2013233. Springer, Berlin (2005)"},{"issue":"3","key":"9500_CR20","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1137\/070705702","volume":"39","author":"P.Q. Nguyen","year":"2009","unstructured":"Nguyen, P.Q., Stehl\u00e9, D.: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39(3), 874\u2013903 (2009)","journal-title":"SIAM J. Comput."},{"key":"9500_CR21","doi-asserted-by":"crossref","unstructured":"Novocin, A.: Factoring univariate polynomials over the rationals. PhD thesis, Florida State University, 2008","DOI":"10.1145\/1394042.1394092"},{"key":"9500_CR22","series-title":"Proceedings of Symposia in Applied Mathematics","first-page":"75","volume-title":"Cryptology and Computational Number Theory","author":"A.M. Odlyzko","year":"1990","unstructured":"Odlyzko, A.M.: The rise and fall of knapsack cryptosystems. In: Cryptology and Computational Number Theory. Proceedings of Symposia in Applied Mathematics, vol. 42, pp. 75\u201388. Am. Math. Soc., Providence (1990)"},{"issue":"1","key":"9500_CR23","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0196-6774(88)90004-1","volume":"9","author":"C.P. Schnorr","year":"1988","unstructured":"Schnorr, C.P.: A more efficient algorithm for lattice basis reduction. J. Algorithms 9(1), 47\u201362 (1988)","journal-title":"J. Algorithms"},{"key":"9500_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1007\/3-540-13345-3_40","volume-title":"Proceedings of the 1984 International Colloquium on Automata, Languages and Programming (ICALP 1984)","author":"A. Sch\u00f6nhage","year":"1984","unstructured":"Sch\u00f6nhage, A.: Factorization of univariate integer polynomials by Diophantine approximation and improved basis reduction algorithm. In: Proceedings of the 1984 International Colloquium on Automata, Languages and Programming (ICALP 1984). Lecture Notes in Computer Science, vol. 172, pp. 436\u2013447. Springer, Berlin (1984)"},{"key":"9500_CR25","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/978-3-642-02295-1_5","volume-title":"The LLL Algorithm: Survey and Applications","author":"D. Stehl\u00e9","year":"2009","unstructured":"Stehl\u00e9, D.: Floating-point LLL: theoretical and practical aspects. In: Nguyen, P.Q., Vall\u00e9e, B. (eds.) The LLL Algorithm: Survey and Applications, pp. 179\u2013194 (2009)"},{"key":"9500_CR26","unstructured":"Storjohann, A.: Faster algorithms for integer lattice basis reduction. Technical Report TR249, Swiss Federal Institute of Technology Z\u00fcrich, Department of Computer Science, 1996"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9500-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9500-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9500-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T18:39:23Z","timestamp":1560019163000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9500-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,1]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["9500"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9500-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,1]]}}}