Computing zeta functions of large polynomial systems over finite fields
Computing zeta functions of large polynomial systems over finite fields
复制标题
计算有限域上大型多项式系统的 zeta 函数
DOI：
10.1016/j.jco.2022.101681
复制
发表时间：
2022
影响因子：
1.7
通讯作者：
Wan, Daqing
中科院分区：
文献类型：
--
作者：
Cheng, Qi;Maurice Rojas, J.;Wan, Daqing
本文改进了Lauder-Wan [11]和Harvey [8]的算法，计算q元有限域Fq上n元m次多项式方程组的zeta函数，其中m是大的.在原始算法中，对m的依赖性是指数的。我们的主要结果是减少对m的依赖从指数多项式。作为一个应用，我们从最近的软件验证文件[3]（在有限域上的程序的通用等价性）的双指数算法加速到单指数时间。一个关键的新成分是一个有效的，有限域版本的经典克罗内克定理（集理论上）减少了数量的定义方程的多项式系统超过F q时，q是适当的大。
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.
影响因子：
1.8
作者：
Harvey, David
通讯作者：
Harvey, David
DOI：
--
发表时间：
1941
期刊：
影响因子：
--
作者：
O. Perron
通讯作者：
O. Perron
有限域上 zeta 函数的算法理论
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
D. Wan
通讯作者：
D. Wan