{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T15:58:05Z","timestamp":1776873485161,"version":"3.51.2"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[1980,5,1]],"date-time":"1980-05-01T00:00:00Z","timestamp":325987200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGSAM Bull."],"published-print":{"date-parts":[[1980,5]]},"abstract":"<jats:p>An enhanced gcd algorithm based on the EZ-GCD algorithm is described. Implementational aspects are emphasized. It is generally faster and is particularly suited for computing gcd of sparse multivariate polynomials. The EEZ-GCD algorithm is characterized by the following features:(1) avoiding unlucky evaluations,(2) predetermining the correct leading coefficient of the desired gcd,(3) using the sparsity of the given polynomials to determine terms in the gcd and(4) direct methods for dealing with the \"common divisor problem.\" The common divisor problem occurs when the gcd has a different common divisor with each of the cofactors. The EZ-GCD algorithm does a square-free decomposition in this case. It can be avoided resulting in increased speed. One method is to use parallel p-adic construction of more than two factors. Machine examples with timing data are included.<\/jats:p>","DOI":"10.1145\/1089220.1089228","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"50-60","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["The EEZ-GCD algorithm"],"prefix":"10.1145","volume":"14","author":[{"given":"Paul S.","family":"Wang","sequence":"first","affiliation":[{"name":"Kent State University, Kent, Ohio"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[1980,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321664"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/355791.355795"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/321371.321381"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Hensel K. Zahlentheorie Goschen Berlin and Leipzig 1913.  Hensel K. Zahlentheorie Goschen Berlin and Leipzig 1913.","DOI":"10.1515\/9783112360026"},{"key":"e_1_2_1_5_1","volume-title":"2: Seminumerical Algorithms","author":"Knuth D. E.","year":"1969","unstructured":"Knuth , D. E. , \"The Art of Computer Programming\", V. 2: Seminumerical Algorithms , Addison-Wesley , Reading, Mass ., 1969 , MR 44 #3531. Knuth, D. E., \"The Art of Computer Programming\", V. 2: Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1969, MR 44 #3531."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/800192.805698"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1975-0396471-3"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings, MACSYMA USERS' CONFERENCE, University of California at Berkeley, July 27--29","author":"Wang P. S.","year":"1977","unstructured":"Wang , P. S. , \"Preserving Sparseness in Multivariate Polynomial Factorization\" , Proceedings, MACSYMA USERS' CONFERENCE, University of California at Berkeley, July 27--29 , 1977 . Wang, P. S., \"Preserving Sparseness in Multivariate Polynomial Factorization\", Proceedings, MACSYMA USERS' CONFERENCE, University of California at Berkeley, July 27--29, 1977."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1978-0568284-3"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings EUROSAM '79","author":"Wang P. S.","year":"1979","unstructured":"Wang , P. S. , \"Analysis of the p-adic Construction of Multivariate Correction Coefficients in Polynomial Factorization: Iteration vs. Recursion \", Proceedings EUROSAM '79 , June 26 --28 , 1979 , Marseille, France. Wang, P. S., \"Analysis of the p-adic Construction of Multivariate Correction Coefficients in Polynomial Factorization: Iteration vs. Recursion\", Proceedings EUROSAM '79, June 26--28, 1979, Marseille, France."},{"key":"e_1_2_1_11_1","volume-title":"MIT","author":"Yun D. Y. Y.","year":"1973","unstructured":"Yun , D. Y. Y. , \"The Hensel Lemma in Algebraic Manipulation\", Ph.D. Thesis , Department of Mathematics , MIT , Nov. 1973 , (also Project MAC TR- 138, Nov. 1974). Yun, D. Y. Y., \"The Hensel Lemma in Algebraic Manipulation\", Ph.D. Thesis, Department of Mathematics, MIT, Nov. 1973, (also Project MAC TR-138, Nov. 1974)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(69)90047-X"},{"key":"e_1_2_1_13_1","first-page":"216","volume-title":"Proceedings, EUROSAM '79","author":"Zippel R.","year":"1979","unstructured":"Zippel , R. , \"Probabilistic Algorithms for Sparse Polynomials\" , Proceedings, EUROSAM '79 , June 26 --28 , 1979 , Marseille, France, pp. 216 -- 226 . Zippel, R., \"Probabilistic Algorithms for Sparse Polynomials\", Proceedings, EUROSAM '79, June 26--28, 1979, Marseille, France, pp. 216--226."},{"key":"e_1_2_1_14_1","volume-title":"LCS, M.I.T.","author":"Reference Manual","year":"1979","unstructured":"MACSYMA Reference Manual , The Mathlab Group , LCS, M.I.T. , Cambridge , Mass ., May 1979 . MACSYMA Reference Manual, The Mathlab Group, LCS, M.I.T., Cambridge, Mass., May 1979."}],"container-title":["ACM SIGSAM Bulletin"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089220.1089228","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1089220.1089228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:22Z","timestamp":1750262902000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089220.1089228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1980,5]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1980,5]]}},"alternative-id":["10.1145\/1089220.1089228"],"URL":"https:\/\/doi.org\/10.1145\/1089220.1089228","relation":{},"ISSN":["0163-5824"],"issn-type":[{"value":"0163-5824","type":"print"}],"subject":[],"published":{"date-parts":[[1980,5]]},"assertion":[{"value":"1980-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}