{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T22:14:35Z","timestamp":1761948875375,"version":"3.41.0"},"reference-count":0,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,1]],"date-time":"2024-09-01T00:00:00Z","timestamp":1725148800000},"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":["ACM Commun. Comput. Algebra"],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>a<\/jats:italic>\n            be a polynomial in Z[x\n            <jats:sub>1<\/jats:sub>\n            , ... , x\n            <jats:sub>n<\/jats:sub>\n            ] that is represented by a black box. In this thesis, we have designed and implemented a new factorization algorithm that, on input of the black box, outputs the irreducible factors of\n            <jats:italic>a<\/jats:italic>\n            in the sparse representation. Our new algorithm based on sparse Hensel lifting applies equally well to general multivariate polynomials, both sparse and dense. We first designed the algorithm for a being monic in x\n            <jats:sub>1<\/jats:sub>\n            and square-free, then completed the factorization problem by considering\n            <jats:italic>a<\/jats:italic>\n            being non-monic, non-square-free, and non-primitive. Our algorithm first finds the factors of the primitive part of\n            <jats:italic>a<\/jats:italic>\n            , then the factors of the content of\n            <jats:italic>a<\/jats:italic>\n            in the main variable x\n            <jats:sub>1<\/jats:sub>\n            . We implemented our algorithm in Maple with some subroutines in C. A variety of timing benchmarks are presented. All our timings are much faster than the current best determinant and factorization algorithms in Maple and Magma. We also present a worst-case complexity analysis of our new black box factorization algorithm, along with a failure probability analysis. The case for large integer coefficients has also been considered.\n          <\/jats:p>","DOI":"10.1145\/3717582.3717595","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T20:41:51Z","timestamp":1739306511000},"page":"105-105","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Sparse Hensel Lifting Algorithms for Multivariate Polynomial Factorization"],"prefix":"10.1145","volume":"58","author":[{"given":"Tian","family":"Chen","sequence":"first","affiliation":[{"name":"Simon Fraser University, Canada"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"container-title":["ACM Communications in Computer Algebra"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717582.3717595","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717582.3717595","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:15Z","timestamp":1750295835000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717582.3717595"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":0,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["10.1145\/3717582.3717595"],"URL":"https:\/\/doi.org\/10.1145\/3717582.3717595","relation":{},"ISSN":["1932-2232","1932-2240"],"issn-type":[{"type":"print","value":"1932-2232"},{"type":"electronic","value":"1932-2240"}],"subject":[],"published":{"date-parts":[[2024,9]]},"assertion":[{"value":"2025-02-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}