Solving polynomial systems over non-fields and applications to modular polynomial factoring. (English) Zbl 07852634
Summary: We study the problem of solving a system of \(m\) polynomials in \(n\) variables over the ring of integers modulo a prime-power \(p^k\). The problem over finite fields is well studied in varied parameter settings. For small characteristic \(p = 2\), Lokshtanov et al. (SODA’17) initiated the study, for degree \(d = 2\) systems, to improve the exhaustive search complexity of \(O(2^n) \cdot \mathsf{poly}(m,n)\) to \(O(2^{0.8765 n}) \cdot \mathsf{poly}(m, n)\); which currently is improved to \(O(2^{0.6943 n}) \cdot \mathsf{poly}(m, n)\) in Dinur (SODA’21). For large \(p\) but constant \(n\), Huang and Wong (FOCS’96) gave a randomized \(\mathsf{poly}(d, m, \log p)\) time algorithm. Note that for growing \(n\), system-solving is known to be intractable even with \(p = 2\) and degree \(d = 2\).
We devise a randomized \(\mathsf{poly}(d, m, \log p)\)-time algorithm to find a root of a given system of \(m\) integral polynomials of degrees bounded by \(d\), in \(n\) variables, modulo a prime power \(p^k\); when \(n+k\) is constant. In a way, we extend the efficient algorithm of Huang and Wong (FOCS’96) for system-solving over Galois fields (i.e., characteristic \(p)\) to system-solving over Galois rings (i.e., characteristic \(p^k)\); when \(k>1\) is constant. The challenge here is to find a lift of singular \(\mathbb{F}_p\)-roots (exponentially many); as there is no efficient general way known in algebraic-geometry for resolving singularities.
Our algorithm has applications to factoring univariate polynomials over Galois rings. Given \(f \in \mathbb{Z} [x]\) and a prime-power \(p^k (k\geq 2)\), finding factors of \(f \bmod p^k\) has a curious state-of-the-art. It is solved for large \(k\) by \(p\)-adic factoring algorithms (von zur Gathen, Hartlieb, ISSAC’96); but unsolved for small \(k\). In particular, no nontrivial factoring method is known for \(k \geq 5\) (Dwivedi, Mittal, Saxena, ISSAC’19). One issue is that degree-\(\delta\) factors of \(f(x) \bmod p^k\) could be exponentially many, as soon as \(k \geq 2\). We give the first randomized \(\mathrm{poly}(\deg (f), \log p)\)-time algorithm to find a degree-\(\delta\) factor of \(f(x) \bmod p^k\), when \(k + \delta\) is constant. Our method has potential application in algebraic coding theory. In particular, extending algebraic geometric and Reed-Solomon codes to Galois rings could enable new and improved bounds on their underlying efficiency parameters.
We devise a randomized \(\mathsf{poly}(d, m, \log p)\)-time algorithm to find a root of a given system of \(m\) integral polynomials of degrees bounded by \(d\), in \(n\) variables, modulo a prime power \(p^k\); when \(n+k\) is constant. In a way, we extend the efficient algorithm of Huang and Wong (FOCS’96) for system-solving over Galois fields (i.e., characteristic \(p)\) to system-solving over Galois rings (i.e., characteristic \(p^k)\); when \(k>1\) is constant. The challenge here is to find a lift of singular \(\mathbb{F}_p\)-roots (exponentially many); as there is no efficient general way known in algebraic-geometry for resolving singularities.
Our algorithm has applications to factoring univariate polynomials over Galois rings. Given \(f \in \mathbb{Z} [x]\) and a prime-power \(p^k (k\geq 2)\), finding factors of \(f \bmod p^k\) has a curious state-of-the-art. It is solved for large \(k\) by \(p\)-adic factoring algorithms (von zur Gathen, Hartlieb, ISSAC’96); but unsolved for small \(k\). In particular, no nontrivial factoring method is known for \(k \geq 5\) (Dwivedi, Mittal, Saxena, ISSAC’19). One issue is that degree-\(\delta\) factors of \(f(x) \bmod p^k\) could be exponentially many, as soon as \(k \geq 2\). We give the first randomized \(\mathrm{poly}(\deg (f), \log p)\)-time algorithm to find a degree-\(\delta\) factor of \(f(x) \bmod p^k\), when \(k + \delta\) is constant. Our method has potential application in algebraic coding theory. In particular, extending algebraic geometric and Reed-Solomon codes to Galois rings could enable new and improved bounds on their underlying efficiency parameters.
MSC:
| 13P15 | Solving polynomial systems; resultants |
| 68W30 | Symbolic computation and algebraic computation |
| 11T06 | Polynomials over finite fields |
References:
| [1] | Armand, Marc André, Improved list decoding of generalized Reed-Solomon and alternant codes over Galois rings, IEEE Trans. Inf. Theory, 51, 2, 728-733, 2005 · Zbl 1247.94064 |
| [2] | Armand, Marc André, List decoding of generalized Reed-Solomon codes over commutative rings, IEEE Trans. Inf. Theory, 51, 1, 411-419, 2005 · Zbl 1247.94063 |
| [3] | Bardet, Magali; Faugère, Jean-Charles; Salvy, Bruno; Spaenlehauer, Pierre-Jean, On the complexity of solving quadratic boolean systems, J. Complex., 29, 1, 53-75, 2013 · Zbl 1255.65090 |
| [4] | Berlekamp, Elwyn R., Factoring polynomials over finite fields, Bell Syst. Tech. J., 46, 8, 1853-1859, 1967 · Zbl 0166.04901 |
| [5] | Berthomieu, Jérémy; Lecerf, Grégoire; Quintin, Guillaume, Polynomial root finding over local rings and application to error correcting codes, Appl. Algebra Eng. Commun. Comput., 24, 6, 413-443, 2013 · Zbl 1309.13034 |
| [6] | Bhargava, Manjul, P-orderings and polynomial functions on arbitrary subsets of Dedekind rings, J. Reine Angew. Math., 490, 101-128, 1997 · Zbl 0899.13022 |
| [7] | Bi, Jingguo; Cheng, Qi; Rojas, J. Maurice, Sublinear root detection and new hardness results for sparse polynomials over finite fields, SIAM J. Comput., 45, 4, 1433-1447, 2016 · Zbl 1345.68281 |
| [8] | Björklund, Andreas; Kaski, Petteri; Williams, Ryan, Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction, (46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 2019, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik) · Zbl 07561519 |
| [9] | Borevich, Zenon Ivanovich; Shafarevich, Igor Rostislavovich, Number Theory, vol. 20, 1986, Academic Press |
| [10] | Bouillaguet, Charles, Delaplace, Claire, Trimoska, Monika, 2021. A simple deterministic algorithm for systems of quadratic polynomials over \(\mathbb{F}_2\). Cryptology ePrint Archive. · Zbl 07848217 |
| [11] | Brownawell, W. Dale, Bounds for the degrees in the Nullstellensatz, Ann. Math., 126, 3, 577-591, 1987 · Zbl 0641.14001 |
| [12] | Buchberger, Bruno, Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal, 1965, Universität Innsbruck, PhD thesis · Zbl 1245.13020 |
| [13] | Cantor, David G.; Gordon, Daniel M., Factoring polynomials over p-adic fields, (International Algorithmic Number Theory Symposium, 2000, Springer), 185-208 · Zbl 1006.11066 |
| [14] | Cantor, David G.; Zassenhaus, Hans, A new algorithm for factoring polynomials over finite fields, Math. Comput., 587-592, 1981 · Zbl 0493.12024 |
| [15] | Chakrabarti, Sayak, Multivariate polynomials modulo prime powers: their roots, zeta-function and applications, 2022, Dept of CSE, IIT Kanpur: Dept of CSE, IIT Kanpur India, Master’s thesis |
| [16] | Chakrabarti, Sayak; Saxena, Nitin, An effective description of the roots of multivariates mod \(p^k\) and the related Igusa’s local zeta function, (Proceedings of the International Symposium on Symbolic and Algebraic Computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC’23, 2023, ACM: ACM Tromsø, Norway) · Zbl 07760756 |
| [17] | Cheng, Howard; Labahn, George, Computing all factorizations in \(\mathbb{Z}_N [x]\), (Proceedings of the International Symposium on Symbolic and Algebraic Computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC’01, 2001), 64-71 · Zbl 1356.13029 |
| [18] | Cheng, Qi; Gao, Shuhong; Rojas, J. Maurice; Wan, Daqing, Counting roots for polynomials modulo prime powers, The Open Book Series (ANTS XIII), 2, 1, 191-205, 2019 · Zbl 1531.11119 |
| [19] | Chistov, A. L., Efficient factorization of polynomials over local fields, Dokl. Akad. Nauk SSSR, 293, 5, 1073-1077, 1987 · Zbl 0636.12010 |
| [20] | Chistov, A. L., Algorithm of polynomial complexity for factoring polynomials over local fields, J. Math. Sci., 70, 4, 1912-1933, 1994 · Zbl 0835.11047 |
| [21] | Chistov, Alexander L., An effective algorithm for deciding solvability of a system of polynomial equations over p-adic integers, Algebra Anal., 33, 6, 162-196, 2021 · Zbl 1507.11111 |
| [22] | Chojnacka-Pniewska, M., Sur les congruences aux racines données, (Annales Polonici Mathematici, vol. 3, 1956, Instytut Matematyczny Polskiej Akademii Nauk), 9-12 · Zbl 0071.03803 |
| [23] | Cox, David; Little, John; OShea, Donal, Ideals, Varieties, and Algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra, 2013, Springer Science & Business Media |
| [24] | Dearden, Bruce; Metzger, Jerry, Roots of polynomials modulo prime powers, Eur. J. Comb., 18, 6, 601-606, 1997 · Zbl 0890.11010 |
| [25] | Denef, Jan; Hoornaert, Kathleen, Newton polyhedra and Igusa’s local zeta function, J. Number Theory, 89, 1, 31-64, 2001 · Zbl 0994.11038 |
| [26] | Dinur, Itai, Cryptanalytic applications of the polynomial method for solving multivariate equation systems over GF(2), (Advances in Cryptology-EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Advances in Cryptology-EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, 2021), 374-403 · Zbl 1479.94157 |
| [27] | Dinur, Itai, Improved algorithms for solving polynomial systems over GF(2) by multiple parity-counting, (Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021, SIAM), 2550-2564 · Zbl 07788489 |
| [28] | Dubé, Thomas W., The structure of polynomial ideals and Gröbner bases, SIAM J. Comput., 19, 4, 750-773, 1990 · Zbl 0697.68051 |
| [29] | Dwivedi, Ashish, Polynomials over composites: compact root representation via ideals and algorithmic consequences, 2023, Dept of CSE, IIT Kanpur: Dept of CSE, IIT Kanpur India, PhD thesis |
| [30] | Dwivedi, Ashish; Saxena, Nitin, Computing Igusa’s local zeta function of univariates in deterministic polynomial-time, (14th Algorithmic Number Theory Symposium (ANTS XIV). 14th Algorithmic Number Theory Symposium (ANTS XIV), Open Book Series, vol. 4(1), 2020), 197-214 · Zbl 1457.11166 |
| [31] | Dwivedi, Ashish; Mittal, Rajat; Saxena, Nitin, Counting basic-irreducible factors mod \(p^k\) in deterministic poly-time and p-adic applications, (Shpilka, Amir, 34th Computational Complexity Conference (CCC 2019). 34th Computational Complexity Conference (CCC 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 137, 2019), 15:1-15:29 · Zbl 07564415 |
| [32] | Dwivedi, Ashish; Mittal, Rajat; Saxena, Nitin, Efficiently factoring polynomials modulo \(p^4\), J. Symb. Comput., 104, 805-823, 2021, Preliminary version appeared in the 44th ACM International Symposium on Symbolic and Algebraic Computation (ISSAC) 2019 · Zbl 1465.13022 |
| [33] | Ehrenfeucht, Andrzej; Karpinski, Marek, The Computational Complexity of (Xor, and)-Counting Problems, 1990, International Computer Science Inst. |
| [34] | Elder, Matt; Lim, Junghee; Sharma, Tushar; Andersen, Tycho; Reps, Thomas, Abstract domains of affine relations, ACM Trans. Program. Lang. Syst., 36, 4, 1-73, 2014 |
| [35] | Forbes, Michael A.; Shpilka, Amir, Complexity theory column 88: challenges in polynomial factorization, ACM SIGACT News, 46, 4, 32-49, 2015 |
| [36] | Garg, Abhibhav; Saxena, Nitin, Special-case algorithms for blackbox radical membership, Nullstellensatz and transcendence degree, (Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, 2020), 186-193 · Zbl 07300070 |
| [37] | Gianni, Patrizia; Trager, Barry; Zacharias, Gail, Gröbner bases and primary decomposition of polynomial ideals, J. Symb. Comput., 6, 2-3, 149-167, 1988 · Zbl 0667.13008 |
| [38] | Gopalan, Parikshit; Guruswami, Venkatesan; Lipton, Richard J., Algorithms for modular counting of roots of multivariate polynomials, Algorithmica, 50, 4, 479-496, 2008 · Zbl 1143.11046 |
| [39] | Goppa, Valerii Denisovich, Codes associated with divisors, Probl. Pereda. Inf., 13, 1, 33-39, 1977 · Zbl 0415.94005 |
| [40] | Greenberg, Marvin J., Rational points in henselian discrete valuation rings, Publ. Math. Inst. Hautes Etudes Sci., 31, 59-64, 1966 |
| [41] | Guàrdia, Jordi; Nart, Enric; Pauli, Sebastian, Single-factor lifting and factorization of polynomials over local fields, J. Symb. Comput., 47, 11, 1318-1346, November 2012 · Zbl 1262.11106 |
| [42] | Hammons, A. Roger; Kumar, P. Vijay; Calderbank, A. Robert; Sloane, Neil J. A.; Solé, Patrick, The \(\mathbb{Z}_4\)-linearity of kerdock, preparata, goethals, and related codes, IEEE Trans. Inf. Theory, 40, 2, 301-319, 1994 · Zbl 0811.94039 |
| [43] | Hauser, Herwig, On the problem of resolution of singularities in positive characteristic (or: a proof we are still waiting for), Bull. Am. Math. Soc., 47, 1, 1-30, 2010 · Zbl 1185.14011 |
| [44] | Hensel, Kurt, Eine neue theorie der algebraischen zahlen, Math. Z., 2, 3, 433-452, Sep 1918 · JFM 46.0254.01 |
| [45] | Hironaka, Heisuke, Resolution of singularities of an algebraic variety over a field of characteristic zero: II, Ann. Math., 205-326, 1964 · Zbl 1420.14031 |
| [46] | Høholdt, Tom; Van Lint, Jacobus H.; Pellikaan, Ruud, Algebraic geometry codes, (Handbook of Coding Theory, 1(Part 1), 1998), 871-961 · Zbl 0922.94015 |
| [47] | Huang, M-D.; Wong, Y-C., Solvability of systems of polynomial congruences modulo a large prime, Comput. Complex., 8, 3, 227-257, 1999, Preliminary version appeared in the IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS) 1996 · Zbl 0977.11054 |
| [48] | Ivanyos, Gábor; Rónyai, Lajos, Chevalley-warning theorem in quantum computing, ERCIM News, 112, 28-29, 2018 |
| [49] | Kaltofen, Erich, Polynomial factorization 1987-1991, (Latin American Symposium on Theoretical Informatics, 1992, Springer), 294-313 |
| [50] | Katz, Daniel, Point count divisibility for algebraic sets over \(\mathbb{Z} / p^\ell \mathbb{Z}\) and other finite principal rings, Proc. Am. Math. Soc., 137, 12, 4065-4075, 2009 · Zbl 1226.11127 |
| [51] | Kayal, Neeraj, Solvability of a system of bivariate polynomial equations over a finite field, (International Colloquium on Automata, Languages, and Programming, 2005, Springer), 551-562 · Zbl 1084.11509 |
| [52] | Kedlaya, Kiran S.; Umans, Christopher, Fast polynomial factorization and modular composition, SIAM J. Comput., 40, 6, 1767-1802, 2011 · Zbl 1333.11117 |
| [53] | Kipnis, Aviad; Patarin, Jacques; Goubin, Louis, Unbalanced oil and vinegar signature schemes, (International Conference on the Theory and Applications of Cryptographic Techniques, 1999, Springer), 206-222 · Zbl 0933.94031 |
| [54] | Klivans, Adam, Factoring polynomials modulo composites, 1997, Carnegie-Mellon Univ, Pittsburgh PA, Dept of CS, Technical report |
| [55] | Kopp, Leann; Randall, Natalie; Rojas, J. Maurice; Zhu, Yuyu, Randomized polynomial-time root counting in prime power rings, Math. Comput., 89, 321, 373-385, 2020 · Zbl 1446.11218 |
| [56] | Lauder, Alan G. B., Counting solutions to equations in many variables over finite fields, Found. Comput. Math., 4, 3, 221-267, 2004 · Zbl 1076.11040 |
| [57] | Lidl, Rudolf; Niederreiter, Harald, Introduction to Finite Fields and Their Applications, 1994, Cambridge University Press · Zbl 0820.11072 |
| [58] | Lokshtanov, Daniel; Paturi, Ramamohan; Tamaki, Suguru; Williams, Ryan; Yu, Huacheng, Beating brute force for systems of polynomial equations over finite fields, (Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, SIAM), 2190-2202 · Zbl 1433.11135 |
| [59] | Marshall, Murray; Ramage, Garry, Zeros of polynomials over finite principal ideal rings, Proc. Am. Math. Soc., 49, 1, 35-38, 1975 · Zbl 0274.12011 |
| [60] | Maulik, Davesh, Root sets of polynomials modulo prime powers, J. Comb. Theory, Ser. A, 93, 1, 125-140, 2001 · Zbl 0991.11002 |
| [61] | Müller-Olm, Markus; Seidl, Helmut, Analysis of modular arithmetic, (European Symposium on Programming, 2005, Springer), 46-60 · Zbl 1108.68404 |
| [62] | Müller-Olm, Markus; Seidl, Helmut, Analysis of modular arithmetic, ACM Trans. Program. Lang. Syst., 29, 5, 2007, 29-es · Zbl 1108.68404 |
| [63] | Neiger, Vincent; Rosenkilde, Johan; Schost, Éric, Fast computation of the roots of polynomials over the ring of power series, (Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, 2017), 349-356 · Zbl 1444.68305 |
| [64] | Niven, Ivan; Zuckerman, Herbert S.; Montgomery, Hugh L., An Introduction to the Theory of Numbers, 2013, John Wiley & Sons · Zbl 0742.11001 |
| [65] | Panayi, Peter N., Computation of Leopoldt’s P-adic regulator, 1995, University of East Anglia, PhD thesis |
| [66] | Patarin, Jacques, Hidden fields equations (hfe) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms, (International Conference on the Theory and Applications of Cryptographic Techniques, 1996, Springer), 33-48 · Zbl 1301.94125 |
| [67] | Robelle, Caleb; Rojas, J. Maurice; Zhu, Yuyu, Sub-linear point counting for variable separated curves over prime power rings, 2021, arXiv preprint |
| [68] | Rojas, J. Maurice; Zhu, Yuyu, Root repulsion and faster solving for very sparse polynomials over p-adic fields, J. Number Theory, 241, 655-699, 2022 · Zbl 1498.11241 |
| [69] | Sălăgean, Ana, Factoring polynomials over \(\mathbb{Z}_4\) and over certain Galois rings, Finite Fields Appl., 11, 1, 56-70, 2005 · Zbl 1075.11078 |
| [70] | Schmidt, Wolfgang M., A lower bound for the number of solutions of equations over finite fields, J. Number Theory, 6, 6, 448-480, 1974 · Zbl 0298.12010 |
| [71] | Sierpiński, Wacław, Remarques sur les racines d’une congruence, Ann. Pol. Math., 1, 1, 89-90, 1955 · Zbl 0055.27101 |
| [72] | Sircana, Carlo, Factorization of polynomials over \(\mathbb{Z} /( p^n)\), (Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, 2017, ACM), 405-412 · Zbl 1458.13028 |
| [73] | Sudan, Madhu, Decoding of Reed Solomon codes beyond the error-correction bound, J. Complex., 13, 1, 180-193, 1997 · Zbl 0872.68026 |
| [74] | Surowka, Robert L.; Regan, Kenneth W., Polynomials modulo composite numbers: Ax-katz type theorems for the structure of their solution sets, 2014, arXiv preprint |
| [75] | Tew, Neal; Kalla, Priyank; Shekhar, Namrata; Gopalakrishnan, Sivaram, Verification of arithmetic datapaths using polynomial function models and congruence solving, (2008 IEEE/ACM International Conference on Computer-Aided Design, 2008, IEEE), 122-128 |
| [76] | Tsfasman, Michael; Vladut, Serge G., Algebraic-Geometric Codes, vol. 58, 2013, Springer Science & Business Media |
| [77] | Tsfasman, Michael A.; Vlădutx, S. G.; Zink, Th, Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound, Math. Nachr., 109, 1, 21-28, 1982 · Zbl 0574.94013 |
| [78] | von zur Gathen, Joachim; Hartlieb, Silke, Factorization of polynomials modulo small prime powers, 1996, Paderborn Univ, Technical report · Zbl 0918.11066 |
| [79] | von zur Gathen, Joachim; Hartlieb, Silke, Factoring modular polynomials, J. Symb. Comput., 26, 5, 583-606, 1998, (Conference version in ISSAC’96) · Zbl 0913.11050 |
| [80] | von zur Gathen, Joachim; Panario, Daniel, Factoring polynomials over finite fields: a survey, J. Symb. Comput., 31, 1-2, 3-17, 2001 · Zbl 0969.11041 |
| [81] | von zur Gathen, Joachim; Karpinski, Marek; Shparlinski, Igor, Counting curves and their projections, Comput. Complex., 6, 1, 64-99, 1996 · Zbl 0990.68642 |
| [82] | Walker, Judy L., The Nordstrom-Robinson code is algebraic-geometric, IEEE Trans. Inf. Theory, 43, 5, 1588-1593, 1997 · Zbl 0904.94027 |
| [83] | Walker, Judy L., Algebraic geometric codes over rings, J. Pure Appl. Algebra, 144, 1, 91-110, 1999 · Zbl 0949.94007 |
| [84] | Zassenhaus, Hans, On Hensel factorization, I, J. Number Theory, 1, 3, 291-311, 1969 · Zbl 0188.33703 |
| [85] | Zassenhaus, Hans, A remark on the Hensel factorization method, Math. Comput., 32, 141, 287-292, 1978 · Zbl 0383.12003 |
| [86] | Zhu, Yuyu, Trees, point counting beyond fields, and root separation, 2020, Texas A&M University, PhD thesis |
| [87] | Zuniga-Galindo, W. A., Computing Igusa’s local zeta functions of univariate polynomials, and linear feedback shift registers, J. Integer Seq., 6, 2, 3, 2003 · Zbl 1040.11090 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
