Computing zeta functions of large polynomial systems over finite fields

2020/07/26 by Cheng, Qi, Rojas, J. Maurice, Wan, Daqing
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2007.13214

Abstract

In this paper, we improve the algorithms of Lauder-Wan \citeLW and Harvey \citeHa to compute the zeta function of a system of m polynomial equations in n variables over the finite field \FF_q of q elements, for m large. The dependence on m in the original algorithms was exponential in m. Our main result is a reduction of the exponential dependence on m to a polynomial dependence on m. As an application, we speed up a doubly exponential time algorithm from a software verification paper \citeBJK (on universal equivalence of programs over finite fields) to singly exponential time. One key new ingredient is an effective version of the classical Kronecker theorem which (set-theoretically) reduces the number of defining equations for a "large" polynomial system over \FF_q when q is suitably large.

Related

• Solving Polynomial Equations Over Finite Fields
• Using zeta functions to factor polynomials over finite fields
• Computing zeta functions over finite fields
• Polynomial evaluation over finite fields: new algorithms and complexity\n bounds
• Computing zeta functions of arithmetic schemes