1. Computing zeta functions of large polynomial systems over finite fields.
- Author
-
Cheng, Qi, Maurice Rojas, J., and Wan, Daqing
- Subjects
- *
ZETA functions , *SOFTWARE verification , *POLYNOMIALS , *FINITE fields , *POLYNOMIAL time algorithms , *EQUATIONS - Abstract
We improve the algorithms of Lauder-Wan [11] and Harvey [8] to compute the zeta function of a system of m polynomial equations in n variables, over the q element finite field F q , for large m. The dependence on m in the original algorithms was exponential in m. Our main result is a reduction of the dependence on m from exponential to polynomial. As an application, we speed up a doubly exponential algorithm from a recent software verification paper [3] (on universal equivalence of programs over finite fields) to singly exponential time. One key new ingredient is an effective, finite field version of the classical Kronecker theorem which (set-theoretically) reduces the number of defining equations for a polynomial system over F q when q is suitably large. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF