Algorithms for modular counting of roots of multivariate polynomials. (English) Zbl 1143.11046
Summary: Given a multivariate polynomial \(P(X_{1},\ldots, X_{n})\) over a finite field \({\mathbb {F}_{q}}\), let \(N (P)\) denote the number of roots over \({\mathbb {F}_{q}^{n}}\). The modular root counting problem is, given a modulus \(r\), to determine \(N_{r}(P)= N(P)\mod r\). We study the complexity of computing \(N_{r}(P)\), when the polynomial is given as a sum of monomials. We give an efficient algorithm to compute \(N_{r}(P)\) when the modulus \(r\) is a power of the characteristic of the field. We show that for all other moduli, the problem of computing \(N_{r}(P)\) is NP-hard. We present some hardness results which imply that our algorithm is essentially optimal for prime fields. We show an equivalence between maximum-likelihood decoding for Reed-Solomon codes and a root-finding problem for symmetric polynomials.
MSC:
| 11Y16 | Number-theoretic algorithms; complexity |
| 11T06 | Polynomials over finite fields |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W30 | Symbolic computation and algebraic computation |
| 94B35 | Decoding |
References:
| [1] | Adleman, L., Huang, M.-D.: Counting rational points on curves and Abelian varieties over finite fields. In: Proceedings of the 1996 Algorithmic Number Theory Symposium. LNCS, vol. 1122, pp. 1–16. Springer, Berlin (1996) · Zbl 0898.11045 |
| [2] | Artin, M.: Algebra. Prentice Hall, New York (1991) |
| [3] | Beigel, R., Tarui, J.: On ACC. Comput. Complex. 4, 350–366 (1994) · Zbl 0835.68040 · doi:10.1007/BF01263423 |
| [4] | Ehrenfeucht, A., Karpinski, M.: The computational complexity of (xor, and)-counting problems. Tech. Report 8543-CS, ICSI, Berkeley (1990) |
| [5] | Grigoriev, D., Karpinski, M.: An approximation algorithm for the number of zeroes of arbitrary polynomials over GF[q]. In: Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS’91), pp. 662–669 (1991) |
| [6] | Guruswami, V., Vardy, A.: Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. In: Proceedings of the ACM-SIAM symposium on Discrete Algorithms (SODA’05), pp. 470–478 (2005) · Zbl 1297.94128 |
| [7] | Huang, M.-D., Ierardi, D.: Counting rational points on curves over finite fields. In: Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS’93), pp. 616–625 (1993) |
| [8] | Huang, M.-D., Wong, Y.: Solvability of systems of polynomial congruences modulo a large prime. J. Comput. Complex. 8, 227–257 (1999) · Zbl 0977.11054 · doi:10.1007/s000370050029 |
| [9] | Karpinski, M., Luby, M.: Approximating the number of zeroes of a GF[2] polynomial. J. Algorithms 14, 280–287 (1993) · Zbl 0769.11047 · doi:10.1006/jagm.1993.1014 |
| [10] | Kedlaya, K.: Computing Zeta functions via p-adic cohomology. In: Algorithmic Number Theory Symposium (ANTS), pp. 1–17 (2004) · Zbl 1125.14300 |
| [11] | Lauder, A., Wan, D.: Computing zeta functions of Artin-Schreier curves over finite fields ii. J. Complex. 20(2–3), 331–349 (2004) · Zbl 1119.14018 · doi:10.1016/j.jco.2003.08.009 |
| [12] | Lauder, A., Wan, D.: Counting points on varieties over finite fields of small characteristic. In: Buhler, J.P., Stevenhagen, P. (eds.) Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography (Mathematical Sciences Research Institute Publications). Cambridge University Press (2007, to appear) |
| [13] | Lidl, R., Niederreiter, H.: Finite Fields, Encylopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (1997) |
| [14] | Luby, M., Velicković, B., Wigderson, A.: Deterministic approximate counting of depth-2 circuits. In: Israel Symposium on Theory of Computing Systems, pp. 18–24 (1993) |
| [15] | Mason, R.C.: Diophantine Equations Over Function Fields. Cambridge University Press, Cambridge (1984) · Zbl 0533.10012 |
| [16] | Moreno, O., Moreno, C.J.: Improvements of the Chevalley-Warning and the Ax-Katz theorems. Am. J. Math. 117(1), 241–244 (1995) · Zbl 0824.11017 · doi:10.2307/2375042 |
| [17] | Papadimitriou, C.: Computational Complexity. Addison–Wesley, Reading (1994) · Zbl 0833.68049 |
| [18] | Pila, J.: Frobenius maps of Abelian varieties and finding roots of unity in finite fields. Math. Comput. 55, 745–763 (1990) · Zbl 0724.11070 · doi:10.1090/S0025-5718-1990-1035941-X |
| [19] | Schoof, R.: Counting points on elliptic curves over finite fields. J. Th’eor. Nr. Bord. 7, 219–254 (1995) · Zbl 0852.11073 |
| [20] | Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865–877 (1991) · Zbl 0733.68034 · doi:10.1137/0220053 |
| [21] | Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 189–201 (1979) · Zbl 0415.68008 |
| [22] | Valiant, L.G.: Completeness for parity problems. In: Proc. 11th International Computing and Combinatorics Conference (COCOON’05), pp. 1–8 (2005) · Zbl 1128.68359 |
| [23] | Valiant, L.G.: Accidental algorithms. In: Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 509–517 (2006) |
| [24] | Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci. 47, 85–93 (1986) · Zbl 0621.68030 · doi:10.1016/0304-3975(86)90135-0 |
| [25] | von zur Gathen, J., Karpinski, M., Shparlinski, I.: Counting curves and their projections. Comput. Complex. 6, 64–99 (1996) · Zbl 0990.68642 · doi:10.1007/BF01202042 |
| [26] | Wan, D.: A Chevalley-Warning approach to p-adic estimate of character sums. Proc. Am. Math. Soc. 123, 45–54 (1995) · Zbl 0821.11062 |
| [27] | Wan, D.: Computing Zeta functions over finite fields. Contemp. Math. 225, 135–141 (1999) · Zbl 0929.11063 |
| [28] | Wan, D.: Modular counting of rational points on sparse equations over finite fields. Found. Comput. Math. (2006, to appear) |
| [29] | Wan, D.: Personal communication (April 2006) |
| [30] | Yao, A.C.: On ACC and threshold circuits. In: 31st IEEE Symposium on Foundations of Computer Science (FOCS’90), pp. 619–627 (1990) |
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.
