{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T06:53:48Z","timestamp":1776840828832,"version":"3.51.2"},"reference-count":20,"publisher":"American Mathematical Society (AMS)","issue":"357","license":[{"start":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T00:00:00Z","timestamp":1770076800000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>An input- and output-sensitive greatest common divisor (GCD) algorithm for multi-variate polynomials over finite fields is proposed by combining the modular method with the Ben-Or\/Tiwari sparse interpolation. The bit complexity of the algorithm is given and is sensitive to the sparse representation, while for previous sparse GCD algorithms, the complexities were given only in some special cases. It is shown that the new algorithm is superior both in theory and in practice compared with existing GCD algorithms: the complexity in the degree is decreased from quadratic to linear and the running times are decreased by 1\u20133 orders of magnitude in various benchmarks.<\/p>","DOI":"10.1090\/mcom\/4054","type":"journal-article","created":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T12:36:40Z","timestamp":1733229400000},"page":"389-413","source":"Crossref","is-referenced-by-count":0,"title":["Bit complexity of polynomial GCD on sparse representation"],"prefix":"10.1090","volume":"95","author":[{"given":"Qiao-Long","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiao-Shan","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2025,2,3]]},"reference":[{"key":"1","unstructured":"A. Arnold, Sparse polynomial interpolation and testing, Ph.D. Thesis, University of Waterloo, 2016."},{"key":"2","doi-asserted-by":"crossref","unstructured":"M. Ben-Or and P. Tiwari, A deterministic algorithm for sparse multivariate polynominal interpolation (extended abstract), Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA (Janos Simon, ed.), ACM, 1988, pp. 301\u2013309.","DOI":"10.1145\/62212.62241"},{"key":"3","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1145\/321662.321664","article-title":"On Euclid\u2019s algorithm and the computation of polynomial greatest common divisors","volume":"18","author":"Brown, W. S.","year":"1971","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"4","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1145\/321371.321381","article-title":"Subresultants and reduced polynomial remainder sequences","volume":"14","author":"Collins, George E.","year":"1967","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"issue":"16","key":"5","doi-asserted-by":"publisher","first-page":"1445","DOI":"10.1016\/j.tcs.2010.11.050","article-title":"Sparse interpolation of multivariate rational functions","volume":"412","author":"Cuyt, Annie","year":"2011","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1145\/1993886.1993909","article-title":"Diversification improves interpolation","author":"Giesbrecht, Mark","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450306751"},{"key":"7","isbn-type":"print","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1145\/2930889.2930903","article-title":"A fast parallel sparse polynomial GCD algorithm","author":"Hu, Jiaxiong","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450343800"},{"key":"8","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.jsc.2020.06.001","article-title":"A fast parallel sparse polynomial GCD algorithm","volume":"105","author":"Hu, Jiaxiong","year":"2021","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"6","key":"9","doi-asserted-by":"publisher","first-page":"1147","DOI":"10.1007\/s11425-020-1791-5","article-title":"Sparse polynomial interpolation based on diversification","volume":"65","author":"Huang, Qiao-Long","year":"2022","journal-title":"Sci. China Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1674-7283","issn-type":"print"},{"key":"10","doi-asserted-by":"crossref","unstructured":"S. Mohammad Mahdi Javadi and M. Monagan, Parallel sparse polynomial interpolation over finite fields, Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, 2010, pp. 160\u2013168.","DOI":"10.1145\/1837210.1837233"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/42267.45069","article-title":"Greatest common divisors of polynomials given by straight-line programs","volume":"35","author":"Kaltofen, Erich","year":"1988","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"12","doi-asserted-by":"crossref","unstructured":"E. Kaltofen, Y. N. Lakshman, and J-M Wiley, Modular rational sparse multivariate polynomial interpolation, Proceedings of the international symposium on Symbolic and algebraic computation, 1990, pp. 135\u2013139.","DOI":"10.1145\/96877.96912"},{"issue":"3-4","key":"13","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0747-7171(03)00088-9","article-title":"Early termination in sparse interpolation algorithms","volume":"36","author":"Kaltofen, Erich","year":"2003","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"3","key":"14","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/S0747-7171(08)80015-6","article-title":"Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators","volume":"9","author":"Kaltofen, Erich","year":"1990","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"15","isbn-type":"print","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1145\/380752.380801","article-title":"Randomness efficient identity testing of multivariate polynomials","author":"Klivans, Adam R.","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/1581133499"},{"key":"16","doi-asserted-by":"crossref","unstructured":"J. Moses and D. Y. Y. Yun, The EZ GCD algorithm, Proceedings of the ACM annual conference, Atlanta, Georgia, USA, August 27-29, 1973 (Irwin E. Perlin and Thomas J. McConnell Jr., eds.), ACM, 1973, pp. 159\u2013166.","DOI":"10.1145\/800192.805698"},{"issue":"5","key":"17","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1006\/jsco.1994.1025","article-title":"Fast construction of irreducible polynomials over finite fields","volume":"17","author":"Shoup, Victor","year":"1994","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1007\/s11424-017-6332-0","article-title":"Computing sparse GCD of multivariate polynomials via polynomial interpolation","volume":"31","author":"Tang, Min","year":"2018","journal-title":"J. Syst. Sci. Complex.","ISSN":"https:\/\/id.crossref.org\/issn\/1009-6124","issn-type":"print"},{"key":"19","doi-asserted-by":"crossref","unstructured":"P. S. Wang, The EEZ-GCD algorithm, SIGSAM Bull. 14 (1980), no. 2, 50\u201360.","DOI":"10.1145\/1089220.1089228"},{"key":"20","isbn-type":"print","first-page":"216","article-title":"Probabilistic algorithms for sparse polynomials","author":"Zippel, Richard","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/3540095195"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2026-95-357\/S0025-5718-2025-04054-7\/S0025-5718-2025-04054-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T05:55:10Z","timestamp":1776837310000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2026-95-357\/S0025-5718-2025-04054-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,3]]},"references-count":20,"journal-issue":{"issue":"357","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["S0025-5718-2025-04054-7"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/4054","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2025,2,3]]}}}