{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:40:12Z","timestamp":1750297212006,"version":"3.41.0"},"reference-count":14,"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":"\n Let\n a<\/jats:italic>\n be a polynomial in Z[\n x<\/jats:italic>\n 1<\/jats:sub>\n ,\n x<\/jats:italic>\n 2<\/jats:sub>\n ,\n \n \u2026,x\n n<\/jats:sub>\n <\/jats:italic>\n ]. Let\n \u03b1<\/jats:italic>\n \u2208 Z\n \n n<\/jats:italic>\n <\/jats:sup>\n and\n p<\/jats:italic>\n be a large prime. Let B be a modular black box representation for\n a<\/jats:italic>\n , that is,\n B<\/jats:bold>\n : Z\n \n n<\/jats:italic>\n <\/jats:sup>\n \u00d7 {\n p<\/jats:italic>\n } \u2192 Z\n \n p<\/jats:italic>\n <\/jats:sub>\n such that B(\n \u03b1,p<\/jats:italic>\n ) outputs\n a<\/jats:italic>\n (\n \u03b1<\/jats:italic>\n ) mod\n p.<\/jats:italic>\n In our implementation\n B<\/jats:bold>\n is a Maple procedure. We present a Maple program CMBBSHL which on input of\n B<\/jats:bold>\n outputs the irreducible factorization \u03a0\n \n r<\/jats:italic>\n <\/jats:sup>\n \n i<\/jats:italic>\n =1\n <\/jats:sub>\n f<\/jats:italic>\n \n e<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n <\/jats:sup>\n \n i<\/jats:italic>\n <\/jats:sub>\n of\n a<\/jats:italic>\n (\n x<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026,\n \n x\n n<\/jats:sub>\n <\/jats:italic>\n ) with high probability. Our program is a combination of Maple codes and C codes where the main programs are implemented in Maple and several subroutines are implemented in C for increased efficiency. We present (1) a description of the algorithm, (2) a demonstration of the software, (3) a timing benchmark, and (4) some implementation details.\n <\/jats:p>","DOI":"10.1145\/3717582.3717588","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T20:41:51Z","timestamp":1739306511000},"page":"77-80","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Maple Program to Factor Multivariate Polynomials Given by Black Boxes"],"prefix":"10.1145","volume":"58","author":[{"given":"Tian","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Mathematics, Simon Fraser University, Burnaby, Canada"}]},{"given":"Michael","family":"Monagan","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Simon Fraser University, Burnaby, Canada"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02163269"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321664"},{"key":"e_1_2_1_3_1","volume-title":"Factoring multivariate polynomials represented by black boxes - a Maple + C implementation. Math. Comput. Sci. 16(2--3), article 18","author":"Chen T.","year":"2022","unstructured":"Chen, T. and Monagan M.: Factoring multivariate polynomials represented by black boxes - a Maple + C implementation. Math. Comput. Sci. 16(2--3), article 18, Springer 2022."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597066.3597119"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/281508.281538"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-15984-3_230"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"e_1_2_1_8_1","first-page":"467","volume-title":"Proceedings of ISSAC'88","author":"Kaltofen E.","year":"1988","unstructured":"Kaltofen, E., and Yagati, L.: Improved sparse multivariate polynomial interpolation algorithms. Proceedings of ISSAC'88, pp. 467--474, Springer, 1988."},{"issue":"4","key":"e_1_2_1_9_1","first-page":"166","article-title":"The design of Maple's sum-of-products and POLY data structures for representing mathematical objects","volume":"48","author":"Monagan M.","year":"2014","unstructured":"Monagan, M. and Pearce, R.: The design of Maple's sum-of-products and POLY data structures for representing mathematical objects. Communications of Computer Algebra, 48(4):166--186, 2014.","journal-title":"Communications of Computer Algebra"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of ICMS 2018","author":"Monagan M.","year":"2018","unstructured":"Monagan, M. and Tuncer, B.: Sparse multivariate polynomial factorization: a high-performance design and implementation. Proceedings of ICMS 2018, LNCS 10931:359--368, Springer, 2018."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2019.05.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3476446.3536178"},{"key":"e_1_2_1_13_1","first-page":"93","article-title":"A new modular interpolation algorithm for factoring multivariate polynomials. Proceedings of ANTS '94","volume":"877","author":"Rubinfeld R.","year":"1994","unstructured":"Rubinfeld, R. and Zippel, R.: A new modular interpolation algorithm for factoring multivariate polynomials. Proceedings of ANTS '94, LNCS 877:93--107, Springer, 1994.","journal-title":"LNCS"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80018-1"}],"container-title":["ACM Communications in Computer Algebra"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717582.3717588","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717582.3717588","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.3717588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["10.1145\/3717582.3717588"],"URL":"https:\/\/doi.org\/10.1145\/3717582.3717588","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"}}]}}