Randomized polynomial-time root counting in prime power rings. (English) Zbl 1446.11218
Summary: Suppose \(k,p\!\in \!\mathbb{N}\) with \(p\) prime and \(f\!\in \!\mathbb{Z}[x]\) is a univariate polynomial with degree \(d\) and all coefficients having absolute value less than \(p^k\). We give a Las Vegas randomized algorithm that computes the number of roots of \(f\) in \(\mathbb{Z}/\!\left (p^k\right )\) within time \(d^3(k\log p)^{2+o(1)}\). (We in fact prove a more intricate complexity bound that is slightly better.) The best previous general algorithm had (deterministic) complexity exponential in \(k\). We also present some experimental data evincing the potential practicality of our algorithm.
MSC:
| 11Y16 | Number-theoretic algorithms; complexity |
| 11T06 | Polynomials over finite fields |
| 11Y99 | Computational number theory |
| 16P10 | Finite rings and finite-dimensional associative algebras |
Keywords:
Las Vegas randomized algorithmReferences:
| [1] | Avenda\~{n}o, Mart\'{i}n; Ibrahim, Ashraf; Rojas, J. Maurice; Rusek, Korben, Faster \(p\)-adic feasibility for certain multivariate sparse polynomials, J. Symbolic Comput., 47, 4, 454-479 (2012) · Zbl 1246.65078 · doi:10.1016/j.jsc.2011.09.007 |
| [2] | Bach, Eric; Shallit, Jeffrey, Algorithmic Number Theory. Vol. 1, Foundations of Computing Series, xvi+512 pp. (1996), MIT Press, Cambridge, MA · Zbl 0873.11070 |
| [3] | Berthomieu, J\'{e}r\'{e}my; Lecerf, Gr\'{e}goire; Quintin, Guillaume, Polynomial root finding over local rings and application to error correcting codes, Appl. Algebra Engrg. Comm. Comput., 24, 6, 413-443 (2013) · Zbl 1309.13034 · doi:10.1007/s00200-013-0200-5 |
| [4] | B\"{u}rgisser, Peter; Clausen, Michael; Shokrollahi, M. Amin, Algebraic Complexity Theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 315, xxiv+618 pp. (1997), Springer-Verlag, Berlin · Zbl 1087.68568 · doi:10.1007/978-3-662-03338-8 |
| [5] | Cantor, David G.; Gordon, Daniel M., Factoring polynomials over \(p\)-adic fields. Algorithmic Number Theory, Leiden, 2000, Lecture Notes in Comput. Sci. 1838, 185-208 (2000), Springer, Berlin · Zbl 1006.11066 · doi:10.1007/10722028\_10 |
| [6] | Castryck, W.; Denef, J.; Vercauteren, F., Computing zeta functions of nondegenerate curves, IMRP Int. Math. Res. Pap., Art. ID 72017, 57 pp. (2006) · Zbl 1161.14302 |
| [7] | Chambert-Loir, Antoine, Compter (rapidement) le nombre de solutions d’\'{e}quations dans les corps finis, Ast\'{e}risque, 317, Exp. No. 968, vii, 39-90 (2008) · Zbl 1189.11059 |
| [8] | Cheng, Qi, Primality proving via one round in ECPP and one iteration in AKS, J. Cryptology, 20, 3, 375-387 (2007) · Zbl 1155.11362 · doi:10.1007/s00145-006-0406-9 |
| [9] | cgrw2 Q.Cheng, S.Gao, J.M.Rojas, and D.Wan, Counting Roots for Polynomials Modulo Prime Powers, Proceedings of ANTS XIII (Algorithmic Number Theory Symposium, July 16-20, 2018, University of Wisconsin, Madison), Mathematical Sciences Publishers (Berkeley, California), to appear. · Zbl 1531.11119 |
| [10] | Chistov, Alexandre L., Efficient factoring polynomials over local fields and its applications. Proceedings of the International Congress of Mathematicians, Vol. I, II, Kyoto, 1990, 1509-1519 (1991), Math. Soc. Japan, Tokyo · Zbl 0761.11045 |
| [11] | Cohen, Henri, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, xii+534 pp. (1993), Springer-Verlag, Berlin · Zbl 0786.11071 · doi:10.1007/978-3-662-02945-9 |
| [12] | Denef, Jan, Report on Igusa’s local zeta function, Ast\'{e}risque, 201-203, Exp. No. 741, 359-386 (1992) (1991) · Zbl 0749.11054 |
| [13] | Gao, Shuhong; Volny, Frank, IV; Wang, Mingsheng, A new framework for computing Gr\"{o}bner bases, Math. Comp., 85, 297, 449-465 (2016) · Zbl 1331.13018 · doi:10.1090/mcom/2969 |
| [14] | von zur Gathen, Joachim; Gerhard, J\"{u}rgen, Modern Computer Algebra, xiv+795 pp. (2013), Cambridge University Press, Cambridge · Zbl 1277.68002 · doi:10.1017/CBO9781139856065 |
| [15] | von zur Gathen, Joachim; Hartlieb, Silke, Factoring modular polynomials, J. Symbolic Comput., 26, 5, 583-606 (1998) · Zbl 0913.11050 · doi:10.1006/jsco.1998.0228 |
| [16] | Gu\`ardia, Jordi; Nart, Enric; Pauli, Sebastian, Single-factor lifting and factorization of polynomials over local fields, J. Symbolic Comput., 47, 11, 1318-1346 (2012) · Zbl 1262.11106 · doi:10.1016/j.jsc.2012.03.001 |
| [17] | Igusa, Jun-Ichi, Complex powers and asymptotic expansions. I. Functions of certain types, J. Reine Angew. Math., 268/269, 110-130 (1974) · Zbl 0287.43007 · doi:10.1515/crll.1974.268-269.110 |
| [18] | Kedlaya, Kiran S.; Umans, Christopher, Fast polynomial factorization and modular composition, SIAM J. Comput., 40, 6, 1767-1802 (2011) · Zbl 1333.11117 · doi:10.1137/08073408X |
| [19] | klivans A.R.Klivans, Factoring polynomials modulo composites, Master’s Thesis, Carnegie Mellon University Computer Science Technical Report CMU-CS-97-136, 1997. |
| [20] | 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 · doi:10.1007/s10208-003-0093-y |
| [21] | Lauder, Alan G. B.; Wan, Daqing, Counting points on varieties over finite fields of small characteristic. Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Math. Sci. Res. Inst. Publ. 44, 579-612 (2008), Cambridge Univ. Press, Cambridge · Zbl 1188.11069 |
| [22] | Lenstra, A. K.; Lenstra, H. W., Jr.; Lov\'{a}sz, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 4, 515-534 (1982) · Zbl 0488.12001 · doi:10.1007/BF01457454 |
| [23] | McDonald, Bernard R., Finite Rings with Identity, Pure and Applied Mathematics 28, ix+429 pp. (1974), Marcel Dekker, Inc., New York · Zbl 0294.16012 |
| [24] | Niven, Ivan; Zuckerman, Herbert S.; Montgomery, Hugh L., An Introduction to the Theory of Numbers, xiv+529 pp. (1991), John Wiley & Sons, Inc., New York · Zbl 0742.11001 |
| [25] | Raghavendran, R., Finite associative rings, Compositio Math., 21, 195-229 (1969) · Zbl 0179.33602 |
| [26] | S\u{a}l\u{a}gean, Ana, Factoring polynomials over \(Z_4\) and over certain Galois rings, Finite Fields Appl., 11, 1, 56-70 (2005) · Zbl 1075.11078 · doi:10.1016/j.ffa.2004.05.001 |
| [27] | Schmidt, Wolfgang M., Solution trees of polynomial congruences modulo prime powers. Number Theory in Progress, Vol. 1, Zakopane-Ko\'{s}cielisko, 1997, 451-471 (1999), de Gruyter, Berlin · Zbl 0939.11034 |
| [28] | Schmidt, Wolfgang M.; Stewart, C. L., Congruences, trees, and \(p\)-adic integers, Trans. Amer. Math. Soc., 349, 2, 605-639 (1997) · Zbl 0933.11017 · doi:10.1090/S0002-9947-97-01547-X |
| [29] | sircana C.Sircana, Factoring polynomials over \(Z/(n),\) Ph.D.thesis, University of Pisa, Italy, 2016. · Zbl 1458.13028 |
| [30] | Wan, Daqing, Algorithmic theory of zeta functions over finite fields. Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Math. Sci. Res. Inst. Publ. 44, 551-578 (2008), Cambridge Univ. Press, Cambridge · Zbl 1188.11075 |
| [31] | Zuniga-Galindo, W. A., Computing Igusa’s local zeta functions of univariate polynomials, and linear feedback shift registers, J. Integer Seq., 6, 3, Article 03.3.6, 18 pp. (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.
