Computing \ Igusa's Local Zeta Functions of Univariate Polynomials, and Linear Feedback Shift Registers
W. A. Zuniga-Galindo
We give a polynomial time algorithm for computing the Igusa local zeta function $Z(s,f)$ attached to a polynomial \ $f(x)\in \mathbb{Z}[x]$, in one variable, with splitting field $\mathbb{Q}$, and a prime number $p$. We also propose a new class of Linear Feedback Shift Registers based on the computation of Igusa's local zeta function.
0346.tex
%\input{tcilatex}
%\input{tcilatex}


\documentclass{amsart}
\usepackage{amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{graphicx}
\usepackage{amscd}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Created=Fri Dec 15 08:49:14 2000}
%TCIDATA{LastRevised=Thu Sep 25 20:04:59 2003}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Journal Articles\AMS Journal Article">}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=amsartci.cst}

\newtheorem{theorem}{Theorem}
\theoremstyle{plain}
\newtheorem{acknowledgement}{Acknowledgement}
\newtheorem{algorithm}{Algorithm}
\newtheorem{axiom}{Axiom}
\newtheorem{case}{Case}
\newtheorem{claim}{Claim}
\newtheorem{conclusion}{Conclusion}
\newtheorem{condition}{Condition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{criterion}{Criterion}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{exercise}{Exercise}
\newtheorem{lemma}{Lemma}
\newtheorem{notation}{Notation}
\newtheorem{problem}{Problem}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
\newtheorem{solution}{Solution}
\newtheorem{summary}{Summary}
\numberwithin{equation}{section}
\numberwithin{theorem}{section}
\numberwithin{lemma}{section}
\numberwithin{proposition}{section}
\numberwithin{corollary}{section}
\numberwithin{remark}{section}
\numberwithin{example}{section}
\numberwithin{definition}{section}
\newcommand{\thmref}[1]{Theorem~\ref{#1}}
\newcommand{\secref}[1]{\S\ref{#1}}
\newcommand{\lemref}[1]{Lemma~\ref{#1}}
\input{tcilatex}

\begin{document}
\title[ Local Zeta Functions and Linear Feedback Shift Registers]{Computing \ Igusa's Local Zeta Functions of Univariate Polynomials, and
Linear Feedback Shift Registers}
\author{W. A. Zuniga-Galindo}

\begin{abstract}
We give a polynomial time algorithm for computing the Igusa local zeta
function $Z(s,f)$ attached to a polynomial \ $f(x)\in \mathbb{Z}[x]$, in one
variable, with splitting field $\mathbb{Q}$, and a prime number $p$. We also
propose a new class of Linear Feedback Shift Registers based on the
computation of Igusa's local zeta function.
\end{abstract}

\address{Department of Mathematics and Computer Science, Barry University, 11300 N.E.
Second Avenue\\
Miami Shores, Florida 33161, USA}
\email{wzuniga@mail.barry.edu}
\thanks{Supported by COLCIENCIAS-Grant \# 089-2000. }
\subjclass{Primary 11S40, 94A60; Secondary 11Y16, 14GG50}
\keywords{Igusa's local zeta function, polynomial time algorithms, one-way functions,
linear feedback shift registers}
\maketitle

\section{Introduction}

Let $f(x)\in \mathbb{Z}[x]$, $x=(x_{1},\mathbb{\cdots },x_{n})$ be a
non-constant polynomial, and $\ p$ a fixed prime number. We put $%
N_{m}(f,p)=N_{m}(f)$ for the number of solutions of the congruence $%
f(x)\equiv 0$ mod $p^{m}$ in $(\mathbb{Z}/p^{m}\mathbb{Z})^{n}$, $m\geqq 1$,
\ and \ $H(t,f)$ for the Poincar\'{e} series 
\begin{equation*}
H(t,f)=\sum\limits_{m=0}^{\infty }N_{m}(f)(p^{-n}t)^{m}\text{,}
\end{equation*}
with $t\in \mathbb{C}$, $\mid t\mid <1$, and \ $N_{0}(f)=1$. This paper is
dedicated to the computation of the sequence $\left\{ N_{m}(f)\right\}
_{m\geqq 0}$ when $f$ is an univariate polynomial with splitting field $%
\mathbb{Q}$.

Igusa showed that the \ Poincar\'{e} series $H(t,f)$ admits a meromorphic
continuation to the complex plane as a rational function of $t$ \cite{I1}, 
\cite{I2}. In this paper we make a first step towards the solution of the
following problem: given a polynomial \ $f(x)$\ as above, how difficult is
to compute the meromorphic continuation of the \ Poincar\'{e} series $H(t,f)$%
?

The computation of the \ Poincar\'{e} series $H(t,f)$\ is equivalent to the
computation of Igusa's local zeta \ function $Z(s,f)$, attached to $f$ and $%
p $, defined as follows. We denote by $\mathbb{Q}_{p}$ the field of $p-$adic
numbers, and by $\mathbb{Z}_{p}$ the ring of $p-$adic integers. For $x\in 
\mathbb{Q}_{p}$, $v_{p}(x)$ denotes the $p-$adic order of $x$, and $%
|x|_{p}=p^{-v_{p}(x)}$ its absolute value. The Igusa local zeta function
associated to $f$ and $p$ is defined as follows: 
\begin{equation*}
Z(s,f)=\int_{\mathbb{Z}_{p}^{n}}|f(x)|_{p}^{s}\mid dx\mid
,\,\,\,\,\,\,\,\,s\in \mathbb{C},\,\,
\end{equation*}
where $\func{Re}(s)>0$, and $\mid dx\mid $ denotes the Haar measure on $%
\mathbb{Q}_{p}^{n}$ so normalized that $\mathbb{Z}_{p}^{n}$ has measure $1$.
The following relation between $Z(s,f)$\ and $\ H(t,f)$ holds (see \cite{I1}%
, theorem 8.2.2): 
\begin{equation*}
H(t,f)=\frac{1-tZ(s,f)}{1-t},\text{ }t=p^{-s}.
\end{equation*}
Thus, the rationality of $Z(s,f)$\ implies the rationality of the
Poincar\'{e} series \ $H(t,f)$, and \ the computation of $H(t,f)$ is \
equivalent to the computation of$\ Z(s,f)$. Igusa \cite[theorem 8.2.1]{I1}\
showed that the local zeta function $Z(s,f)$ \ admits a meromorphic
continuation to the complex plane as a rational function \ of $p^{-s}$.

The first result of this paper is a polynomial time algorithm for computing
the local zeta function $Z(s,f)$ attached to a polynomial \ $f(x)\in \mathbb{%
Z}[x]$, in one variable, with splitting field $\mathbb{Q}$, and a prime
number $p$. We also give an explicit estimate for its complexity (see
algorithm Compute\_$Z(s,f)$ in section 2, and theorem \ref{theoA}).

Many authors have found explicit formulas for $Z(s,f)$, or $H(f,t)$,\ for
several classes of polynomials, among them \cite{D2}, \cite{D-H}, \cite{G1}, 
\cite{G2}, [\cite{I3} and the references therein], \cite{S-Z-G}, \cite{Z-G1}%
, \cite{Z-G2}. In all these works the computation of $Z(s,f)$, or $H(f,t)$,
is reduced to the computation of \ other problems, as the computation of the
number of solutions of polynomial equations with coefficients in a finite
field. Currently, there is no polynomial time algorithm solving this problem
\ \cite{Wa}, \cite{V-K-S}. Moreover, none of the above mentioned works
include complexity estimates for the computation of Igusa's local zeta
functions.

Of particular importance is Denef's explicit formula for \ $Z(s,f)$, when $f$
satisfies some generic conditions \ \cite{D2}. This formula involves the
numerical data associated to a resolution of singularities of the divisor $%
f=0$, and the number of rational points of certain non-singular varieties
over finite fields. Thus the computation of $Z(s,f),$ for a generic
polynomial $f$, is reduced to the computation of \ the numerical data
associated to a resolution of singularities of the divisor $f=0$, and the
number of solutions of non-singular polynomials over finite fields.
Currently, it is unknown if these problems can be solved in polynomial time
on a Turing machine. However, during the last few years important
achievements have been obtained in the computation of resolution of
singularities of polynomials \cite{B-M}, \cite{B-S}, \cite{B-S1}, \cite{Vi}.

The computation of the Igusa local zeta function for an arbitrary polynomial
seems to be an intractable problem on a Turing machine. For example, for $%
p=2 $, the computation of the number of solutions of a polynomial equation
with coefficients in $\mathbb{Z}/2\mathbb{Z}$ is an $\mathbf{NP}-$complete
problem on a Turing Machine \cite[page 251, problem AN9]{G-J}. Then \ in the
case of $2-$adic numbers, the computation of \ the Igusa local zeta function
is an $\mathbf{NP}-$complete problem.

Recently, Anshel and Goldfeld have shown the existence of a strong
connection between the computation of zeta functions and cryptography \cite
{A-G}. Indeed, they proposed a new class of candidates for one-way functions
based on global zeta functions. \ A one-way function is a function $\ F$
such that for each $x$ in the domain of $F$, it is easy to compute $F(x)$;
but for essentially all $y$ in the range of $F$, it is an intractable
problem to find an $x$ \ such that $y=F(x)$. These functions play a central
role, from a practical and theoretical point of view, in modern
cryptography. Currently, there is no guarantee that one-way functions exist
even if $\mathbf{P}\neq \mathbf{NP}$. Most of the present candidates for
one-way functions are constructed on the intractability of problems like
integer factorization and discrete logarithms \cite{G-L-N}. Recently, P.
Shor has introduced a new approach to attack these problems \cite{S}.
Indeed, Shor have shown that on a quantum computer the integer factorization
and discrete logarithm \ problems can be computed in polynomial time.

We set 
\begin{equation*}
\mathcal{H}=\{H(t,f)\mid f(x)\in \mathbb{Z}[x]\text{, in \ one variable,
with splitting field }\mathbb{Q}\},
\end{equation*}
and $N^{\infty }$ $\left( \mathbb{Z}\right) $ for the set \ of finite
sequences of integers. For each positive integer $u$ and a prime number $p$,
we define 
\begin{equation*}
\begin{array}{cccc}
F_{u,p}: & \mathcal{H} & {\ \rightarrow } & \mathbb{N}^{\infty }\left( 
\mathbb{Z}\right) \\ 
& H(t,f) & {\ \rightarrow } & \{N_{0}(f,p),N_{1}(f,p),\cdots ,N_{u}(f,p)\}%
\text{.}
\end{array}
\end{equation*}

Our second result asserts that \ $F_{u,p}(H(t,f))$ \ can be computed in
polynomial time, for every $H(t,f)$\ in $\mathcal{H}$ (see theorem \ref
{theoB}). It seems interesting \ to study the complexity on a Turing machine
of the following \ problem: given a list of positive integers $%
\{a_{0},a_{1},\cdots ,a_{u}\}$, how difficult is it to determine whether or
not there exists a Poincar\'{e} series $H(t,f)=\sum_{m=0}^{\infty
}N_{m}(f)(p^{-1}t)^{m}$, such that $a_{i}=N_{i}(f)$, $i=1$,$\cdots $, $u$?

Currently, the author does not have any result about the complexity of the
above problem, however the mappings $F_{u,p}$ can be considered as new \
class of stream ciphers (see section 8).

\section{The Algorithm \ Compute\_$Z(s,f)$}

In this section we present a polynomial time algorithm, Compute\_$Z(s,f)$, \
that solves the following problem: given \ a polynomial $f(x)\in \mathbb{Z}%
[x]$, in one variable, whose splitting field is $\mathbb{Q}$, \ find an
explicit expression for the meromorphic continuation of $Z(s,f)$. The
algorithm is as follows.

\textbf{Algorithm\ Compute\_}$Z(s,f)$

Input\ : A \ polynomial $f(x)\in \mathbb{Z}[x],$\ in one variable, whose
splitting field is $\mathbb{Q}$.

Output : A rational function of $p^{-s}$\ that is the meromorphic \qquad
continuation of $Z(s,f)$.

\begin{enumerate}
\item  Factorize $f(x)$ in $\mathbb{Q}[x]$: $f(x)=\alpha
_{0}\prod\limits_{i=1}^{r}(x-\alpha _{i})^{e_{i}}\in \mathbb{Q}[x].\qquad $

\item  Compute 
\begin{equation*}
l_{f}=\left\{ 
\begin{array}{cc}
1+\max \{v_{p}(\alpha _{i}-\alpha _{j})\mid i\neq j\text{, }1\leq i\text{, }%
j\leq r\}\text{,} & \text{ if }r\geqq 2\text{;} \\ 
1\text{, } & \text{\ if \ \ }r=1\text{.}
\end{array}
\right. 
\end{equation*}

\item  Compute the $p-$adic expansions of the numbers $\alpha _{i}$, $%
i=1,2,\cdots ,r$\ modulo $p^{l_{f}+1}$.

\item  Compute the tree $T(f,l_{f})$\ associated to $f(x)$\ and $p$ (for the
definition of $T(f,l_{f})$ see (\ref{tree})).

\item  Compute the generating function $G(s,T(f,l_{f}),p)$\ attached to $%
T(f,l_{f})$ (for the definition of $G(s,T(f,l_{f}),p)$\ see (\ref{Gfunction}%
)).

\item  Return $Z(s,f)=G(s,T(f,l_{f}),p)$.

\item  End
\end{enumerate}

In section 6, we shall give a proof of the correctness \ and a \ complexity
estimate for the algorithm Compute\_$Z(s,f)$. The first step in our
algorithm is accomplished by means \ of the factoring algorithm by A.K.
Lenstra, H. Lenstra and L. Lov\'{a}sz \cite{L-L-L}. If $d_{f}$ denotes the
degree of $f(x)=\sum\nolimits_{i}a_{i}x^{i}$, and 
\begin{equation*}
\shortparallel f\shortparallel =\sqrt{\sum_{i}a_{i}^{2}},
\end{equation*}
then\ \ the \ mentioned factoring algorithm needs \ $O\left(
d_{f}^{6}+d_{f}^{9}(\log \shortparallel f\shortparallel )\right) $
arithmetic operations, and the integers on which these operations are
performed each have a binary length \ \ $O\left( d_{f}^{3}+d_{f}^{2}(\log
\shortparallel f\shortparallel )\right) $ \cite[theorem 3.6]{L-L-L}.

The steps $2$, $3$, $4$, $5$ reduce \ in polynomial time the computation of $%
Z(s,f)$ to the computation of a factorization of $f(x)$ over $\mathbb{Q}$.
This reduction is accomplished by constructing a weighted tree from the $p-$%
adic expansion of the roots of $\ f(x)$ modulo a \ certain power of $p$ (see
section 4), and then \ \ associating a generating function to this tree (see
section 5). Finally, \ we shall prove that the generating function \
constructed in this way coincides with the local zeta function of $f(x)$
(see section 5).

\section{$p$-adic Stationary Phase Formula}

Our main tool in the effective computing of Igusa's local zeta function \ of
a polynomial in one variable will be the $p-$adic stationary phase formula,
abbreviated SPF \cite{I3}. This formula is a recursive procedure for
computing local zeta functions. By using this procedure it is possible to
compute the local zeta functions for many classes of polynomials [\cite{I3}
and the references therein], \cite{S-Z-G}, \cite{Z-G1}, \cite{Z-G2}, \cite
{ZG3}.

Given a polynomial $f(x)\in $ $\mathbb{Z}_{p}[x]\setminus $ $p\mathbb{Z}%
_{p}[x]$, we denote by $\overline{f(x)}$ its reduction modulo $p\mathbb{Z}%
_{p}$, i.e., the polynomial obtained by reducing the coefficients of $f(x)$
modulo $p\mathbb{Z}_{p}$. \ We define for each $x_{0}\in $ $\mathbb{Z}_{p}$, 
\begin{equation*}
f_{x_{0}}(x)=p^{-e_{x_{0}}}f(x_{0}+px)\text{,}
\end{equation*}
where $e_{x_{0}}$\ is the minimum \ order of $p$\ \ \ in the coefficients of 
$f(x_{0}+px)$. Thus $f_{x_{0}}(x)\in \mathbb{Z}_{p}[x]\setminus $ $p\mathbb{Z%
}_{p}[x]$. We shall call the polynomial $f_{x_{0}}(x)$\ the \textit{%
dilatation} of $f(x)$\ at $x_{0}$. We also define 
\begin{equation*}
\nu (\overline{f})=\text{Card}\{\overline{z}\in \mathbb{F}_{p}\mid \overline{%
f}(\overline{z})\neq 0\},
\end{equation*}
\begin{equation*}
\delta (\overline{f})=\text{Card}\{\overline{z}\in \mathbb{F}_{p}\mid 
\overline{z}\text{ is a simple root of }\overline{f}(\overline{z})=0\}.
\end{equation*}

We shall use $\{0,1,\cdots ,p-1\}\subseteq \mathbb{Z}_{p}$ as a set of
representatives of the elements of $\mathbb{F}_{p}=\mathbb{Z}/$ $p\mathbb{Z}%
=\{\overline{0},\overline{1},\cdots ,\overline{p-1}\}$. Let $S=S(f)$ denote
the subset of $\{0,1,\cdots ,p-1\}\subseteq \mathbb{Z}_{p}$ which is mapped
bijectively \ by the canonical homomorphism $\mathbb{Z}_{p}\rightarrow 
\mathbb{Z}_{p}/p\mathbb{Z}_{p}$ to the set of roots of \ $\overline{f}(%
\overline{z})=0$ with multiplicity greater than or equal to two.

With all the above notation we are able to state the $p-$adic stationary
phase formula for polynomials in one variable.

\begin{proposition}[{\protect\cite[theorem 10.2.1]{I1}}]
Let $f(x)\in $ $\mathbb{Z}_{p}[x]\setminus $ $p\mathbb{Z}_{p}[x]$ be a
non-cons\-tant polynomial. Then 
\begin{equation*}
Z(s,f)=p^{-1}\nu (\overline{f})+\delta (\overline{f})\frac{(1-p^{-1})p^{-1-s}%
}{(1-p^{-1-s})}+\sum\limits_{\xi \in S}p^{-1-e_{\xi }s}\int\limits_{\mathbb{Z%
}_{p}}\mid f_{\xi }(x)\mid _{p}^{s}dx.
\end{equation*}
\end{proposition}

The following example illustrates the use \ of the $p-$adic stationary phase
formula, and \ also the \ basic aspects of our algorithm for computing $%
Z(s,f)$.

\subsection{Example\label{ex2}}

Let \ $f(x)=(x-\alpha _{1})(x-\alpha _{2})^{3}(x-\alpha _{3})(x-\alpha
_{4})^{2}(x-\alpha _{5})$ be a polynomial such that $\alpha _{1}$, $\alpha
_{2}$ , $\alpha _{3}$, $\alpha _{4}$ , $\alpha _{5}$ are integers having the
following $\ p-$adic expansions: 
\begin{equation*}
\alpha _{1}=a+dp+kp^{2},
\end{equation*}
\begin{equation*}
\alpha _{2}=a+dp+lp^{2},
\end{equation*}
\begin{equation*}
\alpha _{3}=b+gp+mp^{2},
\end{equation*}
\begin{equation*}
\alpha _{4}=c+hp+np^{2},
\end{equation*}
\begin{equation*}
\alpha _{5}=c+hp+rp^{2},
\end{equation*}
where \ the $p$-adic digits $a$, $b$, $c$, $d$, $g$, $h$, $l$, $m$, $n$, $r$
belong to $\{0,1,\mathbb{\cdots },p-1\}$. We assume the $p$-adic digits to
be different by pairs. The local zeta function $Z(s,f)$ will be computed by
using SPF iteratively.

By applying SPF with $\overline{f(x)}=(x-\overline{a})^{4}(x-\overline{b})(x-%
\overline{c})^{3}$, $\nu (\overline{f})=p-3$, $\delta (\overline{f}%
)=1,S=\{a,c\}$, $f_{a}(x)=p^{-4}f(a+px)$, and $f_{c}(x)=p^{-3}f(c+px)$, we
obtain that

\begin{eqnarray}
Z(s,f) &=&p^{-1}(p-3)+\frac{(1-p^{-1})p^{-1-s}}{1-p^{-1-s}}+p^{-1-4s}\int_{%
\mathbb{Z}_{p}}|f_{a}(x)|_{p}^{s}\mid dx\mid  \notag \\
&&+p^{-1-3s}\int_{\mathbb{Z}_{p}}|f_{c}(x)|_{p}^{s}\mid dx\mid \text{.}
\label{step8}
\end{eqnarray}
We apply SPF to the integrals involving $f_{a}(x)$ and $f_{c}(x)$\ in (\ref
{step8}). First, we consider the integral corresponding to \ $f_{a}(x)$.
Since $\overline{f_{a}(x)}=(x-\overline{d})^{4}(\overline{a}-\overline{b})(%
\overline{a}-\overline{c})^{3}$, $S=\{d\}$, $f_{a,d}(x)=p^{-4}f_{a}(d+px)$, $%
\nu (\overline{f_{a}})=p-1$, and $\delta (\overline{f_{a}})=0$, it follows
from (\ref{step8}) using SPF that

\begin{eqnarray}
Z(s,f) &=&p^{-1}(p-3)+\frac{(1-p^{-1})p^{-1-s}}{1-p^{-1-s}}%
+p^{-1}(p-1)p^{-1-4s}  \notag \\
&&+p^{-2-8s}\int_{\mathbb{Z}_{p}}|f_{a,d}(x)|_{p}^{s}\mid dx\mid
+p^{-1-3s}\int_{\mathbb{Z}_{p}}|f_{c}(x)|_{p}^{s}\mid dx\mid \text{.}
\label{step9}
\end{eqnarray}
Now, we apply SPF to the integral involving $f_{c}(x)$ in (\ref{step9}).
Since $\overline{f_{c}(x)}$ $=(\overline{c}-\overline{a})^{4}(\overline{c}-%
\overline{b})(x-\overline{h})^{3}$, $S=\{h\},f_{c,h}(x)=p^{-3}f_{c}(h+px)$, $%
\nu (\overline{f_{c}})=p-1$, and $\delta (\overline{f_{c}})=0$, it follows
from (\ref{step9}) using SPF that 
\begin{eqnarray}
Z(s,f) &=&p^{-1}(p-3)+\frac{(1-p^{-1})p^{-1-s}}{1-p^{-1-s}}%
+p^{-1}(p-1)p^{-1-4s}  \notag \\
&&\,+p^{-2-8s}\int_{\mathbb{Z}_{p}}|f_{a,d}(x)|_{p}^{s}\mid dx\mid
+p^{-1}(p-1)p^{-1-3s}  \notag \\
&&\,+p^{-2-6s}\int_{\mathbb{Z}_{p}}|f_{c,h}(x)|_{p}^{s}\mid dx\mid \text{.}
\label{step10}
\end{eqnarray}

By applying SPF to the integral involving $f_{a,d}(x)$ in (\ref{step10}),
with $\overline{f_{a,d}(x)}=(x-\overline{k})(x-\overline{l})^{3}(\overline{d}%
-\overline{b})(\overline{d}-\overline{c})^{3}$, $S=\{k,l\}$, $%
f_{a,d,k}(x)=p^{-1}f_{a,d}(k+px)$, $|f_{a,d,k}(x)|_{p}^{s}=|x|_{p}^{s}$, $%
f_{a,d,l}(x)=p^{-3}f_{a,d}(l+px)$, $|f_{a,d,l}(x)|_{p}^{s}=|x|_{p}^{3s}$,$\
\nu (\overline{f_{a,d}})=p-2$, and $\delta (\overline{f_{a,d}})=1$, we
obtain \ that

\begin{eqnarray}
Z(s,f) &=&p^{-1}(p-3)+\frac{(1-p^{-1})p^{-1-s}}{1-p^{-1-s}}%
+p^{-1}(p-1)p^{-1-4s}  \notag \\
&&\,+p^{-1}(p-1)p^{-1-3s}+p^{-1}(p-2)p^{-2-8s}+\frac{(1-p^{-1})p^{-3-9s}}{%
1-p^{-1-s}}  \notag \\
&&\,+\frac{(1-p^{-1})p^{-3-11s}}{1-p^{-1-3s}}+p^{-2-6s}\int_{\mathbb{Z}%
_{p}}|f_{c,h}(x)|_{p}^{s}\mid dx\mid \text{.}  \label{step11}
\end{eqnarray}
Finally, by applying SPF to the integral \ involving $f_{c,h}(x)$ in (\ref
{step11}), we obtain that 
\begin{eqnarray}
Z(s,f) &=&p^{-1}(p-3)+\frac{(1-p^{-1})p^{-1-s}}{1-p^{-1-s}}%
+p^{-1}(p-1)p^{-1-4s}  \notag \\
&&\,+p^{-1}(p-1)p^{-1-3s}+p^{-1}(p-2)p^{-2-8s}+\frac{(1-p^{-1})p^{-3-9s}}{%
1-p^{-1-s}}  \notag \\
&&\,+\frac{(1-p^{-1})p^{-3-11s}}{1-p^{-1-3s}}+p^{-1}(p-2)p^{-2-6s}+\frac{%
(1-p^{-1})p^{-3-7s}}{1-p^{-1-s}}  \notag \\
&&+\frac{(1-p^{-1})p^{-3-8s}}{1-p^{-1-2s}}\text{.}  \label{step12}
\end{eqnarray}

\begin{remark}
\label{remark}If $\alpha =\frac{a}{b}\in \mathbb{Q}$, and $v_{p}(\alpha )<0$%
, then 
\begin{equation}
\mid x-\alpha \mid _{p}=\mid \alpha \mid _{p},\text{ for every }x\in \mathbb{%
Z}_{p}.  \label{const}
\end{equation}
On the other hand, a polynomial of the form 
\begin{equation*}
f(x)=\alpha _{0}\prod\limits_{i=1}^{r}(x-\alpha _{i})^{e_{i}}\in \mathbb{Q}%
[x],
\end{equation*}
can be decomposed as $f(x)=\alpha _{0}f_{-}(x)f_{+}(x)$, where 
\begin{equation}
f_{-}(x)=\prod\limits_{\{\alpha _{i}\mid v_{p}(\alpha _{i})<0\}}(x-\alpha
_{i})^{e_{i}},\text{ and \ }f_{+}(x)=\prod\limits_{\{\alpha _{i}\mid
v_{p}(\alpha _{i})\geqq 0\}}(x-\alpha _{i})^{e_{i}}.  \label{pol1}
\end{equation}
From (\ref{const}) and (\ref{pol1}) follow that \ 
\begin{equation*}
Z(s,f)=\mid \alpha _{0}\prod\limits_{\{\alpha _{i}\mid v_{p}(\alpha
_{i})<0\}}\alpha _{i}{}^{e_{i}}\mid _{p}^{s}Z(s,f_{+}).
\end{equation*}
Thus, from a computational point of view, we may assume without loss of
generality that all roots of $f(x)$ are $p-$adic integers.
\end{remark}

\section{Trees and $p$-adic Numbers}

The tree \ $U=U(p)$ of residue classes modulo powers of a given prime number 
$p$ is defined as \ follows. Consider the diagram 
\begin{equation*}
\{0\}=\mathbb{Z}/p^{0}\mathbb{Z}\underleftarrow{\text{ \ }\phi _{1}}\text{ \ 
}\mathbb{Z}/p^{1}\mathbb{Z}\text{ \ }\underleftarrow{\phi _{2}}\text{ \ }%
\mathbb{Z}/p^{2}\mathbb{Z}\text{ }\underleftarrow{\phi _{3}}\cdots
\end{equation*}
where $\phi _{l}$\ the \ are the natural homomorphisms. The vertices of \ $U$
are the elements of $\mathbb{Z}/p^{l}\mathbb{Z}$, for \ $l=0,1,2,\mathbb{%
\cdots }$, and the directed edges are $u\rightarrow v$ where $u\in \mathbb{Z}%
/p^{l}\mathbb{Z}$ and \ $\phi _{l}(u)=v$, for some $l>0$. Thus $U$ is a
rooted tree with root $\{0\}$. Exactly one directed edge emanates \ from
each vertex of $U$; except from the vertex $\{0\}$, from which no edge
emanates. In addition, every vertex is the end point of exactly $p$ directed
edges.

Given two \ vertices $u$, $v$ the notation $u>v$ will mean that there is a
sequence of vertices and edges of the form 
\begin{equation*}
u\rightarrow u^{(1)}\rightarrow \cdots \rightarrow u^{(m)}=v\text{.}
\end{equation*}
The notation $u\geqq v$ \ will mean that $u=v$ or $u>v$. The\textit{\ level} 
$l(u)$ of a vertex $u$ is $m$ if $u\in \mathbb{Z}/p^{m}\mathbb{Z}$. The 
\textit{valence} $Val(u)$ of a vertex $u$ is defined as the number of
directed edges whose end point is $u$.

A subtree, or simply a tree, is defined as a nonempty subset $T$ of vertices
of $U$, such that when $u\in T$ and $u>v$, then \ $v\in T$. Thus \ $T$
together with the directed edges $u\rightarrow v$, where $u,v\in T$ , is
again a tree with root $\{0\}$.

A tree $T$ is named a \textit{weighted tree}, if there exists a weight
function $W:T\rightarrow \mathbb{N}$. The value $W(u)$ is called the weight
of vertex $u$.

If \ $x\in \mathbb{Z}_{p}$, and $x_{l}$ denotes its residue class modulo $%
p^{l}$, then every vertex of $U$ is of the type $x_{l}$ with $l\in \mathbb{N}
$.

A \textit{stalk} is defined as a tree $K$ having at most one vertex at each
level. Thus a stalk is either finite, of the type 
\begin{equation*}
\{0\}\longleftarrow u^{(1)}\longleftarrow \cdots \longleftarrow u^{(l)},
\end{equation*}
or infinite, of the type 
\begin{equation*}
\{0\}\longleftarrow u^{(1)}\longleftarrow \cdots \text{.}
\end{equation*}
Clearly a finite stalk may be written as \ 
\begin{equation*}
\{0\}\longleftarrow x_{1}\longleftarrow \cdots \longleftarrow x_{l},
\end{equation*}
with $x\in \mathbb{Z}$, and infinite stalks as 
\begin{equation*}
\{0\}\longleftarrow x_{1}\longleftarrow x_{2}\longleftarrow \cdots ,
\end{equation*}
with $x\in \mathbb{Z}_{p}$. Thus there is a $1-1$ correspondence between \
infinite stalks and $p-$adic integers.

\subsection{Tree Attached to a Polynomial}

Let 
\begin{equation}
f(x)=\alpha _{0}\prod\limits_{i=1}^{r}(x-\alpha _{i})^{e_{i}}\in \mathbb{Q}%
[x]  \label{pol}
\end{equation}
be a non-constant polynomial, in one variable,\ of degree $d_{f}$, such that 
$v_{p}(\alpha _{i})\geqslant 0$, $i=1,2,\mathbb{\cdots },r$. \ We \
associate to $f(x)$ and a \ prime number $p$ the integer 
\begin{equation*}
l_{f}=\left\{ 
\begin{array}{cc}
1+\max \{v_{p}(\alpha _{i}-\alpha _{j})\mid i\neq j\text{, }1\leq i\text{, }%
j\leq r\}\text{,} & \text{if \ }r\geqq 2\text{;} \\ 
1\text{, } & \text{if \ \ }r=1\text{.}
\end{array}
\right.
\end{equation*}
We set 
\begin{equation*}
\alpha _{i}=a_{0,i}+a_{1,i\text{ }}p+\mathbb{\cdots }+a_{j,i}\text{ }p^{j}+%
\mathbb{\cdots }+a_{l_{f},i}\text{ }p^{l_{f}}\text{ mod }p^{l_{f}+1}\text{, }
\end{equation*}
$a_{j,i}\in \{0,1,\mathbb{\cdots },p-1\}$, $j=0,1,\mathbb{\cdots },l_{f}$, $%
i=1,2,\mathbb{\cdots },r$, for the $p-$adic expansion modulo $p^{l_{f}+1}$
of \ $\alpha _{i}$. We attach a weighted tree $T(f$, $l_{f})$ to $f$ as
follows: 
\begin{equation}
T(f,l_{f},p)=T(f,l_{f})=\bigcup\limits_{i=1}^{r}K(\alpha _{i},l_{f}),
\label{tree}
\end{equation}
where $K(\alpha _{i},l_{f})$\ denotes the stalk corresponding to the $p-$%
adic expansion of $\alpha _{i}$\ modulo $p^{l_{f}+1}$. Thus $T(f$, $l_{f})$\
is a rooted tree. We introduce a weight function on $T(f$, $l_{f}),$\ by
defining the weight of a vertex $u$ of level $m$ as 
\begin{equation}
W(u)=\left\{ 
\begin{array}{cc}
\sum\limits_{\{i\mid \alpha _{i}\equiv u\text{ mod }p^{m}\}}e_{i}, & \text{%
if }\ m\geqq 1\text{;} \\ 
0, & \text{if }\ m=0\text{.}
\end{array}
\right.  \label{weight}
\end{equation}

Given a vertex $u\in T(f,l_{f})$, we define the stalk generated by $u$\ to
be 
\begin{equation*}
B_{u}=\{v\in T(f,l_{f})\mid u\geqq v\}.
\end{equation*}
\ We associate a weight $W^{\ast }(B_{u})$ to \ $B_{u}$ as follows: 
\begin{equation}
W^{\ast }(B_{u})=\sum\limits_{v\in B_{u}}W(v).  \label{weightstalk}
\end{equation}

\subsection{Computation of Trees Attached to \ Polynomials}

Our next step is to show that a tree $T(f,l_{f})$ attached to a polynomial $%
f(x)$, of type (\ref{pol}), can be computed in polynomial time. There are
well known programming techniques \ to construct and manipulate trees and
forests (see e.g. \cite[Volume 1]{K}), for this reason, we shall focus on
showing \ that such computations can be carry out in polynomial time, and
set aside the\ implementation details of a particular algorithm for this
task. We shall include in the computation of \ $T(f,l_{f})$, the computation
of the weights of the stalks generated by its vertices; because all these
data will be used in the computation of the local zeta function of $f$.

\begin{proposition}
\label{prop4.1}The computation of a tree $T(f,l_{f})$ attached to a
polynomial $f(x)$, of type (\ref{pol}), \ from the \ $p-$adic expansions
modulo $p^{l_{f}+1}$\ of its roots 
\begin{equation*}
\alpha _{i}=a_{0,i}+a_{1,i\text{ }}p+\mathbb{\cdots }+a_{l_{f},i}p^{l_{f}}%
\text{ mod }p^{l_{f}+1}\text{ }
\end{equation*}
and multiplicities $e_{i}$, $i=1,2,\mathbb{\cdots },r$, involves \ $O(l_{f%
\text{ }}^{2}d_{f}^{3})$ arithmetic operations on integers with binary
length 
\begin{equation*}
O(\max \{\log p,\log (l_{f}d_{f})\}).
\end{equation*}
\end{proposition}

\begin{proof}
We assume that $T(f,l_{f})$ is finite set of the form 
\begin{equation}
T=\{\text{Level}_{0}\text{,}\cdots \text{,Level}_{j}\text{,}\cdots \text{%
,Level}_{l_{f}+1}\}\text{,}  \label{tipotree}
\end{equation}
where \ Level$_{j}$ represents the set of all vertices with level $j$. Each
Level$_{j}$ is a set of the form 
\begin{equation*}
Level_{j}=\{u_{j,1},\mathbb{\cdots },u_{j,i},\mathbb{\cdots },u_{j,m_{j}}\},
\end{equation*}
and each $u_{j,i}$ is a weighted vertex for every $i=1,\mathbb{\cdots },m_{j}
$. A \ weighted vertex $u_{j,i}$ is a set of the form 
\begin{equation*}
u_{j,i}=\{\text{ }W(u_{j,i})\text{, }Val(u_{j,i}),W^{\ast }(B_{u_{j,i}})\}%
\text{,}
\end{equation*}
where $W(u_{j,i})$ \ is the weight of $u_{j,i}$, $Val(u_{j,i})$ is its
valence, and $W^{\ast }(B_{ui})$ is \ the weight of \ stalk $B_{u_{j,i}}$.
The weight of the stalk generated by \ $u_{j,i}$ can be written as 
\begin{equation*}
W^{\ast }(B_{u_{j,i}})=\sum\limits_{v\in B_{u_{j,i}}}W(v).
\end{equation*}

For the computation of a vertex \ $u_{j,i}$\ of level $j$, we proceed as
follows. We put $I=\{1,2,\mathbb{\cdots },r\},$ and 
\begin{equation*}
M_{j}=\{\alpha _{i}\text{ mod }p^{j}\mid i\in I\}.
\end{equation*}
For each \ $0\leq j\leq l_{f}+1$, we compute a partition of $I$ of type 
\begin{equation}
I=\bigcup\limits_{i=1}^{l_{j}}I_{j,i},  \label{parti}
\end{equation}
such that 
\begin{equation*}
\alpha _{t}\text{ mod }p^{j}=\alpha _{s}\text{ mod }p^{j},
\end{equation*}
for every $t,s\in I_{j,i}$. Each subset $I_{j,i}$\ corresponds \ to a vertex 
$u_{j,i}$\ of level $j$. This \ computation requires\ $O(l_{f}r^{2})$
arithmetic operations on integers with binary length $O(\log p)$. Indeed,
the cost of computing a ``yes or no'' answer for the question: $\alpha _{t}$
mod $p^{j}=\alpha _{s}$ mod $p^{j}?$ is $O(j)$ comparisons of integers with
binary length $O(\log p)$. In the worst case, there are $r$ vectors $M_{j}$,
\ and the computation of partition (\ref{parti}), for a fixed $j$, involves
the comparison of $\alpha _{t}$ with $\alpha _{l}$ for $l=t+1,t+2,\mathbb{%
\cdots },r$. This computation requires\ $O(jr^{2})$ arithmetic operations on
integers with binary length $O(\log p)$. Since $j\leqq l_{f}+1$, the
computation of partition (\ref{parti}) requires\ $O(l_{f}r^{2})$ arithmetic
operations on integers with binary length $O(\log p)$.

The weight of the vertex \ $u_{j,i}$\ is given by the expression 
\begin{equation*}
W(u_{j,i})=\sum\limits_{k\in I_{j,i}}e_{k}.
\end{equation*}
Thus the computation of the weight of a vertex requires $O(r)$ additions of
integers with binary length $O(\log d_{f}r)$.

For the computation of the valence of \ $u_{j,i}$, we proceed as follows.
The valence of $u_{j,i}$ \ can be expressed as 
\begin{equation*}
Val(u_{j,i})=\text{Card}\{I_{j+1,l}\mid I_{j+1,l}\subseteq I_{j,i}\},
\end{equation*}
where $I_{j+1,l}$ runs through all possible sets that correspond to the \
vertices $u_{j+1,l}$, with level $j+1$. Thus the computation of $Val(u_{j,m})
$\ involves \ the computation of $\ $a ``yes or no'' answer for the question 
$I_{j+1,l}\subseteq I_{j,i}$? The computation of a\ ``yes or no'' answer \
involves $O(r)$\ comparisons of integers with binary length $O(\log r)$.
Therefore the computation of $Val(u_{j,i})$\ involves $O(r)$\ comparisons
and $O(r)$ additions of integers with binary length $O(\log r)$.

For the computation of the weight of \ $B_{u_{j,i}}$, we observe that $%
W^{\ast }(B_{u_{j,i}})$ is given by the formula 
\begin{equation*}
W^{\ast }(B_{u_{j,i}})=\sum\limits_{l=0}^{j-1}\sum\limits_{I_{j,i}\subseteq
I_{l,k}}W(I_{l,k}),
\end{equation*}
where $W(I_{l,k})=W(v_{l,k})$, and $v_{l,k}$\ is \ the vertex corresponding
to $I_{l,k}$. Thus the computation of $W^{\ast }(B_{u_{j,i}})$ involves $%
O(l_{f})$ additions of integers with binary length $O(\log (l_{f}$ $d_{f}))$%
, and $O(l_{f}$ $r)$ comparisons of integers with binary length $O(\log r)$.

From the above reasoning follows that the computation of a vertex of a tree $%
T(f,l_{f})$ \ involves at most $O(l_{f}$ $r^{2})$ arithmetic operations
(additions and comparisons) on integers with binary length $O(\max \{\log p,$
$\log ($ $l_{f}$ $d_{f})\})$. Finally, since the number of vertices of $%
T(f,l_{f})$ is at most $O(l_{f}$ $d_{f})$, it follows that \ the computation
of a tree of type $T(f,l_{f})$ involves $O(l_{f}^{2}$ $d_{f}^{3})$
arithmetic operations on integers with binary length $O(\max \{\log p,$ $%
\log ($ $l_{f}$ $d_{f})\})$.
\end{proof}

\section{Generating Functions and Trees}

In this section we attach to a weighted tree $T(f,l_{f})$ and a \ prime $p$
a generating function $G(s,T(f,l_{f}),p)\in \mathbb{Q}(p^{-s})$ defined \ as
follows.

We set 
\begin{equation*}
\mathcal{M}_{T(f,l_{f})}=\left\{ u\in T(f,l_{f})\left| 
\begin{array}{c}
W(u)=1\text{, and there no exists }v\in T(f,l_{f}) \\ 
\text{with }W(v)=1\text{, such that }u>v.
\end{array}
\right. \right\} ,
\end{equation*}

and

\begin{equation*}
L_{u}(p^{-s})=\left\{ 
\begin{array}{cc}
\frac{(1-p^{-1})p^{-l(u)-W^{\ast }(B_{u})s}}{(1-p^{-1-W(u)s})}\text{, \ if}
& l(u)=1+l_{f}\text{, and \ }W(u)\geqq 2\text{;} \\ 
&  \\ 
p^{-1}(p-Val(u))p^{-l(u)-W^{\ast }(B_{u})s}\text{, \ if} & 0\leqq l(u)\leqq
l_{f}\text{, and \ }W(u)\neq 1\text{;} \\ 
&  \\ 
\frac{(1-p^{-1})p^{-l(u)-W^{\ast }(B_{u})s}}{1-p^{-1-s}}\text{, \ \ if} & 
u\in \mathcal{M}_{T(f,l_{f})}\text{;} \\ 
&  \\ 
0\text{,\ \ \ if} & W(u)=1\text{, and }u\notin \mathcal{M}_{T(f,l_{f})}\text{%
.}
\end{array}
\right. 
\end{equation*}

With all the above notation, we define the generating function attached to $%
T(f,l_{f})$ and $p$\ \ as 
\begin{equation}
G(s,T(f,l_{f}),p)=\sum\limits_{u\in T(f,l_{f})}L_{u}(p^{-s})\text{.}
\label{Gfunction}
\end{equation}

Our next goal is to show that $G(s,T(f,l_{f}),p)=Z(s,f)$. The proof of this
fact requires the following preliminary result.

\begin{proposition}
The generating function attached to a tree $T(f,l_{f})$ and a prime $p$
satisfies 
\begin{eqnarray}
G(s,T(f,l_{f}),p) &=&p^{-1}\nu (\overline{f})+\delta (\overline{f})\frac{%
(1-p^{-1})p^{-1-s}}{(1-p^{-1-s})}  \notag \\
&&+\sum\limits_{\xi \in S}p^{-1-e_{\xi }s}G(s,T(f_{\xi },l_{f}-1),p).
\label{ident}
\end{eqnarray}
\end{proposition}

\begin{proof}
Let $A_{f}=\{u\in T(f,l_{f})\mid l(u)=1$, $W(u)=1\},$ and $B_{f}=\{u\in
T(f,l_{f})\mid l(u)=1$, $W(u)\geqq 2\}$. We have the following \ \ partition
for $T(f,l_{f}):$%
\begin{equation}
T(f,l_{f})=\{0\}\bigcup A_{f}\bigcup \left( \bigcup_{u\in B_{f}}T_{u}\right) 
\text{,}  \label{parti1}
\end{equation}
with 
\begin{equation*}
T_{u}=\{v\in T(f,l_{f})\mid v\geqq u\}.
\end{equation*}
Each $T_{u}$\ is a rooted tree with root $\{u\}$.\ \ From \ partition (\ref
{parti1}) and the definition of \ $G(s,T(f,l_{f}),p)$, it follows that 
\begin{eqnarray}
G(s,T(f,l_{f}),p) &=&p^{-1}\left( p-Val(\{0\})\right) +\text{Card}\{A_{f}\}%
\frac{(1-p^{-1})p^{-1-s}}{(1-p^{-1-s})}+  \notag \\
&&\sum\limits_{u\in B_{f}}G(s,T_{u}),  \label{ident0}
\end{eqnarray}
with $G(s,T_{u})=\sum\limits_{v\in T_{u}}L_{v}(p^{-s})$.

Since there exists a bijective correspondence between the roots of $%
\overline{f}(x)\equiv 0$ mod $p$ and the vertices $\ $of $T(f,l_{f})$\ with
level $1$, $\ \ \ \ \ $%
\begin{equation}
\ \ p-Val(\{0\})=\nu (\overline{f})\text{, and \ Card}\{A_{f}\}=\delta (%
\overline{f}).  \label{ident1}
\end{equation}

Now, if the vertex $u$ corresponds to the root \ $\overline{f}(\xi )\equiv 0$
mod $p$, $\ $\ then 
\begin{equation}
T_{u}=\left( \bigcup\limits_{\{\alpha _{i}\mid \alpha _{i}\equiv \xi \text{
mod }p\}}K(\alpha _{i},l_{f})\right) \setminus \{0\}.
\end{equation}
On the other hand, $\ $we have that 
\begin{equation}
T(f_{\xi },l_{f}-1)=\bigcup\limits_{\{\alpha _{i}\mid \alpha _{i}\equiv \xi 
\text{ mod }p\}}K(\frac{\alpha _{i-\xi }}{p},l_{f}-1).
\end{equation}
Now \ we remark that the map $\alpha _{i}\rightarrow \frac{\alpha _{i}-\xi }{%
p}$ induces a isomorphism between the trees $T_{u}$ and \ $T(f_{\xi
},l_{f}-1)$, that preserves the weights of the vertices; and \ thus we may
suppose that $T_{u}$ $=$\ $T(f_{\xi },l_{f}-1)$.\ The level function $l_{T}$
of $T(f_{\xi },l_{f}-1)$ is related to the level function $l_{T_{u}}$ of $%
T_{u}$ by means of the equality $l_{T}$ $-l_{T_{u}}=-1$. In addition, $B_{f}=
$ $S$, where $S$ is the subset of $\{0,1,\mathbb{\cdots },p-1\}\subseteq 
\mathbb{Z}_{p}$ whose reduction modulo $pZ_{p}$ is equal to the set of roots
of \ $\overline{f}(\xi )=0$ with multiplicity greater or equal than two. \
Therefore, it holds that \ 
\begin{equation}
G(s,T_{u})=p^{-1-e_{\xi }s}G(s,T(f_{\xi },l_{f}-1),p).  \label{ident2}
\end{equation}
The result follows from (\ref{ident0}) by the identities (\ref{ident1}) and (%
\ref{ident2}).
\end{proof}

\begin{lemma}
\label{lemma}Let $p$ be a fixed prime number and $v_{p}$ the corresponding $%
p-$adic valuation, and 
\begin{equation*}
f(x)=\alpha _{0}\prod\limits_{i=1}^{r}(x-\alpha _{i})^{e_{i}}\in \mathbb{Q}%
[x]\setminus \mathbb{Q},
\end{equation*}
a polynomial such that $v_{p}(\alpha _{i})\geqq 0$, for $i=1,\cdots ,r$.
Then 
\begin{equation*}
Z(s,f)=G(s,T(f,l_{f}),p).
\end{equation*}
\end{lemma}

\begin{proof}
We proceed by induction on $l_{f}$.

Case\ $l_{f}=1$

If $r=1$ the proof follows immediately, thus we may assume that $r\geqq 2$.
Since $l_{f}=1$, it holds that $v_{p}(\alpha _{i}-\alpha _{j})=0$, for every 
$i$, $j$, satisfying $i\neq j$, and thus \ $\overline{\alpha _{i}}\neq 
\overline{\alpha _{j}}$, if \ $i\neq j$. By applying SPF, we have that 
\begin{equation}
Z(s,f)=p^{-1}\nu (\overline{f})+\delta (\overline{f})\frac{(1-p^{-1})p^{-1-s}%
}{(1-p^{-1-s})}+\sum\limits_{\xi \in S}p^{-1-e_{\xi }s}\frac{(1-p^{-1})}{%
(1-p^{-1-e_{\xi }s})},
\end{equation}
where each $e_{\xi }=e_{j}\geqq 2$, for some $j$, and \ $\alpha _{j}=\xi
+p\beta _{j}$.

\ On the other hand, $T(f,l_{f})$ \ is a rooted tree with $r$ vertices $v_{j}
$, satisfying $l(v_{j})=1$, and $W(v_{j})=e_{j}$,\ for $j=1,\cdots ,r$.
These observations allow one to deduce that $Z(s,f)=G(s,T(f,l_{f}),p)$.

By induction hypothesis, we may assume that \ $Z(s,f)=G(s,T(f,l_{f}),p)$,
for every polynomial $f$ satisfying both the \ hypothesis of the lemma, and
the condition \ $1\leqq l_{f}\leqq k$, $k\in \mathbb{N}$.

Case\ $l_{f}=k+1$, $k\in \mathbb{N}$

Let $f(x)$ \ be \ a polynomial satisfying the lemma's \ hypothesis, and \ $%
l_{f}=k+1$, $k\geqq 1$. By applying SPF, we obtain that 
\begin{equation}
Z(s,f)=p^{-1}\nu (\overline{f})+\delta (\overline{f})\frac{(1-p^{-1})p^{-1-s}%
}{(1-p^{-1-s})}+\sum\limits_{\xi \in S}p^{-1-e_{\xi }s}\int \mid f_{\xi
}(x)\mid _{p}^{s}dx.  \label{eq1}
\end{equation}
Now, since $l_{f_{\xi }}=l_{f}-1$, for every \ $\xi \in S$, it follows from
the induction hypothesis applied to each \ $f_{\xi }(x)$ in (\ref{eq1}),
that 
\begin{equation}
Z(s,f)=p^{-1}\nu (\overline{f})+\delta (\overline{f})\frac{(1-p^{-1})p^{-1-s}%
}{(1-p^{-1-s})}+\sum\limits_{\xi \in S}p^{-1-e_{\xi }s}G(s,T(f_{\xi
},l_{f}-1),\text{ }p).  \label{eq3}
\end{equation}
Finally, from\ identity (\ref{ident}), and (\ref{eq3}), we conclude that 
\begin{equation}
Z(s,f)=G(s,T(f,l_{f}),p).  \label{eq4}
\end{equation}
\end{proof}

The following proposition gives a complexity estimate for the computation of 
$G(s,T(f,l_{f}),p)$.

\begin{proposition}
\label{prop4.2}The computation of the generating function \ 
\begin{equation*}
G(s,T(f,l_{f}),p)
\end{equation*}
from $T(f,l_{f})$, involves $O(l_{f}$ $d_{f})$ arithmetic operations on
integers with binary length \ $O(\max \{\log p,$ $\log ($ $l_{f}$ $d_{f})\})$%
.
\end{proposition}

\begin{proof}
This is a consequence of proposition \ref{prop4.1},\ and the definition of
generating function.
\end{proof}

\section{Computation of $p$-adic Expansions}

In this section we estimate the complexity of the steps $2$ and $3$ in \ the
algorithm Compute\_$Z(s,f)$.

\begin{proposition}
\label{prop4.3}Let 
\begin{equation*}
B=\max_{
\begin{array}{c}
{1\leq i,}\text{ }{j\leq r} \\ 
{i\neq j}
\end{array}
}{\{}\mid c_{j,i}\mid \text{,}\mid d_{j,i}\mid \text{ \ }{\mid }\text{ }%
\alpha _{j}-\alpha _{i}=\frac{c_{j,i}}{d_{j,i}}\text{, }c_{j,i}\text{, }%
d_{j,i}\in \mathbb{Z}\setminus \{0\}{\}}.
\end{equation*}
The computation of the integer $l_{f}$ involves $O(d_{f}^{2}\frac{\log B}{%
\log p})$ arithmetic operations on integers with binary length $O(\max
\{\log B,\log p\})$.
\end{proposition}

\begin{proof}
First, we observe that for $c\in \mathbb{Z}\setminus \{0\}$, \ the
computation of $v_{p}(c)$ \ involves $O(\frac{\log \mid c\mid }{\log p})$
divisions of integers of binary length $O(\max \{\log \mid c\mid ,$ $\log
p\})$. Thus the computation of $v_{p}(\frac{c}{d})=v_{p}(c)-v_{p}(d),$ \
involves $O(\frac{\max \{\log \mid c\mid ,\text{ }\log \mid d\mid \}}{\log p}%
)$ divisions and subtractions of integers with binary length 
\begin{equation*}
O(\max \{\log \mid c\mid ,\log \mid d\mid ,\log p\}).
\end{equation*}
From these observations follow that the computation of $v_{p}(\alpha
_{j}-\alpha _{i})$, $i\neq j$, $1\leq i$, $j\leq r$, involves $O(r^{2}\frac{%
\log B}{\log p})$ arithmetic operations on integers with binary length $%
O(\max \{\log B,\log p\})$. Finally, the computation of the maximum of the $%
v_{p}(\alpha _{j}-\alpha _{i})$, $i\neq j$, $1\leq i$, $j\leq r$, involves $%
O(\log r)$ comparisons of integers with binary length $O(\max \{\log B,\log
p\})$. Therefore the computation of the integer $l_{f}$ involves at most $%
O(d_{f}^{2}\frac{\log B}{\log p})$ arithmetic operations on integers with
binary length $O(\max \{\log B,\log p\})$.
\end{proof}

\begin{proposition}
Let \ $p$ be a fixed prime and $\gamma =\frac{c}{b}\in \mathbb{Q}$, with $%
c,b\in \mathbb{Z}\setminus \{0\}$, and $v_{p}(\gamma )\geqq 0$. The $p-$adic
expansion 
\begin{equation*}
\gamma =a_{0}+a_{1\text{ }}p+\mathbb{\cdots }+a_{j}p^{j}+\mathbb{\cdots }%
+a_{m}p^{m},
\end{equation*}
modulo $p^{m+1}$ involves $O(m+\log (\max \{\mid b\mid ,$ $p\}))$\
arithmetic operations on integers with binary length $O(\max \{\log \mid
c\mid ,\log \mid b\mid ,\log p\})$.
\end{proposition}

\begin{proof}
Let $y\in \{1,\cdots ,p-1\}$ be an integer \ such that $yb\equiv 1$ mod $p$.
This integer \ can be computed \ by means of the Euclidean algorithm in $%
O(\log (\max \{\mid b\mid ,p\}))$ \ arithmetic operations \ involving
integers of binary length $O(\max \{\log \mid b\mid ,\log p\})$ (cf. 
\cite[Volume 2, section 4.5.2]{K}).

We set $\gamma =\gamma _{0}=\frac{c}{b}$, $c_{0}=c$, and define \ $%
a_{0}\equiv yc$ mod $p$. With this notation, the $p-$adic digits $a_{i},i=1$,%
$\cdots $, $m$, can be computed recursively as follows: 
\begin{equation*}
\gamma _{i}=\frac{\frac{\left( c_{i-1}-a_{i-1}b\right) }{p}}{b}=\frac{c_{i}}{%
b},
\end{equation*}
\begin{equation*}
a_{i}=yc_{i}\text{ mod }p.
\end{equation*}
Thus the computation of the $p-$adic expansion of $\gamma $ \ needs \ $%
O(m+\log (\max \{\mid b\mid ,p\}))$\ arithmetic operations on integers with
binary length 
\begin{equation*}
O(\max \{\log \mid c\mid ,\text{ }\log \mid b\mid ,\text{ }\log p\}).
\end{equation*}
\end{proof}

\begin{corollary}
\label{cor4.4}Let $p$ be a fixed prime number and $v_{p}$ the corresponding $%
p-$adic valuation, and 
\begin{equation*}
f(x)=\alpha _{0}\prod\limits_{i=1}^{r}(x-\alpha _{i})^{e_{i}}\in \mathbb{Q}%
[x],
\end{equation*}
a non-constant polynomial such that $v_{p}(\alpha _{i})\geqq 0$, $i=1,\cdots
,r$. The computation of \ the $p-$adic expansions modulo $p^{l_{f}+1}$\ of
the roots $\alpha _{i}$, $i=1,2,\cdots ,r$, of $f(x)$\ \ involves $O(d_{f}$ $%
l_{f}+d_{f}$ $\log (\max \{B,p\}))$\ arithmetic operations \ on integers
with binary length \ $O(\max \{\log B,\log p\})$.
\end{corollary}

\begin{proof}
The corollary \ follows directly from the two previous propositions.
\end{proof}

\section{Computing local zeta functions of polynomials with splitting $%
\mathbb{Q}$}

In this section we prove the \ correctness of the algorithm Compute\_$Z(s,f)$
and estimate its complexity.

\begin{theorem}
\label{theoA}The algorithm Compute\_$Z(s,f)$ \ outputs\ the meromorphic
continuation of the Igusa local zeta function $Z(s,f)$ of a polynomial \ $%
f(x)\in \mathbb{Z}[x]$, in one variable, with splitting field \ $\mathbb{Q}$%
. The number of arithmetic operations needed by the algorithm is 
\begin{equation*}
O\left( d_{f}^{6}+d_{f}^{9}\log (\shortparallel f\shortparallel
)+l_{f}^{2}d_{f}^{3}+d_{f}^{2}\log \left( \max \{B,p\}\right) \right) ,
\end{equation*}
and the integers on which these operations \ are performed have a binary
length 
\begin{equation*}
O\left( \max \{\log p\text{, }\log l_{f}d_{f}\text{, }\log B\text{, }%
d_{f}^{3}+d_{f}^{2}\log (\shortparallel f\shortparallel )\}\right) \text{.}
\end{equation*}
\end{theorem}

\begin{proof}
By remark (\ref{remark}), we may assume without loss of generality that 
\begin{equation*}
f(x)=\alpha _{0}\prod\limits_{i=1}^{r}(x-\alpha _{i})^{e_{i}}\in \mathbb{Q}%
[x]\setminus \mathbb{Q},
\end{equation*}
with $v_{p}(\alpha _{i})\geqq 0$, $i=1,\cdots ,r$. The correctness of the
algorithm follows from lemma \ \ref{lemma}. The complexity estimates are
obtained as follows: the number of arithmetic operations \ needed in the
steps 2 (cf. proposition \ref{prop4.3}), 3 (cf. \ corollary \ref{cor4.4}), 4
(cf. proposition \ref{prop4.1}), 5 (proposition\ \ref{prop4.2}), and 6 is at
most 
\begin{equation*}
O\left( l_{f}^{2}d_{f}^{3}+d_{f}^{2}\log \left( \max \{B,p\}\right) \right) 
\text{;}
\end{equation*}
and these operations are performed on integers \ whose binary length is at
most 
\begin{equation*}
O\left( \max \{\log p\text{, }\log l_{f}d_{f}\text{,}\log B\}\right) .
\end{equation*}
The estimates for the whole algorithm \ follow from the above estimates and
those of \ the factoring algorithm by \ A. K. Lenstra, H. Lenstra and L. Lov%
\'{a}sz (see theorem 3.6 of \cite{L-L-L}).
\end{proof}

\section{Stream Ciphers and Poincar\'{e} series}

There is a natural connection between Poincar\'{e} series and stream
ciphers. In order to explain this relation, we recall some basic facts about
stream ciphers \ \cite{R}. \ Let $\mathbb{F}_{p^{n}}$ be a finite field with 
$p^{n}$ elements, with $p$ a prime number. \ For any integer $r>0$ and $r$\
fixed elements $q_{i}\in \mathbb{F}_{p^{n}}$, $i=1,\mathbb{\cdots },r$\
(called taps), a Linear Feedback Shift Register, abbreviated LFSR, of length 
$r$ consists of $r$ cells with initial contents $\left\{ a_{i}\in \mathbb{F}%
_{p^{n}}\mid i=1,\mathbb{\cdots },r\right\} $. For any $n\geqslant r$, if
the current state is $(a_{n-1},\mathbb{\cdots },a_{n-r})$, then $a_{n}$ is
determined by the linear recurrence relation 
\begin{equation*}
a_{n}=-\sum\limits_{i=1}^{r}a_{n-i}q_{i}.
\end{equation*}
The device outputs the rightmost element $a_{n-r}$, shifts all the cells one
unit right, and feeds $a_{n}$ back to the leftmost cell. 

Any configuration of the $r$ cells \ forms a state of the LSFR. If $%
q_{r}\neq 0$, the following polynomial \ $q(x)\in \mathbb{F}_{p^{n}}[x]$ of
degree $r$\ appears in the analysis of LFSRs: 
\begin{equation*}
q(x)=q_{0}+q_{1}x+\mathbb{\cdots }.+q_{r}x^{r}\text{ \ with }q_{0}=-1\text{.}
\end{equation*}
This polynomial is called the connection polynomial. An infinite sequence $%
A=\left\{ a_{i}\in \mathbb{F}_{p^{n}}\mid i\in \mathbb{N}\right\} $ has
period $T$ if for any $i\geqslant 0$, \ $a_{i+T}=a_{i}$. Such a sequence is
called periodic. If this is only true for $i$ greater than some index $i_{0}$%
, then the sequence is called eventually periodic. The following facts about
an LFSR of length $r$ are well-known \cite{R}.

\begin{enumerate}
\item  There are only finitely many possible states, and the state with all
the cells zero will produce a $0-$sequence. The output sequence is
eventually periodic and the maximal period is $p^{nr}-1$.

\item  The Poincar\'{e} series $\ g(x)=\sum\limits_{i=0}^{\infty }a_{i}x^{i}$
associated with the output sequence is called the generating function of the
sequence. It is a rational function over $\mathbb{F}_{p^{n}}$\ of the form $%
g(x)=\frac{L(x)}{R(x)}$, with $L(x)$, $R(X)$ $\in \mathbb{F}_{p^{n}}[x]$, $%
deg(R(X))<r$. The output sequence is strictly periodic if and only if $%
deg(L(X))<deg(R(X))$.

\item  There is a one-to-one correspondence between LFSRs of length $r$ with 
$q_{r}\neq 0$ and rational functions $\frac{L(x)}{R(x)}$ with $deg(R(X))=r$
and $deg(L(X))<r$.
\end{enumerate}

We set $\mathbb{F}_{p^{n}}(x)$ for the field of rational functions over $%
\mathbb{F}_{p^{n}}$, and $N^{\infty }(\mathbb{F}_{p^{n}})$ for the set of
sequences \ of the form $\{b_{0},\mathbb{\cdots },b_{u}\}$, $b_{i}\in 
\mathbb{F}_{p^{n}}$, $\ 0\leq i\leq u$, $u\in \mathbb{N}$. From the above
considerations, it is possible to identify an LFSR with a function $F_{u}$, $%
u\in \mathbb{N}$, defined as follows: 
\begin{equation}
\begin{array}{cccc}
F_{u}: & \mathbb{F}_{p^{n}}(x) & \rightarrow & N^{\infty }(\mathbb{F}%
_{p^{n}}) \\ 
& \sum\limits_{i=0}^{\infty }a_{i}x^{i} & \rightarrow & \{a_{0},\mathbb{%
\cdots },a_{u}\}.
\end{array}
\label{A}
\end{equation}
We set 
\begin{equation*}
\mathcal{H}=\{H(t,f)\mid f(x)\in \mathbb{Z}[x]\text{, in \ one variable,
with splitting field }\mathbb{Q}\},
\end{equation*}
and $N^{\infty }$ $\left( \mathbb{Z}\right) $\ for the set \ of finite
sequences of integers. Also, for each $u\in \mathbb{N}$, and a prime number $%
p$, we define 
\begin{equation}
\begin{array}{cccc}
F_{u,p}: & \mathcal{H} & {\ \rightarrow } & \mathbb{N}^{\infty }\left( 
\mathbb{Z}\right) \\ 
& H(t,f) & {\ \rightarrow } & \{N_{0}(f,p),N_{1}(f,p),\mathbb{\cdots }%
,N_{u}(f,p)\}\text{.}
\end{array}
\label{B}
\end{equation}
Thus the mappings $F_{u,p}$ can be seen as LFSRs, or stream ciphers, over $%
\mathbb{Z}$. If we replace each $N_{u}(f,p)$ by its binary representation,
then the $\ F_{u,p}$ are LFSRs. For practical purposes it is necessary that $%
F_{u,p}$ \ can be computed efficiently, i.e., in polynomial time. With the
above notation our second result is the following.

\begin{theorem}
\label{theoB} For every $H(t,f)$\ $\in $ $\mathcal{H}$, the computation of \ 
$F_{u,p}(H(t,f))$ involves $O(u^{2}d_{f}l_{f})$ arithmetic operations, and
the integers on which these operations are performed have binary length 
\begin{equation*}
O(\max \{\text{ }(l_{f}+u)\log p,\text{ }\log (d_{f}l_{f})\}).
\end{equation*}
\end{theorem}

The proof of this theorem will be given at the end of this section. This
proof requires some preliminary results. We set $t=q^{-s}$, and 
\begin{equation*}
Z(s,f)=Z(t,f)=\sum\limits_{m=0}^{\infty }c_{m}(f,p)t^{m},
\end{equation*}
with $c_{m}(f,p)=vol(\{x\in \mathbb{Z}_{p}\mid v_{p}(f(x))=m\})$.

\begin{proposition}
Let $f(x)\in \mathbb{Z}[x]\setminus \mathbb{Z}$ be a polynomial in one
variable and $p$ a prime number. The following formula holds for $N_{n}(f,p)$%
: 
\begin{equation}
N_{n}(f,p)=\left\{ 
\begin{array}{ccc}
1\text{,} & \text{if} & n=0\text{;} \\ 
p^{n}\left( 1-\sum\limits_{j=1}^{n}c_{j-1}(f,p)\right) \text{,} & \text{if}
& n\geqslant 1\text{.}
\end{array}
\right.  \label{For1}
\end{equation}
\end{proposition}

\begin{proof}
The result follows by comparing \ the coefficient of $t^{n}$ of the series 
\begin{equation*}
\sum\limits_{n=0}^{\infty }\frac{N_{n}(f,p)}{p^{n}}t^{n}\text{ \ \ and \ }%
\sum\limits_{n=0}^{\infty }d_{n}t^{n}\text{,}
\end{equation*}
in the following equality : 
\begin{equation*}
H(t,f)=\sum\limits_{n=0}^{\infty }\frac{N_{n}(f,p)}{p^{n}}t^{n}=\frac{%
1-t\left( \sum\limits_{m=0}^{\infty }c_{m}(f,p)t^{m}\right) }{1-t}%
=\sum\limits_{n=0}^{\infty }d_{n}t^{n}.
\end{equation*}
\end{proof}

We associate to each $u\in T(f,l_{f})$, and $j\in \mathbb{N}$, a rational
integer $a_{j}(u)$ defined as follows:

\begin{equation}
a_{j}(u)=\left\{ 
\begin{array}{cc}
\frac{(p-1)}{p^{l(u)+1+y(u)}}\text{, \ if} & 
\begin{array}{c}
l(u)=1+l_{f}\text{, }W(u)\geqq 2\text{, }j=W^{\ast }(B_{u})+y(u)W(u)\text{,}
\\ 
\text{for some }y(u)\in \mathbb{N}\text{;}
\end{array}
\\ 
&  \\ 
\frac{(p-Val(u))}{p^{l(u)+1}}\text{, \ if} & 0\leqq l(u)\leqq l_{f}\text{, }%
W(u)\neq 1\text{, }j=W^{\ast }(B_{u})\text{;} \\ 
&  \\ 
\frac{(p-1)}{p^{l(u)+1+y(u)}}\text{, \ if} & 
\begin{array}{c}
u\in \mathcal{M}_{T(f,l_{f})},j=W^{\ast }(B_{u})+y(u)\text{,} \\ 
\text{for some }y(u)\in \mathbb{N}\text{;}
\end{array}
\\ 
&  \\ 
0\text{, \ \ \ \ \ \ \ \ \ \ \ if} & W(u)=1\text{, and }u\notin \mathcal{M}%
_{T(f,l_{f})}\text{;} \\ 
&  \\ 
0\text{, \ \ \ \ \ \ \ \ \ \ \ \ } & \text{in other cases.}
\end{array}
\right.  \label{For2}
\end{equation}

\begin{proposition}
Let $f(x)\in \mathbb{Z}[x]\setminus \mathbb{Z}$ be a polynomial in one
variable, with splitting field $\mathbb{Q}$, and $p$ a prime number. The
following formula holds: 
\begin{equation}
c_{j}(f,p)=\sum\limits_{u\in T(f,l_{f})}a_{j}(u),\text{ }j\geqq 0.
\label{For4}
\end{equation}
\end{proposition}

\begin{proof}
As a consequence of lemma (\ref{lemma}), we have the following identity: 
\begin{equation}
Z(t,f)=\sum\limits_{u\in T(f,l_{f})}L_{u}(t),  \label{For4a}
\end{equation}
with 
\begin{equation}
L_{u}(t)=\left\{ 
\begin{array}{cc}
\frac{(p-1)t^{W^{\ast }(B_{u})}}{p^{l(u)+1}(1-p^{-1}t^{\text{ }W(u)})}\text{%
, \ if} & l(u)=1+l_{f}\text{, }W(u)\geqq 2\text{;} \\ 
&  \\ 
\frac{(p-Val(u))}{p^{l(u)+1}}t^{W^{\ast }(B_{u})}\text{, \ if} & 0\leqq
l(u)\leqq l_{f}\text{, }W(u)\neq 1\text{;} \\ 
&  \\ 
\frac{(p-1)t^{W^{\ast }(B_{u})}}{p^{l(u)+1}(1-p^{-1}t)}\text{, \ if} & u\in 
\mathcal{M}_{T(f,l_{f})}\text{;} \\ 
&  \\ 
0\text{, \ \ \ \ \ if} & W(u)=1\text{, and }u\notin \mathcal{M}_{T(f,l_{f})}.
\end{array}
\right.  \label{For5}
\end{equation}

The result follows by comparing the coefficient of $t^{j}$ in the series $%
Z(t,f)=\sum\limits_{m=0}^{\infty }c_{m}(f,p)t^{m}$, and $Z(t,f)=\sum%
\limits_{u\in T(f,l_{f})}L_{u}(t)$.
\end{proof}

\begin{proposition}
\label{prop8}Let $f(x)\in \mathbb{Z}[x]\setminus \mathbb{Z}$ be a polynomial
in one variable, with splitting field $\mathbb{Q}$, and $p$ a prime number.

\begin{enumerate}
\item  The computation \ of \ $N_{n}(f,p)$, $n\geqq 1$, \ from \ the $%
c_{j-1}(f,p)$, $j=1,\mathbb{\cdots },n$, involves \ $O(n)$ \ \ arithmetic
operations on integers with binary length \ $O(n\log p)$.

\item  The computation \ of \ $c_{j}(f,p)$, $j\geqq 0$, \ from \ $Z(t,f)$,
involves \ $O(d_{f}l_{f})$ \ \ arithmetic operations on integers \ with
binary length \ 
\begin{equation*}
\mathit{O}(\max \{(j+l_{f})\log p,\log p,\log (d_{f}l_{f})\}).
\end{equation*}

\item  The computation \ of any $N_{n}(f,p)$, $n\geqq 1$, from $Z(t,f)$,
involves $O(nd_{f}l_{f})$ \ arithmetic operations on integers with binary
length \ 
\begin{equation*}
\mathit{O}(\max \{(n+l_{f})\log p,\log (d_{f}l_{f})\}).
\end{equation*}
\end{enumerate}
\end{proposition}

\begin{proof}
(1) By (\ref{For2})\ and (\ref{For4}), $c_{j}(f,p)=\frac{v_{j}}{p^{m_{j}}}$, 
$v_{j},m_{j}\in \mathbb{N}$. In addition, 
\begin{equation*}
c_{j-1}(f,p)=p^{-j+1}N_{j-1}(f,p)-p^{-j}N_{j}(f,p).
\end{equation*}
Thus $p^{n}c_{j-1}(f,p)\in \mathbb{N}$, for $\ j=1,\mathbb{\cdots },n$, and
\ $m_{j}\leq $\ $n,$ for $\ j=1,\mathbb{\cdots },n$. From (\ref{For1}), it
follows that $\ $%
\begin{equation}
N_{n}(f,p)=p^{n}-\sum\limits_{j=1}^{n}p^{n}c_{j-1}(f,p),\text{ }n\geqslant 1.
\label{For3}
\end{equation}
The above formula implies that the computation of \ $N_{n}(f,p)$, $n\geqq 1$%
, \ from \ the $c_{j-1}(f,p)$, $j=1,\mathbb{\cdots },n$, involves \ $O(n)$ \
\ arithmetic operations on integers with binary length \ $O(n\log p)$.

(2) The \ computation of $a_{j}(u)$ from $L_{u}(t)$ (i.e. from $Z(t,f)$, cf.
(\ref{For4a}))\ involves $O(1)$ arithmetic operations (cf. (\ref{For2}), (%
\ref{For5})) \ on integers of binary length $O(\max \{\log p$, $\log
(d_{f}l_{f})\})$. Indeed, since the numbers $l(u)$, $W^{\ast }(B_{u})$, $%
W(u) $, $u\in T(f,l_{f})$ are involved in this computation, we know \ by
proposition \ref{prop4.1} that their binary length is bounded by $O(\max
\{\log p$, $\log (d_{f}l_{f})\})$.

The cost of computing \ $c_{j}(f,p)$ from $L_{u}(t)$, $u\in T(f,l_{f})$
(i.e. from $Z(t,f)$) is bounded by the number of vertices of $T(f,l_{f})$ \
multiplied by an upper bound \ for the cost of computing $a_{j}(u)$ from $%
L_{u}(t)$, for any $j$, and $u$ (cf. (\ref{For4})). Therefore, \ from the
previous discussion the cost of computing $c_{j}(f,p)$ from $Z(t,f)$ is
bounded by $O(d_{f}$ $l_{f})$ \ \ arithmetic operations. These arithmetic
operations are performed on integers of binary length bounded \ by $O(\max
\{(j+l_{f})\log p,\log p,$ $\log (d_{f}l_{f})\}).$ Indeed, the binary
lengths of the numerator and the denominator of \ $a_{j}(u)+a_{j}(u^{^{%
\prime }})$, $u$, $u^{^{\prime }}\in T(f,l_{f})$ are bounded by $%
(l_{f}+1+j)\log p$ (cf. (\ref{For2})). Thus, the mentioned arithmetic
operations \ for calculating $c_{j}(f,p)$ from\ $L_{u}(t)$ are performed on
integers whose binary length is bounded by \ $O(\max \{(j+l_{f})\log p,\log
p,$ $\log (d_{f}l_{f})\})$.

(3) The third part \ follows the first and second parts by (\ref{For3}).
\end{proof}

\subsection{Proof of Theorem \ref{theoB}}

The theorem follows from proposition \ref{prop8} (3).

\begin{thebibliography}{99}
\bibitem{A-G}  Anshel, M., and Goldfeld, D., Zeta functions, one-way
functions and pseudorandom number generators, Duke Math. J., 88, 2 (1997),
371-390.

\bibitem{B-M}  Bierstone., \ E., Milman, P., Canonical desingularization in
characteristic zero by blowing up the maximum strata of a local invariant,
Invent. Math. 128 (1997), 207-302.

\bibitem{B-S}  Bodn\'{a}r, G\'{a}bor; Schicho, Josef. A computer program for
the resolution of singularities. Resolution of singularities (Obergurgl,
1997), 231--238, Progr. Math., 181, Birkh\"{a}user, Basel, 2000.

\bibitem{B-S1}  Bodn\'{a}r, G., Schicho, J., \ Automated resolution of
singularities for hypersurfaces, Journal of Symbolic Computation 30 (2000),
401-428.

\bibitem{D1}  Denef J., \ Report on Igusa's local zeta function,
S\'{e}minaire Bourbaki 1990/1991 (730-744) in Asterisque 201-203 (1991),
359-386.

\bibitem{D2}  Denef J., On the degree of Igusa's \ local zeta functions,
Amer. Math. J. 109 (1987), \ 991-1008.

\bibitem{D-H}  Denef J., Hoornaert Kathleen, \ Newton polyhedra and Igusa
local zeta function, Journal of Number Theory 89 (2001), 31-64.

\bibitem{K}  Knuth, D., The art of computer programming, 3 volumes,
Addison-Wesley, 1999.

\bibitem{G-J}  Garey, M. R., Johnson, D. S., Computers and intractability: A
guide to the theory of $\mathbf{NP}$-Completeness, 1979, \ W. H. Freedman
and Company, New York.

\bibitem{G1}  Goldman, Jay R., \ Numbers of solution of congruences:
Poincar\'{e} series for strongly nondegenerate forms, Proc. Amer. Math.
Soc., 87 (1983), 586-590.

\bibitem{G2}  Goldman, Jay R., \ Numbers of solution of congruences:
Poincar\'{e} series for algebraic curves, Adv. in Math. 62 (1986), 68-83.

\bibitem{G-L-N}  Goldreich, O., Levin, L. A., and Nisan, N., On constructing
1-1 one-way functions, preprint available at
http://www.wisdom.weizmann.ac.il/~\symbol{126}oded/cryptography.html.

\bibitem{G-K-L}  Goldreich, O., \ Krawczyk, H., \ Luby, M., \ On the
existence of pseudorandom number generators, SIAM J. on Computing, Vol. 22
(1993), 1163-1175.

\bibitem{I1}  Igusa, Jun-Ichi, An introduction to the theory of local zeta
functions, AMS /IP studies in \ advanced mathematics, v. 14, 2000.

\bibitem{I2}  Igusa, J., \ Complex powers and asymptotic expansions, I
Crelles J. Math., 268/269 (1974), 110-130; II, ibid., 278/279 (1975),
357-368.

\bibitem{I3}  Igusa, J., A stationary phase formula for $p-$adic integrals \
and its applications, in Algebraic Geometry and its Applications,
Springer-Verlag (1994), 175-194.

\bibitem{L-L-L}  Lenstra, A.K., Lenstra, H.W., Lov\'{a}sz, L., Factoring
polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534.

\bibitem{R}  Ruepel R., Analysis and design of stream ciphers,
Springer-Verlag, New York, 1986.

\bibitem{S-Z-G}  Saia, M.J., Zuniga-Galindo, W.A., Local zeta functions,
Newton polygons and non degeneracy conditions, to appear in Trans. Amer.
Math. Soc.

\bibitem{S}  P. Shor, Algorithms for quantum computation, discrete
logarithms, and factoring, in Proceedings of 35th Annual Symposium on
Foundations of Computer Science, IEEE Computer Society Press, Los alamitos,
California, 1994, 124-134.

\bibitem{Vi}  Villamayor, O., Constructiveness of Hironaka's resolution,
Ann. Scient. Ecole Norm. Sup. 4 (1989), 1-32.

\bibitem{V-K-S}  von zur Gathen, J., Karpinski, M., Shparlinski, I.,
Counting curves and their projections, in Proceedings ACM\ STOC\ 93, 805-812.

\bibitem{Wa}  Daqing Wan, Algorithmic theory of zeta functions over finite
fields,to appear in MSRI Computational Number Theory Proceedings.

\bibitem{Z-G1}  Zuniga-Galindo W. A., Igusa's local zeta functions of
semiquasihomogeneous polynomials, Trans. Amer. Math. Soc. 353, (2001),
3193-3207.

\bibitem{Z-G2}  Zuniga-Galindo W. A., Local zeta functions and Newton
polyhedra, \ to appear in Nagoya Math. J.

\bibitem{ZG3}  Zuniga-Galindo W.A., Local zeta function for non-degenerate
homogeneous mappings, preprint 2003.
\end{thebibliography}

\end{document}


tcilatex.tex
% Macros for Scientific Word 2.5 documents saved with the LaTeX filter.
%Copyright (C) 1994-96 TCI Software Research, Inc.
\typeout{TCILATEX Macros for Scientific Word 2.5 <04 SEP 96>.}

\typeout{NOTICE:  This macro file is NOT proprietary and may be 
freely copied and distributed.}


\makeatletter
%%
%% Changes
%% ** to \def\readFRAMEparams
%%    replaces h by H, if the float package is loaded
%%
\@ifundefined{@HHfloat}{\relax}{\typeout{** TCILaTeX detected 'float'-package:}	}	
%%see changes
%
%%%%%%%%%%%%%%%%%%%%%%
% macros for time
\newcount\@hour\newcount\@minute\chardef\@x10\chardef\@xv60
\def\tcitime{
\def\@time{%
  \@minute\time\@hour\@minute\divide\@hour\@xv
  \ifnum\@hour<\@x 0\fi\the\@hour:%
  \multiply\@hour\@xv\advance\@minute-\@hour
  \ifnum\@minute<\@x 0\fi\the\@minute
  }}%

%%%%%%%%%%%%%%%%%%%%%%
% macro for hyperref
\@ifundefined{hyperref}{\def\hyperref#1#2#3#4{#2\ref{#4}#3}}{}

% macro for external program call
\@ifundefined{qExtProgCall}{\def\qExtProgCall#1#2#3#4#5#6{\relax}}{}
%%%%%%%%%%%%%%%%%%%%%%
%
% macros for graphics
%
\def\FILENAME#1{#1}%
%
\def\QCTOpt[#1]#2{%
  \def\QCTOptB{#1}
  \def\QCTOptA{#2}
}
\def\QCTNOpt#1{%
  \def\QCTOptA{#1}
  \let\QCTOptB\empty
}
\def\Qct{%
  \@ifnextchar[{%
    \QCTOpt}{\QCTNOpt}
}
\def\QCBOpt[#1]#2{%
  \def\QCBOptB{#1}
  \def\QCBOptA{#2}
}
\def\QCBNOpt#1{%
  \def\QCBOptA{#1}
  \let\QCBOptB\empty
}
\def\Qcb{%
  \@ifnextchar[{%
    \QCBOpt}{\QCBNOpt}
}
\def\PrepCapArgs{%
  \ifx\QCBOptA\empty
    \ifx\QCTOptA\empty
      {}%
    \else
      \ifx\QCTOptB\empty
        {\QCTOptA}%
      \else
        [\QCTOptB]{\QCTOptA}%
      \fi
    \fi
  \else
    \ifx\QCBOptA\empty
      {}%
    \else
      \ifx\QCBOptB\empty
        {\QCBOptA}%
      \else
        [\QCBOptB]{\QCBOptA}%
      \fi
    \fi
  \fi
}
\newcount\GRAPHICSTYPE
%\GRAPHICSTYPE 0 is for TurboTeX
%\GRAPHICSTYPE 1 is for DVIWindo (PostScript)
%%%(removed)%\GRAPHICSTYPE 2 is for psfig (PostScript)
\GRAPHICSTYPE=\z@
\def\GRAPHICSPS#1{%
 \ifcase\GRAPHICSTYPE%\GRAPHICSTYPE=0
   \special{ps: #1}%
 \or%\GRAPHICSTYPE=1
   \special{language "PS", include "#1"}%
%%%\or%\GRAPHICSTYPE=2
%%%  #1%
 \fi
}%
%
\def\GRAPHICSHP#1{\special{include #1}}%
%
% \graffile{ body }                                  %#1
%          { contentswidth (scalar)  }               %#2
%          { contentsheight (scalar) }               %#3
%          { vertical shift when in-line (scalar) }  %#4
\def\graffile#1#2#3#4{%
%%% \ifnum\GRAPHICSTYPE=\tw@
%%%  %Following if using psfig
%%%  \@ifundefined{psfig}{\input psfig.tex}{}%
%%%  \psfig{file=#1, height=#3, width=#2}%
%%% \else
  %Following for all others
  % JCS - added BOXTHEFRAME, see below
    \leavevmode
    \raise -#4 \BOXTHEFRAME{%
        \hbox to #2{\raise #3\hbox to #2{\null #1\hfil}}}%
}%
%
% A box for drafts
\def\draftbox#1#2#3#4{%
 \leavevmode\raise -#4 \hbox{%
  \frame{\rlap{\protect\tiny #1}\hbox to #2%
   {\vrule height#3 width\z@ depth\z@\hfil}%
  }%
 }%
}%
%
\newcount\draft
\draft=\z@
\let\nographics=\draft
\newif\ifwasdraft
\wasdraftfalse

%  \GRAPHIC{ body }                                  %#1
%          { draft name }                            %#2
%          { contentswidth (scalar)  }               %#3
%          { contentsheight (scalar) }               %#4
%          { vertical shift when in-line (scalar) }  %#5
\def\GRAPHIC#1#2#3#4#5{%
 \ifnum\draft=\@ne\draftbox{#2}{#3}{#4}{#5}%
  \else\graffile{#1}{#3}{#4}{#5}%
  \fi
 }%
%
\def\addtoLaTeXparams#1{%
    \edef\LaTeXparams{\LaTeXparams #1}}%
%
% JCS -  added a switch BoxFrame that can 
% be set by including X in the frame params.
% If set a box is drawn around the frame.

\newif\ifBoxFrame \BoxFramefalse
\newif\ifOverFrame \OverFramefalse
\newif\ifUnderFrame \UnderFramefalse

\def\BOXTHEFRAME#1{%
   \hbox{%
      \ifBoxFrame
         \frame{#1}%
      \else
         {#1}%
      \fi
   }%
}


\def\doFRAMEparams#1{\BoxFramefalse\OverFramefalse\UnderFramefalse\readFRAMEparams#1\end}%
\def\readFRAMEparams#1{%
   \ifx#1\end%
  \let\next=\relax
  \else
  \ifx#1i\dispkind=\z@\fi
  \ifx#1d\dispkind=\@ne\fi
  \ifx#1f\dispkind=\tw@\fi
 	%% BEGIN CHANGES 0.12
	\ifx#1h
    \ifnum\dispkind=\tw@
			\@ifundefined{@HHfloat}{
			  \addtoLaTeXparams{h}
		 	 }{
         \def\LaTeXparams{H}
         \typeout{tcilatex: attribute align pos of FRAME  set to H}
         \typeout{\space \space \space \space all other placement options (tbp) are ignored }
   		 }
	  \else
			\addtoLaTeXparams{h}
    \fi
	\fi
  \if\LaTeXparams H
  	 \ifx#1t\fi	 %% ignore	all other placement
  	 \ifx#1b\fi	 %% options (tbp) 
     \ifx#1p\fi
  \else
      \ifx#1t\addtoLaTeXparams{t}\fi
      \ifx#1b\addtoLaTeXparams{b}\fi
      \ifx#1p\addtoLaTeXparams{p}\fi
  \fi
	%\typeout{LaTeXparms: \LaTeXparams}
%%END CHANGES 0.12

  \ifx#1X\BoxFrametrue\fi
  \ifx#1O\OverFrametrue\fi
  \ifx#1U\UnderFrametrue\fi
  \ifx#1w
    \ifnum\draft=1\wasdrafttrue\else\wasdraftfalse\fi
    \draft=\@ne
  \fi
  \let\next=\readFRAMEparams
  \fi
 \next
 }%
%
%Macro for In-line graphics object
%   \IFRAME{ contentswidth (scalar)  }               %#1
%          { contentsheight (scalar) }               %#2
%          { vertical shift when in-line (scalar) }  %#3
%          { draft name }                            %#4
%          { body }                                  %#5
%          { caption}                                %#6


\def\IFRAME#1#2#3#4#5#6{%
      \bgroup
      \let\QCTOptA\empty
      \let\QCTOptB\empty
      \let\QCBOptA\empty
      \let\QCBOptB\empty
      #6%
      \parindent=0pt%
      \leftskip=0pt
      \rightskip=0pt
      \setbox0 = \hbox{\QCBOptA}%
      \@tempdima = #1\relax
      \ifOverFrame
          % Do this later
          \typeout{This is not implemented yet}%
          \show\HELP
      \else
         \ifdim\wd0>\@tempdima
            \advance\@tempdima by \@tempdima
            \ifdim\wd0 >\@tempdima
               \textwidth=\@tempdima
               \setbox1 =\vbox{%
                  \noindent\hbox to \@tempdima{\hfill\GRAPHIC{#5}{#4}{#1}{#2}{#3}\hfill}\\%
                  \noindent\hbox to \@tempdima{\parbox[b]{\@tempdima}{\QCBOptA}}%
               }%
               \wd1=\@tempdima
            \else
               \textwidth=\wd0
               \setbox1 =\vbox{%
                 \noindent\hbox to \wd0{\hfill\GRAPHIC{#5}{#4}{#1}{#2}{#3}\hfill}\\%
                 \noindent\hbox{\QCBOptA}%
               }%
               \wd1=\wd0
            \fi
         \else
            %\show\BBB
            \ifdim\wd0>0pt
              \hsize=\@tempdima
              \setbox1 =\vbox{%
                \unskip\GRAPHIC{#5}{#4}{#1}{#2}{0pt}%
                \break
                \unskip\hbox to \@tempdima{\hfill \QCBOptA\hfill}%
              }%
              \wd1=\@tempdima
           \else
              \hsize=\@tempdima
              \setbox1 =\vbox{%
                \unskip\GRAPHIC{#5}{#4}{#1}{#2}{0pt}%
              }%
              \wd1=\@tempdima
           \fi
         \fi
         \@tempdimb=\ht1
         \advance\@tempdimb by \dp1
         \advance\@tempdimb by -#2%
         \advance\@tempdimb by #3%
         \leavevmode
         \raise -\@tempdimb \hbox{\box1}%
      \fi
      \egroup%
}%
%
%Macro for Display graphics object
%   \DFRAME{ contentswidth (scalar)  }               %#1
%          { contentsheight (scalar) }               %#2
%          { draft label }                           %#3
%          { name }                                  %#4
%          { caption}                                %#5
\def\DFRAME#1#2#3#4#5{%
 \begin{center}
     \let\QCTOptA\empty
     \let\QCTOptB\empty
     \let\QCBOptA\empty
     \let\QCBOptB\empty
     \ifOverFrame 
        #5\QCTOptA\par
     \fi
     \GRAPHIC{#4}{#3}{#1}{#2}{\z@}
     \ifUnderFrame 
        \nobreak\par #5\QCBOptA
     \fi
 \end{center}%
 }%
%
%Macro for Floating graphic object
%   \FFRAME{ framedata f|i tbph x F|T }              %#1
%          { contentswidth (scalar)  }               %#2
%          { contentsheight (scalar) }               %#3
%          { caption }                               %#4
%          { label }                                 %#5
%          { draft name }                            %#6
%          { body }                                  %#7
\def\FFRAME#1#2#3#4#5#6#7{%
 \begin{figure}[#1]%
  \let\QCTOptA\empty
  \let\QCTOptB\empty
  \let\QCBOptA\empty
  \let\QCBOptB\empty
  \ifOverFrame
    #4
    \ifx\QCTOptA\empty
    \else
      \ifx\QCTOptB\empty
        \caption{\QCTOptA}%
      \else
        \caption[\QCTOptB]{\QCTOptA}%
      \fi
    \fi
    \ifUnderFrame\else
      \label{#5}%
    \fi
  \else
    \UnderFrametrue%
  \fi
  \begin{center}\GRAPHIC{#7}{#6}{#2}{#3}{\z@}\end{center}%
  \ifUnderFrame
    #4
    \ifx\QCBOptA\empty
      \caption{}%
    \else
      \ifx\QCBOptB\empty
        \caption{\QCBOptA}%
      \else
        \caption[\QCBOptB]{\QCBOptA}%
      \fi
    \fi
    \label{#5}%
  \fi
  \end{figure}%
 }%
%
%
%    \FRAME{ framedata f|i tbph x F|T }              %#1
%          { contentswidth (scalar)  }               %#2
%          { contentsheight (scalar) }               %#3
%          { vertical shift when in-line (scalar) }  %#4
%          { caption }                               %#5
%          { label }                                 %#6
%          { name }                                  %#7
%          { body }                                  %#8
%
%    framedata is a string which can contain the following
%    characters: idftbphxFT
%    Their meaning is as follows:
%             i, d or f : in-line, display, or floating
%             t,b,p,h   : LaTeX floating placement options
%             x         : fit contents box to contents
%             F or T    : Figure or Table. 
%                         Later this can expand
%                         to a more general float class.
%
%
\newcount\dispkind%

\def\makeactives{
  \catcode`\"=\active
  \catcode`\;=\active
  \catcode`\:=\active
  \catcode`\'=\active
  \catcode`\~=\active
}
\bgroup
   \makeactives
   \gdef\activesoff{%
      \def"{\string"}
      \def;{\string;}
      \def:{\string:}
      \def'{\string'}
      \def~{\string~}
      %\bbl@deactivate{"}%
      %\bbl@deactivate{;}%
      %\bbl@deactivate{:}%
      %\bbl@deactivate{'}%
    }
\egroup

\def\FRAME#1#2#3#4#5#6#7#8{%
 \bgroup
 \@ifundefined{bbl@deactivate}{}{\activesoff}
 \ifnum\draft=\@ne
   \wasdrafttrue
 \else
   \wasdraftfalse%
 \fi
 \def\LaTeXparams{}%
 \dispkind=\z@
 \def\LaTeXparams{}%
 \doFRAMEparams{#1}%
 \ifnum\dispkind=\z@\IFRAME{#2}{#3}{#4}{#7}{#8}{#5}\else
  \ifnum\dispkind=\@ne\DFRAME{#2}{#3}{#7}{#8}{#5}\else
   \ifnum\dispkind=\tw@
    \edef\@tempa{\noexpand\FFRAME{\LaTeXparams}}%
    \@tempa{#2}{#3}{#5}{#6}{#7}{#8}%
    \fi
   \fi
  \fi
  \ifwasdraft\draft=1\else\draft=0\fi{}%
  \egroup
 }%
%
% This macro added to let SW gobble a parameter that
% should not be passed on and expanded. 

\def\TEXUX#1{"texux"}

%
% Macros for text attributes:
%
\def\BF#1{{\bf {#1}}}%
\def\NEG#1{\leavevmode\hbox{\rlap{\thinspace/}{$#1$}}}%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
% macros for user - defined functions
\def\func#1{\mathop{\rm #1}}%
\def\limfunc#1{\mathop{\rm #1}}%

%
% miscellaneous 
%\long\def\QQQ#1#2{}%
\long\def\QQQ#1#2{%
     \long\expandafter\def\csname#1\endcsname{#2}}%
%\def\QTP#1{}% JCS - this was changed becuase style editor will define QTP
\@ifundefined{QTP}{\def\QTP#1{}}{}
\@ifundefined{QEXCLUDE}{\def\QEXCLUDE#1{}}{}
%\@ifundefined{Qcb}{\def\Qcb#1{#1}}{}
%\@ifundefined{Qct}{\def\Qct#1{#1}}{}
\@ifundefined{Qlb}{\def\Qlb#1{#1}}{}
\@ifundefined{Qlt}{\def\Qlt#1{#1}}{}
\def\QWE{}%
\long\def\QQA#1#2{}%
%\def\QTR#1#2{{\em #2}}% Always \em!!!
%\def\QTR#1#2{\mbox{\begin{#1}#2\end{#1}}}%cb%%%
\def\QTR#1#2{{\csname#1\endcsname #2}}%(gp) Is this the best?
\long\def\TeXButton#1#2{#2}%
\long\def\QSubDoc#1#2{#2}%
\def\EXPAND#1[#2]#3{}%
\def\NOEXPAND#1[#2]#3{}%
\def\PROTECTED{}%
\def\LaTeXparent#1{}%
\def\ChildStyles#1{}%
\def\ChildDefaults#1{}%
\def\QTagDef#1#2#3{}%
%
% Macros for style editor docs
\@ifundefined{StyleEditBeginDoc}{\def\StyleEditBeginDoc{\relax}}{}
%
% Macros for footnotes
\def\QQfnmark#1{\footnotemark}
\def\QQfntext#1#2{\addtocounter{footnote}{#1}\footnotetext{#2}}
%
% Macros for indexing.
\def\MAKEINDEX{\makeatletter\input gnuindex.sty\makeatother\makeindex}%	
\@ifundefined{INDEX}{\def\INDEX#1#2{}{}}{}%
\@ifundefined{SUBINDEX}{\def\SUBINDEX#1#2#3{}{}{}}{}%
\@ifundefined{initial}%  
   {\def\initial#1{\bigbreak{\raggedright\large\bf #1}\kern 2\p@\penalty3000}}%
   {}%
\@ifundefined{entry}{\def\entry#1#2{\item {#1}, #2}}{}%
\@ifundefined{primary}{\def\primary#1{\item {#1}}}{}%
\@ifundefined{secondary}{\def\secondary#1#2{\subitem {#1}, #2}}{}%
%
%
\@ifundefined{ZZZ}{}{\MAKEINDEX\makeatletter}%
%
% Attempts to avoid problems with other styles
\@ifundefined{abstract}{%
 \def\abstract{%
  \if@twocolumn
   \section*{Abstract (Not appropriate in this style!)}%
   \else \small 
   \begin{center}{\bf Abstract\vspace{-.5em}\vspace{\z@}}\end{center}%
   \quotation 
   \fi
  }%
 }{%
 }%
\@ifundefined{endabstract}{\def\endabstract
  {\if@twocolumn\else\endquotation\fi}}{}%
\@ifundefined{maketitle}{\def\maketitle#1{}}{}%
\@ifundefined{affiliation}{\def\affiliation#1{}}{}%
\@ifundefined{proof}{\def\proof{\noindent{\bfseries Proof. }}}{}%
\@ifundefined{endproof}{\def\endproof{\mbox{\ \rule{.1in}{.1in}}}}{}%
\@ifundefined{newfield}{\def\newfield#1#2{}}{}%
\@ifundefined{chapter}{\def\chapter#1{\par(Chapter head:)#1\par }%
 \newcount\c@chapter}{}%
\@ifundefined{part}{\def\part#1{\par(Part head:)#1\par }}{}%
\@ifundefined{section}{\def\section#1{\par(Section head:)#1\par }}{}%
\@ifundefined{subsection}{\def\subsection#1%
 {\par(Subsection head:)#1\par }}{}%
\@ifundefined{subsubsection}{\def\subsubsection#1%
 {\par(Subsubsection head:)#1\par }}{}%
\@ifundefined{paragraph}{\def\paragraph#1%
 {\par(Subsubsubsection head:)#1\par }}{}%
\@ifundefined{subparagraph}{\def\subparagraph#1%
 {\par(Subsubsubsubsection head:)#1\par }}{}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These symbols are not recognized by LaTeX
\@ifundefined{therefore}{\def\therefore{}}{}%
\@ifundefined{backepsilon}{\def\backepsilon{}}{}%
\@ifundefined{yen}{\def\yen{\hbox{\rm\rlap=Y}}}{}%
\@ifundefined{registered}{%
   \def\registered{\relax\ifmmode{}\r@gistered
                    \else$\m@th\r@gistered$\fi}%
 \def\r@gistered{^{\ooalign
  {\hfil\raise.07ex\hbox{$\scriptstyle\rm\text{R}$}\hfil\crcr
  \mathhexbox20D}}}}{}%
\@ifundefined{Eth}{\def\Eth{}}{}%
\@ifundefined{eth}{\def\eth{}}{}%
\@ifundefined{Thorn}{\def\Thorn{}}{}%
\@ifundefined{thorn}{\def\thorn{}}{}%
% A macro to allow any symbol that requires math to appear in text
\def\TEXTsymbol#1{\mbox{$#1$}}%
\@ifundefined{degree}{\def\degree{{}^{\circ}}}{}%
%
% macros for T3TeX files
\newdimen\theight
\def\Column{%
 \vadjust{\setbox\z@=\hbox{\scriptsize\quad\quad tcol}%
  \theight=\ht\z@\advance\theight by \dp\z@\advance\theight by \lineskip
  \kern -\theight \vbox to \theight{%
   \rightline{\rlap{\box\z@}}%
   \vss
   }%
  }%
 }%
%
\def\qed{%
 \ifhmode\unskip\nobreak\fi\ifmmode\ifinner\else\hskip5\p@\fi\fi
 \hbox{\hskip5\p@\vrule width4\p@ height6\p@ depth1.5\p@\hskip\p@}%
 }%
%
\def\cents{\hbox{\rm\rlap/c}}%
\def\miss{\hbox{\vrule height2\p@ width 2\p@ depth\z@}}%
%\def\miss{\hbox{.}}%        %another possibility 
%
\def\vvert{\Vert}%           %always translated to \left| or \right|
%
\def\tcol#1{{\baselineskip=6\p@ \vcenter{#1}} \Column}  %
%
\def\dB{\hbox{{}}}%                 %dummy entry in column 
\def\mB#1{\hbox{$#1$}}%             %column entry
\def\nB#1{\hbox{#1}}%               %column entry (not math)
%
%\newcount\notenumber
%\def\clearnotenumber{\notenumber=0}
%\def\note{\global\advance\notenumber by 1
% \footnote{$^{\the\notenumber}$}}
%\def\note{\global\advance\notenumber by 1
\def\note{$^{\dag}}%
%
%

\def\newfmtname{LaTeX2e}
\def\chkcompat{%
   \if@compatibility
   \else
     \usepackage{latexsym}
   \fi
}

\ifx\fmtname\newfmtname
  \DeclareOldFontCommand{\rm}{\normalfont\rmfamily}{\mathrm}
  \DeclareOldFontCommand{\sf}{\normalfont\sffamily}{\mathsf}
  \DeclareOldFontCommand{\tt}{\normalfont\ttfamily}{\mathtt}
  \DeclareOldFontCommand{\bf}{\normalfont\bfseries}{\mathbf}
  \DeclareOldFontCommand{\it}{\normalfont\itshape}{\mathit}
  \DeclareOldFontCommand{\sl}{\normalfont\slshape}{\@nomath\sl}
  \DeclareOldFontCommand{\sc}{\normalfont\scshape}{\@nomath\sc}
  \chkcompat
\fi

%
% Greek bold macros
% Redefine all of the math symbols 
% which might be bolded	 - there are 
% probably others to add to this list

\def\alpha{{\Greekmath 010B}}%
\def\beta{{\Greekmath 010C}}%
\def\gamma{{\Greekmath 010D}}%
\def\delta{{\Greekmath 010E}}%
\def\epsilon{{\Greekmath 010F}}%
\def\zeta{{\Greekmath 0110}}%
\def\eta{{\Greekmath 0111}}%
\def\theta{{\Greekmath 0112}}%
\def\iota{{\Greekmath 0113}}%
\def\kappa{{\Greekmath 0114}}%
\def\lambda{{\Greekmath 0115}}%
\def\mu{{\Greekmath 0116}}%
\def\nu{{\Greekmath 0117}}%
\def\xi{{\Greekmath 0118}}%
\def\pi{{\Greekmath 0119}}%
\def\rho{{\Greekmath 011A}}%
\def\sigma{{\Greekmath 011B}}%
\def\tau{{\Greekmath 011C}}%
\def\upsilon{{\Greekmath 011D}}%
\def\phi{{\Greekmath 011E}}%
\def\chi{{\Greekmath 011F}}%
\def\psi{{\Greekmath 0120}}%
\def\omega{{\Greekmath 0121}}%
\def\varepsilon{{\Greekmath 0122}}%
\def\vartheta{{\Greekmath 0123}}%
\def\varpi{{\Greekmath 0124}}%
\def\varrho{{\Greekmath 0125}}%
\def\varsigma{{\Greekmath 0126}}%
\def\varphi{{\Greekmath 0127}}%

\def\nabla{{\Greekmath 0272}}
\def\FindBoldGroup{%
   {\setbox0=\hbox{$\mathbf{x\global\edef\theboldgroup{\the\mathgroup}}$}}%
}

\def\Greekmath#1#2#3#4{%
    \if@compatibility
        \ifnum\mathgroup=\symbold
           \mathchoice{\mbox{\boldmath$\displaystyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\textstyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\scriptstyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\scriptscriptstyle\mathchar"#1#2#3#4$}}%
        \else
           \mathchar"#1#2#3#4% 
        \fi 
    \else 
        \FindBoldGroup
        \ifnum\mathgroup=\theboldgroup % For 2e
           \mathchoice{\mbox{\boldmath$\displaystyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\textstyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\scriptstyle\mathchar"#1#2#3#4$}}%
                      {\mbox{\boldmath$\scriptscriptstyle\mathchar"#1#2#3#4$}}%
        \else
           \mathchar"#1#2#3#4% 
        \fi     	    
	  \fi}

\newif\ifGreekBold  \GreekBoldfalse
\let\SAVEPBF=\pbf
\def\pbf{\GreekBoldtrue\SAVEPBF}%
%

\@ifundefined{theorem}{\newtheorem{theorem}{Theorem}}{}
\@ifundefined{lemma}{\newtheorem{lemma}[theorem]{Lemma}}{}
\@ifundefined{corollary}{\newtheorem{corollary}[theorem]{Corollary}}{}
\@ifundefined{conjecture}{\newtheorem{conjecture}[theorem]{Conjecture}}{}
\@ifundefined{proposition}{\newtheorem{proposition}[theorem]{Proposition}}{}
\@ifundefined{axiom}{\newtheorem{axiom}{Axiom}}{}
\@ifundefined{remark}{\newtheorem{remark}{Remark}}{}
\@ifundefined{example}{\newtheorem{example}{Example}}{}
\@ifundefined{exercise}{\newtheorem{exercise}{Exercise}}{}
\@ifundefined{definition}{\newtheorem{definition}{Definition}}{}


\@ifundefined{mathletters}{%
  %\def\theequation{\arabic{equation}}
  \newcounter{equationnumber}  
  \def\mathletters{%
     \addtocounter{equation}{1}
     \edef\@currentlabel{\theequation}%
     \setcounter{equationnumber}{\c@equation}
     \setcounter{equation}{0}%
     \edef\theequation{\@currentlabel\noexpand\alph{equation}}%
  }
  \def\endmathletters{%
     \setcounter{equation}{\value{equationnumber}}%
  }
}{}

%Logos
\@ifundefined{BibTeX}{%
    \def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
                 T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}}{}%
\@ifundefined{AmS}%
    {\def\AmS{{\protect\usefont{OMS}{cmsy}{m}{n}%
                A\kern-.1667em\lower.5ex\hbox{M}\kern-.125emS}}}{}%
\@ifundefined{AmSTeX}{\def\AmSTeX{\protect\AmS-\protect\TeX\@}}{}%
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOTE: The rest of this file is read only if amstex has not been
% loaded.  This section is used to define amstex constructs in the
% event they have not been defined.
%
%
\ifx\ds@amstex\relax
   \message{amstex already loaded}\makeatother\endinput% 2.09 compatability
\else
   \@ifpackageloaded{amstex}%
      {\message{amstex already loaded}\makeatother\endinput}
      {}
   \@ifpackageloaded{amsgen}%
      {\message{amsgen already loaded}\makeatother\endinput}
      {}
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%
%
%  Macros to define some AMS LaTeX constructs when 
%  AMS LaTeX has not been loaded
% 
% These macros are copied from the AMS-TeX package for doing
% multiple integrals.
%
\def\DN@{\def\next@}%
\def\eat@#1{}%
\let\DOTSI\relax
\def\RIfM@{\relax\ifmmode}%
\def\FN@{\futurelet\next}%
\newcount\intno@
\def\iint{\DOTSI\intno@\tw@\FN@\ints@}%
\def\iiint{\DOTSI\intno@\thr@@\FN@\ints@}%
\def\iiiint{\DOTSI\intno@4 \FN@\ints@}%
\def\idotsint{\DOTSI\intno@\z@\FN@\ints@}%
\def\ints@{\findlimits@\ints@@}%
\newif\iflimtoken@
\newif\iflimits@
\def\findlimits@{\limtoken@true\ifx\next\limits\limits@true
 \else\ifx\next\nolimits\limits@false\else
 \limtoken@false\ifx\ilimits@\nolimits\limits@false\else
 \ifinner\limits@false\else\limits@true\fi\fi\fi\fi}%
\def\multint@{\int\ifnum\intno@=\z@\intdots@                          %1
 \else\intkern@\fi                                                    %2
 \ifnum\intno@>\tw@\int\intkern@\fi                                   %3
 \ifnum\intno@>\thr@@\int\intkern@\fi                                 %4
 \int}%                                                               %5
\def\multintlimits@{\intop\ifnum\intno@=\z@\intdots@\else\intkern@\fi
 \ifnum\intno@>\tw@\intop\intkern@\fi
 \ifnum\intno@>\thr@@\intop\intkern@\fi\intop}%
\def\intic@{%
    \mathchoice{\hskip.5em}{\hskip.4em}{\hskip.4em}{\hskip.4em}}%
\def\negintic@{\mathchoice
 {\hskip-.5em}{\hskip-.4em}{\hskip-.4em}{\hskip-.4em}}%
\def\ints@@{\iflimtoken@                                              %1
 \def\ints@@@{\iflimits@\negintic@
   \mathop{\intic@\multintlimits@}\limits                             %2
  \else\multint@\nolimits\fi                                          %3
  \eat@}%                                                             %4
 \else                                                                %5
 \def\ints@@@{\iflimits@\negintic@
  \mathop{\intic@\multintlimits@}\limits\else
  \multint@\nolimits\fi}\fi\ints@@@}%
\def\intkern@{\mathchoice{\!\!\!}{\!\!}{\!\!}{\!\!}}%
\def\plaincdots@{\mathinner{\cdotp\cdotp\cdotp}}%
\def\intdots@{\mathchoice{\plaincdots@}%
 {{\cdotp}\mkern1.5mu{\cdotp}\mkern1.5mu{\cdotp}}%
 {{\cdotp}\mkern1mu{\cdotp}\mkern1mu{\cdotp}}%
 {{\cdotp}\mkern1mu{\cdotp}\mkern1mu{\cdotp}}}%
%
%
%  These macros are for doing the AMS \text{} construct
%
\def\RIfM@{\relax\protect\ifmmode}
\def\text{\RIfM@\expandafter\text@\else\expandafter\mbox\fi}
\let\nfss@text\text
\def\text@#1{\mathchoice
   {\textdef@\displaystyle\f@size{#1}}%
   {\textdef@\textstyle\tf@size{\firstchoice@false #1}}%
   {\textdef@\textstyle\sf@size{\firstchoice@false #1}}%
   {\textdef@\textstyle \ssf@size{\firstchoice@false #1}}%
   \glb@settings}

\def\textdef@#1#2#3{\hbox{{%
                    \everymath{#1}%
                    \let\f@size#2\selectfont
                    #3}}}
\newif\iffirstchoice@
\firstchoice@true
%
%    Old Scheme for \text
%
%\def\rmfam{\z@}%
%\newif\iffirstchoice@
%\firstchoice@true
%\def\textfonti{\the\textfont\@ne}%
%\def\textfontii{\the\textfont\tw@}%
%\def\text{\RIfM@\expandafter\text@\else\expandafter\text@@\fi}%
%\def\text@@#1{\leavevmode\hbox{#1}}%
%\def\text@#1{\mathchoice
% {\hbox{\everymath{\displaystyle}\def\textfonti{\the\textfont\@ne}%
%  \def\textfontii{\the\textfont\tw@}\textdef@@ T#1}}%
% {\hbox{\firstchoice@false
%  \everymath{\textstyle}\def\textfonti{\the\textfont\@ne}%
%  \def\textfontii{\the\textfont\tw@}\textdef@@ T#1}}%
% {\hbox{\firstchoice@false
%  \everymath{\scriptstyle}\def\textfonti{\the\scriptfont\@ne}%
%  \def\textfontii{\the\scriptfont\tw@}\textdef@@ S\rm#1}}%
% {\hbox{\firstchoice@false
%  \everymath{\scriptscriptstyle}\def\textfonti
%  {\the\scriptscriptfont\@ne}%
%  \def\textfontii{\the\scriptscriptfont\tw@}\textdef@@ s\rm#1}}}%
%\def\textdef@@#1{\textdef@#1\rm\textdef@#1\bf\textdef@#1\sl
%    \textdef@#1\it}%
%\def\DN@{\def\next@}%
%\def\eat@#1{}%
%\def\textdef@#1#2{%
% \DN@{\csname\expandafter\eat@\string#2fam\endcsname}%
% \if S#1\edef#2{\the\scriptfont\next@\relax}%
% \else\if s#1\edef#2{\the\scriptscriptfont\next@\relax}%
% \else\edef#2{\the\textfont\next@\relax}\fi\fi}%
%
%
%These are the AMS constructs for multiline limits.
%
\def\Let@{\relax\iffalse{\fi\let\\=\cr\iffalse}\fi}%
\def\vspace@{\def\vspace##1{\crcr\noalign{\vskip##1\relax}}}%
\def\multilimits@{\bgroup\vspace@\Let@
 \baselineskip\fontdimen10 \scriptfont\tw@
 \advance\baselineskip\fontdimen12 \scriptfont\tw@
 \lineskip\thr@@\fontdimen8 \scriptfont\thr@@
 \lineskiplimit\lineskip
 \vbox\bgroup\ialign\bgroup\hfil$\m@th\scriptstyle{##}$\hfil\crcr}%
\def\Sb{_\multilimits@}%
\def\endSb{\crcr\egroup\egroup\egroup}%
\def\Sp{^\multilimits@}%
\let\endSp\endSb
%
%
%These are AMS constructs for horizontal arrows
%
\newdimen\ex@
\ex@.2326ex
\def\rightarrowfill@#1{$#1\m@th\mathord-\mkern-6mu\cleaders
 \hbox{$#1\mkern-2mu\mathord-\mkern-2mu$}\hfill
 \mkern-6mu\mathord\rightarrow$}%
\def\leftarrowfill@#1{$#1\m@th\mathord\leftarrow\mkern-6mu\cleaders
 \hbox{$#1\mkern-2mu\mathord-\mkern-2mu$}\hfill\mkern-6mu\mathord-$}%
\def\leftrightarrowfill@#1{$#1\m@th\mathord\leftarrow
\mkern-6mu\cleaders
 \hbox{$#1\mkern-2mu\mathord-\mkern-2mu$}\hfill
 \mkern-6mu\mathord\rightarrow$}%
\def\overrightarrow{\mathpalette\overrightarrow@}%
\def\overrightarrow@#1#2{\vbox{\ialign{##\crcr\rightarrowfill@#1\crcr
 \noalign{\kern-\ex@\nointerlineskip}$\m@th\hfil#1#2\hfil$\crcr}}}%
\let\overarrow\overrightarrow
\def\overleftarrow{\mathpalette\overleftarrow@}%
\def\overleftarrow@#1#2{\vbox{\ialign{##\crcr\leftarrowfill@#1\crcr
 \noalign{\kern-\ex@\nointerlineskip}$\m@th\hfil#1#2\hfil$\crcr}}}%
\def\overleftrightarrow{\mathpalette\overleftrightarrow@}%
\def\overleftrightarrow@#1#2{\vbox{\ialign{##\crcr
   \leftrightarrowfill@#1\crcr
 \noalign{\kern-\ex@\nointerlineskip}$\m@th\hfil#1#2\hfil$\crcr}}}%
\def\underrightarrow{\mathpalette\underrightarrow@}%
\def\underrightarrow@#1#2{\vtop{\ialign{##\crcr$\m@th\hfil#1#2\hfil
  $\crcr\noalign{\nointerlineskip}\rightarrowfill@#1\crcr}}}%
\let\underarrow\underrightarrow
\def\underleftarrow{\mathpalette\underleftarrow@}%
\def\underleftarrow@#1#2{\vtop{\ialign{##\crcr$\m@th\hfil#1#2\hfil
  $\crcr\noalign{\nointerlineskip}\leftarrowfill@#1\crcr}}}%
\def\underleftrightarrow{\mathpalette\underleftrightarrow@}%
\def\underleftrightarrow@#1#2{\vtop{\ialign{##\crcr$\m@th
  \hfil#1#2\hfil$\crcr
 \noalign{\nointerlineskip}\leftrightarrowfill@#1\crcr}}}%
%%%%%%%%%%%%%%%%%%%%%

% 94.0815 by Jon:

\def\qopnamewl@#1{\mathop{\operator@font#1}\nlimits@}
\let\nlimits@\displaylimits
\def\setboxz@h{\setbox\z@\hbox}


\def\varlim@#1#2{\mathop{\vtop{\ialign{##\crcr
 \hfil$#1\m@th\operator@font lim$\hfil\crcr
 \noalign{\nointerlineskip}#2#1\crcr
 \noalign{\nointerlineskip\kern-\ex@}\crcr}}}}

 \def\rightarrowfill@#1{\m@th\setboxz@h{$#1-$}\ht\z@\z@
  $#1\copy\z@\mkern-6mu\cleaders
  \hbox{$#1\mkern-2mu\box\z@\mkern-2mu$}\hfill
  \mkern-6mu\mathord\rightarrow$}
\def\leftarrowfill@#1{\m@th\setboxz@h{$#1-$}\ht\z@\z@
  $#1\mathord\leftarrow\mkern-6mu\cleaders
  \hbox{$#1\mkern-2mu\copy\z@\mkern-2mu$}\hfill
  \mkern-6mu\box\z@$}


\def\projlim{\qopnamewl@{proj\,lim}}
\def\injlim{\qopnamewl@{inj\,lim}}
\def\varinjlim{\mathpalette\varlim@\rightarrowfill@}
\def\varprojlim{\mathpalette\varlim@\leftarrowfill@}
\def\varliminf{\mathpalette\varliminf@{}}
\def\varliminf@#1{\mathop{\underline{\vrule\@depth.2\ex@\@width\z@
   \hbox{$#1\m@th\operator@font lim$}}}}
\def\varlimsup{\mathpalette\varlimsup@{}}
\def\varlimsup@#1{\mathop{\overline
  {\hbox{$#1\m@th\operator@font lim$}}}}

%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\def\tfrac#1#2{{\textstyle {#1 \over #2}}}%
\def\dfrac#1#2{{\displaystyle {#1 \over #2}}}%
\def\binom#1#2{{#1 \choose #2}}%
\def\tbinom#1#2{{\textstyle {#1 \choose #2}}}%
\def\dbinom#1#2{{\displaystyle {#1 \choose #2}}}%
\def\QATOP#1#2{{#1 \atop #2}}%
\def\QTATOP#1#2{{\textstyle {#1 \atop #2}}}%
\def\QDATOP#1#2{{\displaystyle {#1 \atop #2}}}%
\def\QABOVE#1#2#3{{#2 \above#1 #3}}%
\def\QTABOVE#1#2#3{{\textstyle {#2 \above#1 #3}}}%
\def\QDABOVE#1#2#3{{\displaystyle {#2 \above#1 #3}}}%
\def\QOVERD#1#2#3#4{{#3 \overwithdelims#1#2 #4}}%
\def\QTOVERD#1#2#3#4{{\textstyle {#3 \overwithdelims#1#2 #4}}}%
\def\QDOVERD#1#2#3#4{{\displaystyle {#3 \overwithdelims#1#2 #4}}}%
\def\QATOPD#1#2#3#4{{#3 \atopwithdelims#1#2 #4}}%
\def\QTATOPD#1#2#3#4{{\textstyle {#3 \atopwithdelims#1#2 #4}}}%
\def\QDATOPD#1#2#3#4{{\displaystyle {#3 \atopwithdelims#1#2 #4}}}%
\def\QABOVED#1#2#3#4#5{{#4 \abovewithdelims#1#2#3 #5}}%
\def\QTABOVED#1#2#3#4#5{{\textstyle 
   {#4 \abovewithdelims#1#2#3 #5}}}%
\def\QDABOVED#1#2#3#4#5{{\displaystyle 
   {#4 \abovewithdelims#1#2#3 #5}}}%
%
% Macros for text size operators:

%JCS - added braces and \mathop around \displaystyle\int, etc.
%
\def\tint{\mathop{\textstyle \int}}%
\def\tiint{\mathop{\textstyle \iint }}%
\def\tiiint{\mathop{\textstyle \iiint }}%
\def\tiiiint{\mathop{\textstyle \iiiint }}%
\def\tidotsint{\mathop{\textstyle \idotsint }}%
\def\toint{\mathop{\textstyle \oint}}%
\def\tsum{\mathop{\textstyle \sum }}%
\def\tprod{\mathop{\textstyle \prod }}%
\def\tbigcap{\mathop{\textstyle \bigcap }}%
\def\tbigwedge{\mathop{\textstyle \bigwedge }}%
\def\tbigoplus{\mathop{\textstyle \bigoplus }}%
\def\tbigodot{\mathop{\textstyle \bigodot }}%
\def\tbigsqcup{\mathop{\textstyle \bigsqcup }}%
\def\tcoprod{\mathop{\textstyle \coprod }}%
\def\tbigcup{\mathop{\textstyle \bigcup }}%
\def\tbigvee{\mathop{\textstyle \bigvee }}%
\def\tbigotimes{\mathop{\textstyle \bigotimes }}%
\def\tbiguplus{\mathop{\textstyle \biguplus }}%
%
%
%Macros for display size operators:
%

\def\dint{\mathop{\displaystyle \int}}%
\def\diint{\mathop{\displaystyle \iint }}%
\def\diiint{\mathop{\displaystyle \iiint }}%
\def\diiiint{\mathop{\displaystyle \iiiint }}%
\def\didotsint{\mathop{\displaystyle \idotsint }}%
\def\doint{\mathop{\displaystyle \oint}}%
\def\dsum{\mathop{\displaystyle \sum }}%
\def\dprod{\mathop{\displaystyle \prod }}%
\def\dbigcap{\mathop{\displaystyle \bigcap }}%
\def\dbigwedge{\mathop{\displaystyle \bigwedge }}%
\def\dbigoplus{\mathop{\displaystyle \bigoplus }}%
\def\dbigodot{\mathop{\displaystyle \bigodot }}%
\def\dbigsqcup{\mathop{\displaystyle \bigsqcup }}%
\def\dcoprod{\mathop{\displaystyle \coprod }}%
\def\dbigcup{\mathop{\displaystyle \bigcup }}%
\def\dbigvee{\mathop{\displaystyle \bigvee }}%
\def\dbigotimes{\mathop{\displaystyle \bigotimes }}%
\def\dbiguplus{\mathop{\displaystyle \biguplus }}%
%
%Companion to stackrel
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}%
%
%
% These are AMS environments that will be defined to
% be verbatims if amstex has not actually been 
% loaded
%
%
\begingroup \catcode `|=0 \catcode `[= 1
\catcode`]=2 \catcode `\{=12 \catcode `\}=12
\catcode`\\=12 
|gdef|@alignverbatim#1\end{align}[#1|end[align]]
|gdef|@salignverbatim#1\end{align*}[#1|end[align*]]

|gdef|@alignatverbatim#1\end{alignat}[#1|end[alignat]]
|gdef|@salignatverbatim#1\end{alignat*}[#1|end[alignat*]]

|gdef|@xalignatverbatim#1\end{xalignat}[#1|end[xalignat]]
|gdef|@sxalignatverbatim#1\end{xalignat*}[#1|end[xalignat*]]

|gdef|@gatherverbatim#1\end{gather}[#1|end[gather]]
|gdef|@sgatherverbatim#1\end{gather*}[#1|end[gather*]]

|gdef|@gatherverbatim#1\end{gather}[#1|end[gather]]
|gdef|@sgatherverbatim#1\end{gather*}[#1|end[gather*]]


|gdef|@multilineverbatim#1\end{multiline}[#1|end[multiline]]
|gdef|@smultilineverbatim#1\end{multiline*}[#1|end[multiline*]]

|gdef|@arraxverbatim#1\end{arrax}[#1|end[arrax]]
|gdef|@sarraxverbatim#1\end{arrax*}[#1|end[arrax*]]

|gdef|@tabulaxverbatim#1\end{tabulax}[#1|end[tabulax]]
|gdef|@stabulaxverbatim#1\end{tabulax*}[#1|end[tabulax*]]


|endgroup
  

  
\def\align{\@verbatim \frenchspacing\@vobeyspaces \@alignverbatim
You are using the "align" environment in a style in which it is not defined.}
\let\endalign=\endtrivlist
 
\@namedef{align*}{\@verbatim\@salignverbatim
You are using the "align*" environment in a style in which it is not defined.}
\expandafter\let\csname endalign*\endcsname =\endtrivlist




\def\alignat{\@verbatim \frenchspacing\@vobeyspaces \@alignatverbatim
You are using the "alignat" environment in a style in which it is not defined.}
\let\endalignat=\endtrivlist
 
\@namedef{alignat*}{\@verbatim\@salignatverbatim
You are using the "alignat*" environment in a style in which it is not defined.}
\expandafter\let\csname endalignat*\endcsname =\endtrivlist




\def\xalignat{\@verbatim \frenchspacing\@vobeyspaces \@xalignatverbatim
You are using the "xalignat" environment in a style in which it is not defined.}
\let\endxalignat=\endtrivlist
 
\@namedef{xalignat*}{\@verbatim\@sxalignatverbatim
You are using the "xalignat*" environment in a style in which it is not defined.}
\expandafter\let\csname endxalignat*\endcsname =\endtrivlist




\def\gather{\@verbatim \frenchspacing\@vobeyspaces \@gatherverbatim
You are using the "gather" environment in a style in which it is not defined.}
\let\endgather=\endtrivlist
 
\@namedef{gather*}{\@verbatim\@sgatherverbatim
You are using the "gather*" environment in a style in which it is not defined.}
\expandafter\let\csname endgather*\endcsname =\endtrivlist


\def\multiline{\@verbatim \frenchspacing\@vobeyspaces \@multilineverbatim
You are using the "multiline" environment in a style in which it is not defined.}
\let\endmultiline=\endtrivlist
 
\@namedef{multiline*}{\@verbatim\@smultilineverbatim
You are using the "multiline*" environment in a style in which it is not defined.}
\expandafter\let\csname endmultiline*\endcsname =\endtrivlist


\def\arrax{\@verbatim \frenchspacing\@vobeyspaces \@arraxverbatim
You are using a type of "array" construct that is only allowed in AmS-LaTeX.}
\let\endarrax=\endtrivlist

\def\tabulax{\@verbatim \frenchspacing\@vobeyspaces \@tabulaxverbatim
You are using a type of "tabular" construct that is only allowed in AmS-LaTeX.}
\let\endtabulax=\endtrivlist

 
\@namedef{arrax*}{\@verbatim\@sarraxverbatim
You are using a type of "array*" construct that is only allowed in AmS-LaTeX.}
\expandafter\let\csname endarrax*\endcsname =\endtrivlist

\@namedef{tabulax*}{\@verbatim\@stabulaxverbatim
You are using a type of "tabular*" construct that is only allowed in AmS-LaTeX.}
\expandafter\let\csname endtabulax*\endcsname =\endtrivlist

% macro to simulate ams tag construct


% This macro is a fix to eqnarray
\def\@@eqncr{\let\@tempa\relax
    \ifcase\@eqcnt \def\@tempa{& & &}\or \def\@tempa{& &}%
      \else \def\@tempa{&}\fi
     \@tempa
     \if@eqnsw
        \iftag@
           \@taggnum
        \else
           \@eqnnum\stepcounter{equation}%
        \fi
     \fi
     \global\tag@false
     \global\@eqnswtrue
     \global\@eqcnt\z@\cr}


% This macro is a fix to the equation environment
 \def\endequation{%
     \ifmmode\ifinner % FLEQN hack
      \iftag@
        \addtocounter{equation}{-1} % undo the increment made in the begin part
        $\hfil
           \displaywidth\linewidth\@taggnum\egroup \endtrivlist
        \global\tag@false
        \global\@ignoretrue   
      \else
        $\hfil
           \displaywidth\linewidth\@eqnnum\egroup \endtrivlist
        \global\tag@false
        \global\@ignoretrue 
      \fi
     \else   
      \iftag@
        \addtocounter{equation}{-1} % undo the increment made in the begin part
        \eqno \hbox{\@taggnum}
        \global\tag@false%
        $$\global\@ignoretrue
      \else
        \eqno \hbox{\@eqnnum}% $$ BRACE MATCHING HACK
        $$\global\@ignoretrue
      \fi
     \fi\fi
 } 

 \newif\iftag@ \tag@false
 
 \def\tag{\@ifnextchar*{\@tagstar}{\@tag}}
 \def\@tag#1{%
     \global\tag@true
     \global\def\@taggnum{(#1)}}
 \def\@tagstar*#1{%
     \global\tag@true
     \global\def\@taggnum{#1}%  
}

% Do not add anything to the end of this file.  
% The last section of the file is loaded only if 
% amstex has not been.



\makeatother
\endinput


math0204360.extracted_bib
\begin{thebibliography}{99}
\bibitem{A-G}  Anshel, M., and Goldfeld, D., Zeta functions, one-way
functions and pseudorandom number generators, Duke Math. J., 88, 2 (1997),
371-390.

\bibitem{B-M}  Bierstone., \ E., Milman, P., Canonical desingularization in
characteristic zero by blowing up the maximum strata of a local invariant,
Invent. Math. 128 (1997), 207-302.

\bibitem{B-S}  Bodn\'{a}r, G\'{a}bor; Schicho, Josef. A computer program for
the resolution of singularities. Resolution of singularities (Obergurgl,
1997), 231--238, Progr. Math., 181, Birkh\"{a}user, Basel, 2000.

\bibitem{B-S1}  Bodn\'{a}r, G., Schicho, J., \ Automated resolution of
singularities for hypersurfaces, Journal of Symbolic Computation 30 (2000),
401-428.

\bibitem{D1}  Denef J., \ Report on Igusa's local zeta function,
S\'{e}minaire Bourbaki 1990/1991 (730-744) in Asterisque 201-203 (1991),
359-386.

\bibitem{D2}  Denef J., On the degree of Igusa's \ local zeta functions,
Amer. Math. J. 109 (1987), \ 991-1008.

\bibitem{D-H}  Denef J., Hoornaert Kathleen, \ Newton polyhedra and Igusa
local zeta function, Journal of Number Theory 89 (2001), 31-64.

\bibitem{K}  Knuth, D., The art of computer programming, 3 volumes,
Addison-Wesley, 1999.

\bibitem{G-J}  Garey, M. R., Johnson, D. S., Computers and intractability: A
guide to the theory of $\mathbf{NP}$-Completeness, 1979, \ W. H. Freedman
and Company, New York.

\bibitem{G1}  Goldman, Jay R., \ Numbers of solution of congruences:
Poincar\'{e} series for strongly nondegenerate forms, Proc. Amer. Math.
Soc., 87 (1983), 586-590.

\bibitem{G2}  Goldman, Jay R., \ Numbers of solution of congruences:
Poincar\'{e} series for algebraic curves, Adv. in Math. 62 (1986), 68-83.

\bibitem{G-L-N}  Goldreich, O., Levin, L. A., and Nisan, N., On constructing
1-1 one-way functions, preprint available at
http://www.wisdom.weizmann.ac.il/~\symbol{126}oded/cryptography.html.

\bibitem{G-K-L}  Goldreich, O., \ Krawczyk, H., \ Luby, M., \ On the
existence of pseudorandom number generators, SIAM J. on Computing, Vol. 22
(1993), 1163-1175.

\bibitem{I1}  Igusa, Jun-Ichi, An introduction to the theory of local zeta
functions, AMS /IP studies in \ advanced mathematics, v. 14, 2000.

\bibitem{I2}  Igusa, J., \ Complex powers and asymptotic expansions, I
Crelles J. Math., 268/269 (1974), 110-130; II, ibid., 278/279 (1975),
357-368.

\bibitem{I3}  Igusa, J., A stationary phase formula for $p-$adic integrals \
and its applications, in Algebraic Geometry and its Applications,
Springer-Verlag (1994), 175-194.

\bibitem{L-L-L}  Lenstra, A.K., Lenstra, H.W., Lov\'{a}sz, L., Factoring
polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534.

\bibitem{R}  Ruepel R., Analysis and design of stream ciphers,
Springer-Verlag, New York, 1986.

\bibitem{S-Z-G}  Saia, M.J., Zuniga-Galindo, W.A., Local zeta functions,
Newton polygons and non degeneracy conditions, to appear in Trans. Amer.
Math. Soc.

\bibitem{S}  P. Shor, Algorithms for quantum computation, discrete
logarithms, and factoring, in Proceedings of 35th Annual Symposium on
Foundations of Computer Science, IEEE Computer Society Press, Los alamitos,
California, 1994, 124-134.

\bibitem{Vi}  Villamayor, O., Constructiveness of Hironaka's resolution,
Ann. Scient. Ecole Norm. Sup. 4 (1989), 1-32.

\bibitem{V-K-S}  von zur Gathen, J., Karpinski, M., Shparlinski, I.,
Counting curves and their projections, in Proceedings ACM\ STOC\ 93, 805-812.

\bibitem{Wa}  Daqing Wan, Algorithmic theory of zeta functions over finite
fields,to appear in MSRI Computational Number Theory Proceedings.

\bibitem{Z-G1}  Zuniga-Galindo W. A., Igusa's local zeta functions of
semiquasihomogeneous polynomials, Trans. Amer. Math. Soc. 353, (2001),
3193-3207.

\bibitem{Z-G2}  Zuniga-Galindo W. A., Local zeta functions and Newton
polyhedra, \ to appear in Nagoya Math. J.

\bibitem{ZG3}  Zuniga-Galindo W.A., Local zeta function for non-degenerate
homogeneous mappings, preprint 2003.
\end{thebibliography}