{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T09:01:55Z","timestamp":1781168515400,"version":"3.54.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T00:00:00Z","timestamp":1748390400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T00:00:00Z","timestamp":1748390400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2026,7]]},"DOI":"10.1007\/s00200-025-00690-w","type":"journal-article","created":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T11:04:24Z","timestamp":1748430264000},"page":"853-877","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimizing the half-gcd algorithm"],"prefix":"10.1007","volume":"37","author":[{"given":"Joris","family":"van der Hoeven","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,5,28]]},"reference":[{"key":"690_CR1","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. In: Proceedings ACM STOC \u201988, pp. 301\u2013309. New York, NY, USA (1988)","DOI":"10.1145\/62212.62241"},{"key":"690_CR2","volume-title":"Algebraic Coding Theory","author":"ER Berlekamp","year":"1968","unstructured":"Berlekamp, E.R.: Algebraic Coding Theory. McGraw-Hill, New York (1968)"},{"key":"690_CR3","first-page":"325","volume-title":"Fast Multiplication and its Applications","author":"DJ Bernstein","year":"2008","unstructured":"Bernstein, D.J.: Fast Multiplication and its Applications, pp. 325\u2013384. Mathematical Sciences Research Institute Publications, Cambridge University Press, Cambridge (2008)"},{"key":"690_CR4","doi-asserted-by":"publisher","first-page":"340","DOI":"10.46586\/tches.v2019.i3.340-398","volume":"3","author":"DJ Bernstein","year":"2019","unstructured":"Bernstein, D.J., Yang, B.-Y.: Fast constant-time gcd computation and modular inversion. IACR Trans. Cryptogr. Hardw. Embed. Syst. 3, 340\u2013398 (2019)","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"issue":"3","key":"690_CR5","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0196-6774(80)90013-9","volume":"1","author":"RP Brent","year":"1980","unstructured":"Brent, R.P., Gustavson, F.G., Yun, D.Y.Y.: Fast solution of Toeplitz systems of equations and computation of Pad\u00e9 approximants. J. Algorithms 1(3), 259\u2013295 (1980)","journal-title":"J. Algorithms"},{"key":"690_CR6","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/BF01178683","volume":"28","author":"DG Cantor","year":"1991","unstructured":"Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inform. 28, 693\u2013701 (1991)","journal-title":"Acta Inform."},{"issue":"154","key":"690_CR7","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1090\/S0025-5718-1981-0606517-5","volume":"36","author":"DG Cantor","year":"1981","unstructured":"Cantor, D.G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Math. Comput. 36(154), 587\u2013592 (1981)","journal-title":"Math. Comput."},{"key":"690_CR8","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"JW Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, 297\u2013301 (1965)","journal-title":"Math. Comput."},{"key":"690_CR9","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1109\/TIT.1987.1057299","volume":"33","author":"JL Dornstetter","year":"1987","unstructured":"Dornstetter, J.L.: On the equivalence between Berlekamp\u2019s and Euclid\u2019s algorithms. IEEE Trans. Inf. Theory 33, 428\u2013431 (1987)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"690_CR10","doi-asserted-by":"crossref","unstructured":"Grenet, B., van der Hoeven, J., Lecerf, G.: Randomized root finding over finite fields using tangent Graeffe transforms. In: Proceedings ISSAC \u201915, pp. 197\u2013204. ACM: New York, NY, USA (2015)","DOI":"10.1145\/2755996.2756647"},{"key":"690_CR11","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/s00200-003-0144-2","volume":"14","author":"G Hanrot","year":"2004","unstructured":"Hanrot, G., Quercia, M., Zimmermann, P.: The middle product algorithm I. Speeding up the division and square root of power series. AAECC 14, 415\u2013438 (2004)","journal-title":"AAECC"},{"key":"690_CR12","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1090\/S0025-5718-2010-02392-0","volume":"80","author":"D Harvey","year":"2011","unstructured":"Harvey, D.: Faster algorithms for the square root and reciprocal of power series. Math. Comput. 80, 387\u2013394 (2011)","journal-title":"Math. Comput."},{"key":"690_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2019.03.004","volume":"54","author":"D Harvey","year":"2019","unstructured":"Harvey, D., van der Hoeven, J.: Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. J. Complex. 54, 101404 (2019)","journal-title":"J. Complex."},{"issue":"2","key":"690_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3505584","volume":"69","author":"D Harvey","year":"2022","unstructured":"Harvey, D., van der Hoeven, J.: Polynomial multiplication over finite fields in time $$O (n \\log n)$$. J. ACM 69(2), 1\u201340 (2022)","journal-title":"J. ACM"},{"key":"690_CR15","first-page":"595","volume":"7","author":"A Karatsuba","year":"1963","unstructured":"Karatsuba, A., Ofman, J.: Multiplication of multidigit numbers on automata. Sov. Phys. Dokl. 7, 595\u2013596 (1963)","journal-title":"Sov. Phys. Dokl."},{"key":"690_CR16","unstructured":"Knuth, D.E.: The analysis of algorithms. In: Actes du Congr\u00e8s International des Mathe\u00e9maticiens 1970, vol.\u00a03, pp. 269\u2013274. Gauthier-Villars (1971)"},{"key":"690_CR17","volume-title":"On the complexity of the Lickteig\u2013Roy subresultant algorithm","author":"G Lecerf","year":"2017","unstructured":"Lecerf, G.: On the complexity of the Lickteig\u2013Roy subresultant algorithm. CNRS & \u00c9cole Polyechnique, Palaiseau (2017)"},{"key":"690_CR18","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1080\/00029890.1938.11990797","volume":"45","author":"DH Lehmer","year":"1938","unstructured":"Lehmer, D.H.: Euclid\u2019s algorithm for large numbers. Amer. Math. Mon. 45, 227\u2013233 (1938)","journal-title":"Amer. Math. Mon."},{"key":"690_CR19","doi-asserted-by":"crossref","unstructured":"Lichtblau, D.: Half-GCD and fast rational recovery. In: Proceedings ISSAC \u201905, pp. 231\u2013236 (2005)","DOI":"10.1145\/1073884.1073917"},{"key":"690_CR20","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1109\/TIT.1969.1054260","volume":"15","author":"J Massey","year":"1969","unstructured":"Massey, J.: Shift-register synthesis and bch decoding. IEEE Trans. Inf. Theory 15, 122\u2013127 (1969)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"690_CR21","doi-asserted-by":"crossref","unstructured":"Moenck, R.: Fast computation of GCDs. In: Proceedings of the 5th ACM Annual Symposium on Theory of Computing, pp. 142\u2013171. ACM Press, New York (1973)","DOI":"10.1145\/800125.804045"},{"issue":"261","key":"690_CR22","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1090\/S0025-5718-07-02017-0","volume":"77","author":"N M\u00f6ller","year":"2008","unstructured":"M\u00f6ller, N.: On Sch\u00f6nhage\u2019s algorithm and subquadratic integer gcd computation. Math. Comput. 77(261), 589\u2013607 (2008)","journal-title":"Math. Comput."},{"key":"690_CR23","doi-asserted-by":"crossref","unstructured":"Morain, F.: Implementing the Thull\u2013Yap algorithm for computing Euclidean remainder sequences. In: Proceedings ISSAC \u201922, pp. 197\u2013205 (2022)","DOI":"10.1145\/3476446.3536188"},{"key":"690_CR24","first-page":"24","volume":"1","author":"R Prony","year":"1971","unstructured":"Prony, R.: Essai experimental et analytique sur les lois de la dilatabilite de fluides elastiques et sur celles da la force expansion de la vapeur de l\u2019alcool, a differentes temperatures. J. l\u2019Ecole Polytech. 1, 24\u201376 (1971)","journal-title":"J. l\u2019Ecole Polytech."},{"key":"690_CR25","doi-asserted-by":"crossref","unstructured":"Reischert, D.: Asymptotically fast computation of subresultants. In Proceedings ISSAC \u201997, pp. 233\u2013240 (1997)","DOI":"10.1145\/258726.258792"},{"issue":"2","key":"690_CR26","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF00289520","volume":"1","author":"A Sch\u00f6nhage","year":"1971","unstructured":"Sch\u00f6nhage, A.: Schnelle berechnung von kettenbruchentwicklungen. Acta Inform. 1(2), 139\u2013144 (1971)","journal-title":"Acta Inform."},{"key":"690_CR27","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/BF00289470","volume":"7","author":"A Sch\u00f6nhage","year":"1977","unstructured":"Sch\u00f6nhage, A.: Schnelle multiplikation von polynomen \u00fcber K\u00f6rpern der charakteristik 2. Acta Inform. 7, 395\u2013398 (1977)","journal-title":"Acta Inform."},{"key":"690_CR28","unstructured":"Shoup, V.: NTL: a library for doing number theory. www.shoup.net\/ntl (1996)"},{"key":"690_CR29","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-540-24847-7_31","volume-title":"Algorithmic Number Theory","author":"D Stehl\u00e9","year":"2004","unstructured":"Stehl\u00e9, D., Zimmermann, P.: A binary recursive gcd algorithm. In: Buell, D. (ed.) Algorithmic Number Theory, pp. 411\u2013425. Springer, Berlin, Heidelberg (2004)"},{"key":"690_CR30","unstructured":"Stevin, S.: L\u2019arithm\u00e9tique. Imprimerie de Christophle Plantin (1585)"},{"key":"690_CR31","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/BF02165411","volume":"13","author":"V Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13, 352\u2013356 (1969)","journal-title":"Numer. Math."},{"key":"690_CR32","doi-asserted-by":"crossref","unstructured":"Strassen, V.: The computational complexity of continued fractions. In: Proceeding of the 4th ACM Symposium on Symbolic and Algebraic Computation, pp. 51\u201367 (1981)","DOI":"10.1145\/800206.806371"},{"key":"690_CR33","unstructured":"Thull, K., Yap, C.K.: A unified approach to HGCD algorithms for polynomials and integers. https:\/\/cs.nyu.edu\/yap\/papers\/SYNOP.htm#hgcd"},{"issue":"2","key":"690_CR34","first-page":"714","volume":"4","author":"AL Toom","year":"1963","unstructured":"Toom, A.L.: The complexity of a scheme of functional elements realizing the multiplication of integers. Sov. Math. 4(2), 714\u2013716 (1963)","journal-title":"Sov. Math."},{"key":"690_CR35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065","volume-title":"Modern Computer Algebra","author":"J von zur Gathen","year":"2013","unstructured":"von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, New York, NY (2013)"},{"key":"690_CR36","doi-asserted-by":"crossref","unstructured":"van der Hoeven, J.: The truncated Fourier transform and applications. In: Proceedings ISSAC 2004, pp. 290\u2013296. University of Cantabria, Santander, Spain (2004)","DOI":"10.1145\/1005285.1005327"},{"key":"690_CR37","unstructured":"van\u00a0der Hoeven, J., Lecerf, G.: Implementing number theoretic transforms. Technical Report, HAL. https:\/\/hal.science\/hal-04841449 (2024)"},{"issue":"3","key":"690_CR38","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/3457341.3457342","volume":"54","author":"J van der Hoeven","year":"2021","unstructured":"van der Hoeven, J., Monagan, M.: Computing one billion roots using the tangent Graeffe method. ACM SIGSAM Commun. Comput. Algebra 54(3), 65\u201385 (2021)","journal-title":"ACM SIGSAM Commun. Comput. Algebra"},{"key":"690_CR39","unstructured":"van der Hoeven, J., et\u00a0al.: GNU TeXmacs. https:\/\/www.texmacs.org (1998)"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-025-00690-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00200-025-00690-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-025-00690-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T08:44:26Z","timestamp":1781167466000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00200-025-00690-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,28]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["690"],"URL":"https:\/\/doi.org\/10.1007\/s00200-025-00690-w","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,28]]},"assertion":[{"value":"16 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}