Computation of Igusa's Local Zeta Functions, Trees, and One-Way Functions, by W. A. Zuniga-Galindo

Abstract: In this paper we present a polynomial time algorithm to compute the local zeta function $Z(s,f)$ attached to a polynomial \\ $f(x)\\in \\QTR\{Bbb\}\ {Z\}[x]$ ( in one variable, with splitting field $\\QTR\{Bbb\}\{Q\}$) and a prime $p$. The algorithm reduces in polynomial time the computation of $Z(s,f)$ to the compu tation of a factorization of $f(x)$ over $\\QTR\{Bbb\}\{Q\}$. This reduction is accomplished by constructing a weighted tree from the $p-$adic expansion of th e roots of $f(x)$ modulo a certain power of $p$, and then associating a generating function to this tree. The genera\\-ting function constructed in this way coincides with the local zeta function of $f(x).$ We also propose a new class of candidates for one-way functions based on Igusa's zeta functions attached to polynomials in one variable.

W. A. Zuniga-Galindo <>