论文标题
在有限场上计算大多项式系统的Zeta函数
Computing zeta functions of large polynomial systems over finite fields
论文作者
论文摘要
在本文中，我们改进了Lauder-Wan \ cite {lw}和Harvey \ cite {ha}的算法，以计算$ n $变量的$ m $ polyenmial方程的Zeta函数，该系统在有限的字段上$ \ ff_q $ Q $ Q $ elements，for $ m $ m $ m $ $ m $ $ $ $ $ $。原始算法中对$ m $的依赖性为$ m $。我们的主要结果是减少了对$ m $的指数依赖性对$ m $的多项式依赖性。作为一个应用程序，我们从软件验证论文\ cite {bjk}（在有限字段上的通用等效性上）从软件验证纸\ cite \ cite \ cite \ cite \ cite cape加快了双重指数时间算法。一个关键的新成分是经典的kronecker定理的有效版本，该版本（从理论上讲）减少了$ \ ff_q $的“大”多项式系统的定义方程数，当$ q $适当大。
In this paper, we improve the algorithms of Lauder-Wan \cite{LW} and Harvey \cite{Ha} 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 \cite{BJK} (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.
