Computing Igusa’s Local Zeta Functions of Univariate Polynomials, and Linear Feedback

Shift Registers

W. A. Zuniga-Galindo Department of Mathematics and Computer Science Barry University 11300 N. E. Second Avenue Miami Shores, Florida 33161 USA

                    wzuniga@mail.barry.edu

Abstract

We give a polynomial time algorithm for computing the Igusa local zeta function Z(s, f) attached to a polynomial f(x) ∈ ℤ[x], in one variable, with splitting field ℚ, 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.

1. Introduction

Let f(x) ∈ ℤ[x], x = (x_{1}, ⋯, 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) ≡ 0 mod p^{m} in (ℤ/p^{m}ℤ)^{n}, m ≧ 1, and H(t, f) for the Poincaré series

H(t, f) = ∑_{m=0}^{∞} N_{m}(f)(p^{−n}t)^{m},

with t ∈ ℂ, | t |< 1, and N_{0}(f) = 1. This paper is dedicated to the computation of the sequence {N_{m}(f)}_{m≧0} when f is an univariate polynomial with splitting field ℚ.

Igusa showed that the Poincaré series H(t, f) admits a meromorphic continuation to the complex plane as a rational function of t [14], [15]. 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é series H(t, f)?

The computation of the Poincaré 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 ℚ_{p} the field of p−adic numbers, and by ℤ_{p} the ring of p−adic integers. For x ∈ ℚ_{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:

Z(s, f) = ∫_{ℤ_{p}^{n}} |f(x)|_{p}^{s} | dx |, s ∈ ℂ,

where Re(s) > 0, and | dx | denotes the Haar measure on ℚ_{p}^{n} so normalized that ℤ_{p}^{n} has measure 1. The following relation between Z(s, f) and H(t, f) holds (see [14], theorem 8.2.2):

H(t, f) = \frac{1 − tZ(s, f)}{1 − t}, t = p^{−s}.

Thus, the rationality of Z(s, f) implies the rationality of the Poincaré series H(t, f), and the computation of H(t, f) is equivalent to the computation ofZ(s, f). Igusa [14, theorem 8.2.1] 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) ∈ ℤ[x], in one variable, with splitting field ℚ, 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 7.1).

Many authors have found explicit formulas for Z(s, f), or H(f, t), for several classes of polynomials, among them [6], [7], [10], [11], [[16] and the references therein], [19], [24], [25]. 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 [23], [22]. 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 [6]. 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 [2], [3], [4], [21].

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 ℤ/2ℤ is an NP−complete problem on a Turing Machine [9, page 251, problem AN9]. Then in the case of 2−adic numbers, the computation of the Igusa local zeta function is an NP−complete problem.

Recently, Anshel and Goldfeld have shown the existence of a strong connection between the computation of zeta functions and cryptography [1]. 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 P ≠ NP. Most of the present candidates for one-way functions are constructed on the intractability of problems like integer factorization and discrete logarithms [12]. Recently, P. Shor has introduced a new approach to attack these problems [20]. Indeed, Shor have shown that on a quantum computer the integer factorization and discrete logarithm problems can be computed in polynomial time.

We set

H = {H(t, f) | f(x) ∈ ℤ[x], in one variable, with splitting field ℚ},

and N^{∞} (ℤ) for the set of finite sequences of integers. For each positive integer u and a prime number p, we define

\begin{aligned}F_{u,p} : & H & → & ℕ^{∞} (ℤ) \\ & H(t, f) & → & \{N_{0}(f, p), N_{1}(f, p), ⋯, N_{u}(f, p)\}. \end{aligned}

Our second result asserts that F_{u,p}(H(t, f)) can be computed in polynomial time, for every H(t, f) in H (see theorem 8.1). 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}, ⋯, a_{u}}, how difficult is it to determine whether or not there exists a Poincaré series H(t, f) = ∑_{m=0}^{∞} N_{m}(f)(p^{−1}t)^{m}, such that a_{i} = N_{i}(f), i = 1,⋯, 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).

2. 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) ∈ ℤ[x], in one variable, whose splitting field is ℚ, find an explicit expression for the meromorphic continuation of Z(s, f). The algorithm is as follows.

Algorithm Compute Z(s, f)

Input : A polynomial f(x) ∈ ℤ[x], in one variable, whose splitting field is ℚ.

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

(1) Factorize f(x) in ℚ[x]: f(x) = α_{0} ∏_{i=1}^{r}(x − α_{i})^{e_{i}} ∈ ℚ[x].

(2) Compute

l_{f} = \{ \begin{matrix}1 + max\{v_{p}(α_{i} − α_{j}) | i ≠ j, 1 ≤ i, j ≤ r\}, & if r ≧ 2; \\ 1, & if r = 1. \end{matrix}

(3) Compute the p−adic expansions of the numbers α_{i}, i = 1, 2, ⋯, r modulo p^{l_{f} +1}.

(4) Compute the tree T (f, l_{f}) associated to f(x) and p (for the definition of T (f, l_{f}) see (4.2)).

(5) 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 (5.1)).

(6) Return Z(s, f) = G(s, T (f, l_{f}), p).

(7) End

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ász [17]. If d_{f} denotes the degree of f(x) = ∑_{i} a_{i}x^{i}, and

∥f∥ = \sqrt{∑_{i} a_{i}^{2}},

then the mentioned factoring algorithm needs O (d_{f}^{6} + d_{f}^{9}(log ∥f∥)) arithmetic operations, and the integers on which these operations are performed each have a binary length

O (d_{f}^{3} + d_{f}^{2}(log ∥f∥))

[17, theorem 3.6].

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 ℚ. 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).

3. 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 [16]. 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 [[16] and the references therein], [19], [24], [25], [26].

Given a polynomial f(x) ∈ ℤ_{p}[x]\ pℤ_{p}[x], we denote by \overline{f(x)} its reduction modulo pℤ_{p}, i.e., the polynomial obtained by reducing the coefficients of f(x) modulo pℤ_{p}. We define for each x_{0} ∈ ℤ_{p},

f_{x_{0}}(x) = p^{−e_{x_{0}}}f(x_{0} + px),

where e_{x_{0}} is the minimum order of p in the coefficients of f(x_{0} + px). Thus f_{x_{0}}(x) ∈ ℤ_{p}[x]\ pℤ_{p}[x]. We shall call the polynomial f_{x_{0}}(x) the dilatation of f(x) at x_{0}. We also define

ν(\overline{f}) = Card\{\overline{z} ∈ 𝔽_{p} | \overline{f}(\overline{z}) ≠ 0\},
δ(\overline{f}) = Card\{\overline{z} ∈ 𝔽_{p} | \overline{z} is a simple root of \overline{f}(\overline{z}) = 0\}.

We shall use {0, 1, ⋯, p − 1} ⊆ ℤ_{p} as a set of representatives of the elements of 𝔽_{p} = ℤ/ pℤ = \{\overline{0}, \overline{1}, ⋯, \overline{p − 1}\}. Let S = S(f) denote the subset of \{0, 1, ⋯, p − 1\} ⊆ ℤ_{p} which is mapped bijectively by the canonical homomorphism ℤ_{p} → ℤ_{p}/pℤ_{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.

Proposition 3.1 ([14, theorem 10.2.1]). Let f(x) ∈ ℤ_{p}[x]\ pℤ_{p}[x] be a non-constant polynomial. Then

Z(s, f) = p^{−1}ν(\overline{f}) + δ(\overline{f})\frac{(1 − p^{−1})p^{−1−s}}{(1 − p^{−1−s})} + ∑_{ξ∈S} p^{−1−e_{ξ}s} ∫_{ℤ_{p}} | f_{ξ}(x) |_{p}^{s} dx.

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).

3.1. Example. Let f(x) = (x − α_{1})(x − α_{2})^{3}(x − α_{3})(x − α_{4})^{2}(x − α_{5}) be a polynomial such that α_{1}, α_{2} , α_{3}, α_{4} , α_{5} are integers having the following p−adic expansions:

α_{1} = a + dp + kp^{2},
α_{2} = a + dp + lp^{2},
α_{3} = b + gp + mp^{2},
α_{4} = c + hp + np^{2},
α_{5} = c + hp + rp^{2},

where the p-adic digits a, b, c, d, g, h, l, m, n, r belong to {0, 1, ⋯, 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}, ν(\overline{f}) = p − 3, δ(\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

Z(s, f) = p^{−1}(p − 3) + \frac{(1 − p^{−1})p^{−1−s}}{1 − p^{−1−s}} + p^{−1−4s} ∫_{ℤ_{p}} |f_{a}(x)|_{p}^{s} | dx |
+p^{−1−3s} ∫_{ℤ_{p}} |f_{c}(x)|_{p}^{s} | dx | .  (3.1)

We apply SPF to the integrals involving f_{a}(x) and f_{c}(x) in (3.1). 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), ν(\overline{f_{a}}) = p − 1, and δ(\overline{f_{a}}) = 0, it follows from (3.1) using SPF that

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}
+p^{−2−8s} ∫_{ℤ_{p}} |f_{a,d}(x)|_{p}^{s} | dx | +p^{−1−3s} ∫_{ℤ_{p}} |f_{c}(x)|_{p}^{s} | dx | .  (3.2)

Now, we apply SPF to the integral involving f_{c}(x) in (3.2). 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), ν(\overline{f_{c}}) = p − 1, and δ(\overline{f_{c}}) = 0, it follows from (3.2) using SPF that

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}
+p^{−2−8s} ∫_{ℤ_{p}} |f_{a,d}(x)|_{p}^{s} | dx | +p^{−1}(p − 1)p^{−1−3s}
+p^{−2−6s} ∫_{ℤ_{p}} |f_{c,h}(x)|_{p}^{s} | dx | .  (3.3)

By applying SPF to the integral involving f_{a,d}(x) in (3.3), 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}, ν(\overline{f_{a,d}}) = p − 2, and δ(\overline{f_{a,d}}) = 1, we obtain that

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}

+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}}

+\frac{(1 − p^{−1})p^{−3−11s}}{1 − p^{−1−3s}} + p^{−2−6s} ∫_{ℤ_{p}} |f_{c,h}(x)|_{p}^{s} | dx | .  (3.4)

Finally, by applying SPF to the integral involving f_{c,h}(x) in (3.4), we obtain that

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}

+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}}

+\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}}

+\frac{(1 − p^{−1})p^{−3−8s}}{1 − p^{−1−2s}}.  (3.5)

Remark 3.1. If α = \frac{a}{b} ∈ ℚ, and v_{p}(α) < 0, then

| x − α |_{p}=| α |_{p}, for every x ∈ ℤ_{p}.  (3.6)

On the other hand, a polynomial of the form

f(x) = α_{0} ∏_{i=1}^{r}(x − α_{i})^{e_{i}} ∈ ℚ[x],

can be decomposed as f(x) = α_{0}f_{−}(x)f_{+}(x), where

f_{−}(x) = ∏_{{α_{i}|v_{p}(α_{i})<0}}(x − α_{i})^{e_{i}}, and f_{+}(x) = ∏_{{α_{i}|v_{p}(α_{i})≧0}}(x − α_{i})^{e_{i}}.  (3.7)

From (3.6) and (3.7) follow that

Z(s, f) =| α_{0} ∏_{{α_{i}|v_{p}(α_{i})<0}} α_{i}^{e_{i}} |_{p}^{s} Z(s, f_{+}).

Thus, from a computational point of view, we may assume without loss of generality that all roots of f(x) are p−adic integers.

4. 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

\{0\} = ℤ/p^{0}ℤ\underleftarrow{ϕ_{1}} ℤ/p^{1}ℤ \underleftarrow{ϕ_{2}} ℤ/p^{2}ℤ \underleftarrow{ϕ_{3}} ⋯

where ϕ_{l} the are the natural homomorphisms. The vertices of U are the elements of ℤ/p^{l}ℤ, for l = 0, 1, 2, ⋯, and the directed edges are u → v where u ∈ ℤ/p^{l}ℤ and ϕ_{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

u → u^{(1)} → ⋯ → u^{(m)} = v.

The notation u ≧ v will mean that u = v or u > v. The level l(u) of a vertex u is m if u ∈ ℤ/p^{m}ℤ. The valence V al(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 ∈ T and u > v, then v ∈ T. Thus T together with the directed edges u → v, where u, v ∈ T , is again a tree with root {0}.

A tree T is named a weighted tree, if there exists a weight function W : T → ℕ. The value W (u) is called the weight of vertex u.

If x ∈ ℤ_{p}, and x_{l} denotes its residue class modulo p^{l}, then every vertex of U is of the type x_{l} with l ∈ ℕ.

A stalk is defined as a tree K having at most one vertex at each level. Thus a stalk is either finite, of the type

{0} ⟵ u^{(1)} ⟵ ⋯ ⟵ u^{(l)},

or infinite, of the type

{0} ⟵ u^{(1)} ⟵ · · ·.

Clearly a finite stalk may be written as

{0} ⟵ x_{1} ⟵ ⋯ ⟵ x_{l},

with x ∈ ℤ, and infinite stalks as

{0} ⟵ x_{1} ⟵ x_{2} ⟵ ⋯,

with x ∈ ℤ_{p}. Thus there is a 1 − 1 correspondence between infinite stalks and p−adic integers.

4.1. Tree Attached to a Polynomial. Let

f(x) = α_{0} ∏_{i=1}^{r}(x − α_{i})^{e_{i}} ∈ ℚ[x]  (4.1)

be a non-constant polynomial, in one variable, of degree d_{f}, such that v_{p}(α_{i}) ⩾ 0, i = 1, 2, ⋯, r. We associate to f(x) and a prime number p the integer

l_{f} = \{ \begin{matrix}1 + max\{v_{p}(α_{i} − α_{j}) | i ≠ j, 1 ≤ i, j ≤ r\}, & if r ≧ 2; \\ 1, & if r = 1. \end{matrix}

We set

α_{i} = a_{0,i} + a_{1,i} p + ⋯ + a_{j,i} p^{j} + ⋯ + a_{l_{f} ,i} p^{l_{f}} mod p^{l_{f} +1},

a_{j,i} ∈ {0, 1, ⋯, p − 1}, j = 0, 1, ⋯, l_{f}, i = 1, 2, ⋯, r, for the p−adic expansion modulo p^{l_{f} +1} of α_{i}. We attach a weighted tree T (f, l_{f}) to f as follows:

T (f, l_{f}, p) = T (f, l_{f}) = ⋃_{i=1}^{r} K(α_{i}, l_{f}),  (4.2)

where K(α_{i}, l_{f}) denotes the stalk corresponding to the p−adic expansion of α_{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

W (u) = \{ \begin{matrix}∑_{\{i|α_{i}≡u mod p^{m}\}} e_{i}, & if m ≧ 1; \\ 0, & if m = 0. \end{matrix}  (4.3)

Given a vertex u ∈ T (f, l_{f}), we define the stalk generated by u to be

B_{u} = {v ∈ T (f, l_{f}) | u ≧ v}.

We associate a weight W^{∗}(B_{u}) to B_{u} as follows:

W^{∗}(B_{u}) = ∑_{v∈B_{u}} W (v).  (4.4)

4.2. 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 (4.1), can be computed in polynomial time. There are well known programming techniques to construct and manipulate trees and forests (see e.g. [8, Volume 1]), 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.

Proposition 4.1. The computation of a tree T (f, l_{f}) attached to a polynomial f(x), of type (4.1), from the p−adic expansions modulo p^{l_{f} +1} of its roots

α_{i} = a_{0,i} + a_{1,i} p + ⋯ + a_{l_{f} ,i}p^{l_{f}} mod p^{l_{f} +1}

and multiplicities e_{i}, i = 1, 2, ⋯, r, involves O(l_{f}^{2} d_{f}^{3}) arithmetic operations on integers with binary length

O(max{log p, log(l_{f}d_{f})}).

Proof. We assume that T (f, l_{f}) is finite set of the form

T = {Level_{0}, ⋯,Level_{j}, ⋯,Level_{l_{f} +1}},  (4.5)

where Level_{j} represents the set of all vertices with level j. Each Level_{j} is a set of the form

Level_{j} = {u_{j,1}, ⋯, u_{j,i}, ⋯, u_{j,m_{j}}},

and each u_{j,i} is a weighted vertex for every i = 1, ⋯, m_{j}. A weighted vertex u_{j,i} is a set of the form

u_{j,i} = { W (u_{j,i}), V al(u_{j,i}), W^{∗}(B_{u_{j,i}})},

where W (u_{j,i}) is the weight of u_{j,i}, V al(u_{j,i}) is its valence, and W^{∗}(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

W^{∗}(B_{u_{j,i}}) = ∑_{v∈B_{u_{j,i}}} W (v).

For the computation of a vertex u_{j,i} of level j, we proceed as follows. We put I = {1, 2, ⋯, r}, and

M_{j} = {α_{i} mod p^{j} | i ∈ I}.

For each 0 ≤ j ≤ l_{f} + 1, we compute a partition of I of type

I = ⋃_{i=1}^{l_{j}} I_{j,i},  (4.6)

such that

α_{t} mod p^{j} = α_{s} mod p^{j},

for every t, s ∈ 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: α_{t} mod p^{j} = α_{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 (4.6), for a fixed j, involves the comparison of α_{t} with α_{l} for l = t + 1, t + 2, ⋯, r. This computation requires O(jr^{2}) arithmetic operations on integers with binary length O(log p). Since j ≦ l_{f} + 1, the computation of partition (4.6) 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

W (u_{j,i}) = ∑_{k∈I_{j,i}} e_{k}.

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

V al(u_{j,i}) = Card{I_{j+1,l} | I_{j+1,l} ⊆ I_{j,i}},

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 V al(u_{j,m}) involves the computation of a “yes or no” answer for the question I_{j+1,l} ⊆ 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 V al(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^{∗}(B_{u_{j,i}}) is given by the formula

W^{∗}(B_{u_{j,i}}) = ∑_{l=0}^{j−1} ∑_{I_{j,i}⊆I_{l,k}} W (I_{l,k}),

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^{∗}(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})}).

5. 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) ∈ ℚ(p^{−s}) defined as follows.

We set

M_{T (f,l_{f})} = \{u ∈ T (f, l_{f}) | \begin{matrix}W (u) = 1, and there no exists v ∈ T (f, l_{f}) \\ with W (v) = 1, such that u > v. \end{matrix} \} ,

and

L_{u}(p^{−s}) = \{ \begin{matrix}\frac{(1−p^{−1})p^{−l(u)−W^{∗}(Bu)s}}{(1−p^{−1−W (u)s})} , if & l(u) = 1 + l_{f}, and W (u) ≧ 2; \\ p^{−1}(p − V al(u))p^{−l(u)−W^{∗}(B_{u})s}, if & 0 ≦ l(u) ≦ l_{f}, and W (u) ≠ 1; \\ \frac{(1−p^{−1})p^{−l(u)−W^{∗}(Bu)s}}{1−p^{−1−s}}, if & u ∈ M_{T (f,l_{f})}; \\ 0, if & W (u) = 1, and u ∉ M_{T (f,l_{f})}. \end{matrix}

With all the above notation, we define the generating function attached to T (f, l_{f}) and p as

G(s, T (f, l_{f}), p) = ∑_{u∈T (f,l_{f})} L_{u}(p^{−s}).  (5.1)

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.

Proposition 5.1. The generating function attached to a tree T (f, l_{f}) and a prime p satisfies

G(s, T (f, l_{f}), p) = p^{−1}ν(\overline{f}) + δ(\overline{f})\frac{(1 − p^{−1})p^{−1−s}}{(1 − p^{−1−s})}
+ ∑_{ξ∈S} p^{−1−e_{ξ}s}G(s, T (f_{ξ}, l_{f} − 1), p).  (5.2)

Proof. Let A_{f} = {u ∈ T (f, l_{f}) | l(u) = 1, W (u) = 1}, and B_{f} = {u ∈ T (f, l_{f}) | l(u) = 1, W (u) ≧ 2}. We have the following partition for T (f, l_{f}) :

T (f, l_{f}) = {0} ⋃ A_{f} ⋃ ( ⋃_{u∈B_{f}} T_{u}),  (5.3)

with

T_{u} = {v ∈ T (f, l_{f}) | v ≧ u}.

Each T_{u} is a rooted tree with root {u}. From partition (5.3) and the definition of G(s, T (f, l_{f}), p), it follows that

G(s, T (f, l_{f}), p) = p^{−1} (p − V al(\{0\})) + Card\{A_{f}\}\frac{(1 − p^{−1})p^{−1−s}}{(1 − p^{−1−s})} +
∑_{u∈B_{f}} G(s, T_{u}),  (5.4)

with G(s, T_{u}) = ∑_{v∈T_{u}} L_{v}(p^{−s}).

Since there exists a bijective correspondence between the roots of \overline{f}(x) ≡ 0 mod p and the vertices of T (f, l_{f}) with level 1,

p − V al(\{0\}) = ν(\overline{f}), and Card\{A_{f}\} = δ(\overline{f}).  (5.5)

Now, if the vertex u corresponds to the root \overline{f}(ξ) ≡ 0 mod p, then

T_{u} = (  ⋃_{{α_{i}|α_{i}≡ξ mod p}} K(α_{i}, l_{f})) \ {0}.  (5.6)

On the other hand, we have that

T (f_{ξ}, l_{f} − 1) = ⋃_{\{α_{i}|α_{i}≡ξ mod p\}} K(\frac{α_{i−ξ}}{p} , l_{f} − 1).  (5.7)

Now we remark that the map α_{i} → \frac{α_{i}−ξ}{p} induces a isomorphism between the trees T_{u} and T (f_{ξ}, l_{f} − 1), that preserves the weights of the vertices; and thus we may suppose that T_{u} = T (f_{ξ}, l_{f} − 1). The level function l_{T} of T (f_{ξ}, 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, ⋯, p − 1\} ⊆ ℤ_{p} whose reduction modulo pZ_{p} is equal to the set of roots of \overline{f}(ξ) = 0 with multiplicity greater or equal than two. Therefore, it holds that

G(s, T_{u}) = p^{−1−e_{ξ}s}G(s, T (f_{ξ}, l_{f} − 1), p).  (5.8)

The result follows from (5.4) by the identities (5.5) and (5.8).

Lemma 5.1. Let p be a fixed prime number and v_{p} the corresponding p−adic valuation, and

f(x) = α_{0} ∏_{i=1}^{r}(x − α_{i})^{e_{i}} ∈ ℚ[x] \ ℚ,

a polynomial such that v_{p}(α_{i}) ≧ 0, for i = 1, ⋯, r. Then

Z(s, f) = G(s, T (f, l_{f}), p).

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 ≧ 2. Since l_{f} = 1, it holds that v_{p}(α_{i} − α_{j}) = 0, for every i, j, satisfying i ≠ j, and thus \overline{α_{i}} ≠ \overline{α_{j}}, if i ≠ j. By applying SPF, we have that

Z(s, f) = p^{−1}ν(\overline{f}) + δ(\overline{f})\frac{(1 − p^{−1})p^{−1−s}}{(1 − p^{−1−s})} + ∑_{ξ∈S} p^{−1−e_{ξ}s} \frac{(1 − p^{−1})}{(1 − p^{−1−e_{ξ}s})},  (5.9)

where each e_{ξ} = e_{j} ≧ 2, for some j, and α_{j} = ξ + pβ_{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, ⋯, 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 ≦ l_{f} ≦ k, k ∈ ℕ.

Case l_{f} = k + 1, k ∈ ℕ

Let f(x) be a polynomial satisfying the lemma’s hypothesis, and l_{f} = k + 1, k ≧ 1. By applying SPF, we obtain that

Z(s, f) = p^{−1}ν(\overline{f}) + δ(\overline{f})\frac{(1 − p^{−1})p^{−1−s}}{(1 − p^{−1−s})} + ∑_{ξ∈S} p^{−1−e_{ξ}s} ∫ | f_{ξ}(x) |_{p}^{s} dx.  (5.10)

Now, since l_{f_{ξ}} = l_{f} − 1, for every ξ ∈ S, it follows from the induction hypothesis applied to each f_{ξ}(x) in (5.10), that

Z(s, f) = p^{−1}ν(\overline{f}) + δ(\overline{f})\frac{(1 − p^{−1})p^{−1−s}}{(1 − p^{−1−s})} + ∑_{ξ∈S} p^{−1−e_{ξ}s}G(s, T (f_{ξ}, l_{f} − 1), p).  (5.11)

Finally, from identity (5.2), and (5.11), we conclude that

Z(s, f) = G(s, T (f, l_{f}), p).  (5.12)

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

Proposition 5.2. The computation of the generating function

G(s, T (f, l_{f}), p)

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})}).

Proof. This is a consequence of proposition 4.1, and the definition of generating function.

6. 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).

Proposition 6.1. Let

B = max ; \begin{matrix}1 ≤ i, & j ≤ r \\ i ≠ j \end{matrix} \{ | c_{j,i} | , | d_{j,i} | | α_{j} − α_{i} = \frac{c_{j,i}}{d_{j,i}}, c_{j,i}, d_{j,i} ∈ ℤ \ \{0\}\}.

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}).

Proof. First, we observe that for c ∈ ℤ \ \{0\}, the computation of v_{p}(c) involves O(\frac{log|c|}{log p}) divisions of integers of binary length O(max{log | c |, log p}). Thus the computation of v_{p}(\frac{c}{d}) = v_{p}(c) − v_{p}(d), involves O(\frac{max\{log|c|, log|d|\}}{log p}) divisions and subtractions of integers with binary length

O(max{log | c |, log | d |, log p}).

From these observations follow that the computation of v_{p}(α_{j} − α_{i}), i ≠ j, 1 ≤ i, j ≤ 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}(α_{j} − α_{i}), i ≠ j, 1 ≤ i, j ≤ 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}).

Proposition 6.2. Let p be a fixed prime and γ = \frac{c}{b} ∈ ℚ, with c, b ∈ ℤ \ \{0\}, and v_{p}(γ) ≧ 0. The p−adic expansion

γ = a_{0} + a_{1} p + ⋯ + a_{j}p^{j} + ⋯ + a_{m}p^{m},

modulo p^{m+1} involves O(m+log(max{| b |, p})) arithmetic operations on integers with binary length O(max{log | c |, log | b |, log p}).

Proof. Let y ∈ {1, ⋯, p − 1} be an integer such that yb ≡ 1 mod p. This integer can be computed by means of the Euclidean algorithm in O(log(max{| b |, p})) arithmetic operations involving integers of binary length O(max{log | b |, log p}) (cf. [8, Volume 2, section 4.5.2]).

We set γ = γ_{0} = \frac{c}{b}, c_{0} = c, and define a_{0} ≡ yc mod p. With this notation, the p−adic digits a_{i}, i = 1,⋯, m, can be computed recursively as follows:

γ_{i} = \frac{\frac{(c_{i−1}−a_{i−1}b)}{p}}{b} = \frac{c_{i}}{b} ,

a_{i} = yc_{i} mod p.

Thus the computation of the p−adic expansion of γ needs O(m + log(max{| b |, p})) arithmetic operations on integers with binary length

O(max{log | c |, log | b |, log p}).

Corollary 6.1. Let p be a fixed prime number and v_{p} the corresponding p−adic valuation, and

f(x) = α_{0} ∏_{i=1}^{r}(x − α_{i})^{e_{i}} ∈ ℚ[x],

a non-constant polynomial such that v_{p}(α_{i}) ≧ 0, i = 1, ⋯, r. The computation of the p−adic expansions modulo p^{l_{f} +1} of the roots α_{i}, i = 1, 2, ⋯, 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}).

Proof. The corollary follows directly from the two previous propositions.

7. Computing local zeta functions of polynomials with splitting ℚ

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

Theorem 7.1. The algorithm Compute Z(s, f) outputs the meromorphic continuation of the Igusa local zeta function Z(s, f) of a polynomial f(x) ∈ ℤ[x], in one variable, with splitting field ℚ. The number of arithmetic operations needed by the algorithm is

O (d_{f}^{6} + d_{f}^{9} log(∥f∥) + l_{f}^{2}d_{f}^{3} + d_{f}^{2} log (max{B, p})) ,

and the integers on which these operations are performed have a binary length

O (max{log p, log l_{f}d_{f}, log B, d_{f}^{3} + d_{f}^{2} log(∥f∥)}).

Proof. By remark (3.1), we may assume without loss of generality that

f(x) = α_{0} ∏_{i=1}^{r}(x − α_{i})^{e_{i}} ∈ ℚ[x] \ ℚ,

with v_{p}(α_{i}) ≧ 0, i = 1, ⋯, r. The correctness of the algorithm follows from lemma 5.1. The complexity estimates are obtained as follows: the number of arithmetic operations needed in the steps 2 (cf. proposition 6.1), 3 (cf. corollary 6.1), 4 (cf. proposition 4.1), 5 (proposition 5.2), and 6 is at most

O (l_{f}^{2}d_{f}^{3} + d_{f}^{2} log (max{B, p}));

and these operations are performed on integers whose binary length is at most

O (max{log p, log l_{f}d_{f}, log B}) .

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ász (see theorem 3.6 of [17]).

8. Stream Ciphers and Poincaré series

There is a natural connection between Poincaré series and stream ciphers. In order to explain this relation, we recall some basic facts about stream ciphers [18]. Let 𝔽_{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} ∈ 𝔽_{p^{n}}, i = 1, ⋯, r (called taps), a Linear Feedback Shift Register, abbreviated LFSR, of length r consists of r cells with initial contents {a_{i} ∈ 𝔽_{p^{n}} | i = 1, ⋯, r}. For any n ⩾ r, if the current state is (a_{n−1}, ⋯, a_{n−r}), then a_{n} is determined by the linear recurrence relation

a_{n} = − ∑_{i=1}^{r} a_{n−i}q_{i}.

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} ≠ 0, the following polynomial q(x) ∈ 𝔽_{p^{n}}[x] of degree r appears in the analysis of LFSRs:

q(x) = q_{0} + q_{1}x + · · ·. + q_{r}x^{r} with q_{0} = −1.

This polynomial is called the connection polynomial. An infinite sequence A = {a_{i} ∈ 𝔽_{p^{n}} | i ∈ ℕ} has period T if for any i ⩾ 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 [18].

(1) 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.

(2) The Poincaré series g(x) = ∑_{i=0}^{∞} a_{i}x^{i} associated with the output sequence is called the

generating function of the sequence. It is a rational function over 𝔽_{p^{n}} of the form g(x) = \frac{L(x)}{R(x)}, with L(x), R(X) ∈ 𝔽_{p^{n}}[x], deg(R(X)) < r. The output sequence is strictly periodic if and only if deg(L(X)) < deg(R(X)).

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

We set 𝔽_{p^{n}}(x) for the field of rational functions over 𝔽_{p^{n}}, and N^{∞}(𝔽_{p^{n}}) for the set of sequences of the form {b_{0}, ⋯, b_{u}}, b_{i} ∈ 𝔽_{p^{n}}, 0 ≤ i ≤ u, u ∈ ℕ. From the above considerations, it is possible to identify an LFSR with a function F_{u}, u ∈ ℕ, defined as follows:

\begin{aligned}F_{u} : & 𝔽_{p^{n}}(x) & → & N^{∞}(𝔽_{p^{n}}) \\ & ∑_{i=0}^{∞} a_{i}x^{i} & → & \{a_{0}, ⋯, a_{u}\}. \end{aligned}  (8.1)

We set

H = {H(t, f) | f(x) ∈ ℤ[x], in one variable, with splitting field ℚ},

and N^{∞} (ℤ) for the set of finite sequences of integers. Also, for each u ∈ ℕ, and a prime number p, we define

\begin{aligned}F_{u,p} : & H & → & ℕ^{∞} (ℤ) \\ & H(t, f) & → & \{N_{0}(f, p), N_{1}(f, p), ⋯, N_{u}(f, p)\}. \end{aligned}  (8.2)

Thus the mappings F_{u,p} can be seen as LFSRs, or stream ciphers, over ℤ. 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.

Theorem 8.1. For every H(t, f) ∈ 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

O(max{ (l_{f} + u) log p, log(d_{f}l_{f})}).

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

Z(s, f) = Z(t, f) = ∑_{m=0}^{∞} c_{m}(f, p)t^{m},

with c_{m}(f, p) = vol({x ∈ ℤ_{p} | v_{p}(f(x)) = m}).

Proposition 8.1. Let f(x) ∈ ℤ[x]\ℤ be a polynomial in one variable and p a prime number. The following formula holds for N_{n}(f, p):

N_{n}(f, p) = \{ \begin{matrix}1, & if & n = 0; \\ p^{n} (1 − ∑_{j=1}^{n} c_{j−1}(f, p)), & if & n ⩾ 1. \end{matrix}  (8.3)

Proof. The result follows by comparing the coefficient of t^{n} of the series

∑_{n=0}^{∞} \frac{N_{n}(f, p)}{p^{n}}t^{n} and ∑_{n=0}^{∞} d_{n}t^{n},

in the following equality :

H(t, f) = ∑_{n=0}^{∞} \frac{N_{n}(f, p)}{p^{n}}t^{n} = \frac{1 − t ( ∑_{m=0}^{∞} c_{m}(f, p)t^{m})}{1 − t} = ∑_{n=0}^{∞} d_{n}t^{n}.

We associate to each u ∈ T (f, l_{f}), and j ∈ ℕ, a rational integer a_{j}(u) defined as follows:

a_{j}(u) = \{ \begin{matrix}\frac{(p−1)}{p^{l(u)+1+y(u)}} , if & \begin{matrix}l(u) = 1 + l_{f}, W (u) ≧ 2, j = W^{∗}(B_{u}) + y(u)W (u), \\ for some y(u) ∈ ℕ; \end{matrix} \\ \frac{(p−V al(u))}{p^{l(u)+1}}, if & 0 ≦ l(u) ≦ l_{f}, W (u) ≠ 1, j = W^{∗}(B_{u}); \\ \frac{(p−1)}{p^{l(u)+1+y(u)}} , if & \begin{matrix}u ∈ M_{T (f,l_{f})}, j = W^{∗}(B_{u}) + y(u), \\ for some y(u) ∈ ℕ; \end{matrix} \\ 0,  if & W (u) = 1, and u ∉ M_{T (f,l_{f})}; \\ 0, & in other cases. \end{matrix}  (8.4)

Proposition 8.2. Let f(x) ∈ ℤ[x] \ ℤ be a polynomial in one variable, with splitting field ℚ, and p a prime number. The following formula holds:

c_{j}(f, p) = ∑_{u∈T (f,l_{f})} a_{j}(u), j ≧ 0.  (8.5)

Proof. As a consequence of lemma (5.1), we have the following identity:

Z(t, f) = ∑_{u∈T (f,l_{f})} L_{u}(t),  (8.6)

with

L_{u}(t) = \{ \begin{matrix}\frac{(p−1)t^{W^{∗}(Bu)}}{p^{l(u)+1}(1−p^{−1}t ^{W (u)})}, if & l(u) = 1 + l_{f}, W (u) ≧ 2; \\ \frac{(p−V al(u))}{p^{l(u)+1}}t^{W^{∗}(B_{u})}, if & 0 ≦ l(u) ≦ l_{f}, W (u) ≠ 1; \\ \frac{(p−1)t^{W^{∗}(Bu)}}{p^{l(u)+1}(1−p^{−1}t)}, if & u ∈ M_{T (f,l_{f})}; \\ 0, if & W (u) = 1, and u ∉ M_{T (f,l_{f})}. \end{matrix}  (8.7)

The result follows by comparing the coefficient of t^{j} in the series Z(t, f) = ∑_{m=0}^{∞} c_{m}(f, p)t^{m},

and Z(t, f) = ∑_{u∈T (f,l_{f})} L_{u}(t).

Proposition 8.3. Let f(x) ∈ ℤ[x] \ ℤ be a polynomial in one variable, with splitting field ℚ, and p a prime number.

(1) The computation of N_{n}(f, p), n ≧ 1, from the c_{j−1}(f, p), j = 1, ⋯, n, involves O(n) arithmetic operations on integers with binary length O(n log p).

(2) The computation of c_{j}(f, p), j ≧ 0, from Z(t, f), involves O(d_{f}l_{f}) arithmetic operations on integers with binary length

O(max{(j + l_{f}) log p, log p, log(d_{f}l_{f})}).

(3) The computation of any N_{n}(f, p), n ≧ 1, from Z(t, f), involves O(nd_{f}l_{f}) arithmetic operations on integers with binary length

O(max{(n + l_{f}) log p, log(d_{f}l_{f})}).

Proof. (1) By (8.4) and (8.5), c_{j}(f, p) = \frac{v_{j}}{p^{m_{j}}}, v_{j}, m_{j} ∈ ℕ. In addition,

c_{j−1}(f, p) = p^{−j+1}N_{j−1}(f, p) − p^{−j}N_{j}(f, p).

Thus p^{n}c_{j−1}(f, p) ∈ ℕ, for j = 1, ⋯, n, and m_{j} ≤ n, for j = 1, ⋯, n. From (8.3), it follows that

N_{n}(f, p) = p^{n} − ∑_{j=1}^{n} p^{n}c_{j−1}(f, p), n ⩾ 1.  (8.8)

The above formula implies that the computation of N_{n}(f, p), n ≧ 1, from the c_{j−1}(f, p), j = 1, ⋯, 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. (8.6)) involves O(1) arithmetic operations (cf. (8.4), (8.7)) on integers of binary length O(max{log p, log(d_{f}l_{f})}). Indeed, since the numbers l(u), W^{∗}(B_{u}), W (u), u ∈ T (f, l_{f}) are involved in this computation, we know by proposition 4.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 ∈ 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. (8.5)). 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′), u, u′ ∈ T (f, l_{f}) are bounded by (l_{f} + 1 + j) log p (cf. (8.4)). 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 (8.8).

8.1. Proof of Theorem 8.1. The theorem follows from proposition 8.3 (3).

9. Acknowledgments.

This work supported by COLCIENCIAS-Grant # 089-2000.

References

[1] Anshel, M., and Goldfeld, D., Zeta functions, one-way functions and pseudorandom number generators, Duke Math. J. 88 (1997), 371–390.

[2] 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.

[3] Bodnár, Gábor; Schicho, Josef. A computer program for the resolution of singularities. Resolution of singularities (Obergurgl, 1997), 231–238, Progr. Math., 181, Birkhäuser, Basel, 2000.

[4] Bodnár, G., Schicho, J., Automated resolution of singularities for hypersurfaces, J. Symbolic Comput. 30 (2000), 401–428.

[5] Denef J., Report on Igusa’s local zeta function, Séminaire Bourbaki 1990/1991 (730-744) in Astérisque 201–203 (1991), 359–386.

[6] Denef J., On the degree of Igusa’s local zeta functions, Amer. Math. J. 109 (1987), 991–1008.

[7] Denef J., Hoornaert Kathleen, Newton polyhedra and Igusa local zeta function, J. Number Theory 89 (2001), 31–64.

[8] Knuth, D., The Art of Computer Programming, 3 volumes, Addison-Wesley, 1999.

[9] Garey, M. R., Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, W. H. Freeman and Company, New York.

[10] Goldman, Jay R., Numbers of solution of congruences: Poincaré series for strongly nondegenerate forms, Proc. Amer. Math. Soc., 87 (1983), 586–590.

[11] Goldman, Jay R., Numbers of solution of congruences: Poincaré series for algebraic curves, Adv. in Math. 62 (1986), 68–83.

[12] Goldreich, O., Levin, L. A., and Nisan, N., On constructing 1-1 one-way functions, preprint available at http://www.wisdom.weizmann.ac.il/ ˜ oded/cryptography.html.

[13] Goldreich, O., Krawczyk, H., Luby, M., On the existence of pseudorandom number generators, SIAM J. on Computing, 22 (1993), 1163–1175.

[14] Igusa, Jun-Ichi, An Introduction to the Theory of Local Zeta Functions, AMS/IP Studies in Advanced Mathematics, v. 14, 2000.

[15] Igusa, J., Complex powers and asymptotic expansions, I J. Reine Angew. Math. 268/269 (1974), 110–130; II, ibid., 278/279 (1975), 357–368.

[16] Igusa, J., A stationary phase formula for p−adic integrals and its applications, in Algebraic Geometry and its Applications, Springer-Verlag (1994), 175–194.

[17] Lenstra, A.K., Lenstra, H.W., Lovász, L., Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534.

[18] Rueppel R., Analysis and Design of Stream Ciphers, Springer-Verlag, New York, 1986.

[19] Saia, M.J., Zuniga-Galindo, W.A., Local zeta functions, Newton polygons and non degeneracy conditions, to appear in Trans. Amer. Math. Soc.

[20] 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.

[21] Villamayor, O., Constructiveness of Hironaka’s resolution, Ann. Scient. Ecole Norm. Sup. 4 (1989), 1–32.

[22] von zur Gathen, J., Karpinski, M., Shparlinski, I., Counting curves and their projections, in Proceedings ACM STOC 1993, 805–812.

[23] Daqing Wan, Algorithmic theory of zeta functions over finite fields,to appear in MSRI Computational Number Theory Proceedings.

[24] Zuniga-Galindo W. A., Igusa’s local zeta functions of semiquasihomogeneous polynomials, Trans. Amer. Math. Soc. 353 (2001), 3193–3207.

[25] Zuniga-Galindo W. A., Local zeta functions and Newton polyhedra, to appear in Nagoya Math. J.

[26] Zuniga-Galindo W.A., Local zeta function for non-degenerate homogeneous mappings, preprint 2003.

2000 Mathematics Subject Classification: Primary 11S40, 94A60; Secondary 11Y16, 14GG50.

Key words: Igusa’s local zeta function, polynomial time algorithms, one-way functions, linear feedback shift registers.

Received May 3, 2003; revised version received September 25, 2003. Published in Journal of Integer Sequences, October 20, 2003.

Return to Journal of Integer Sequences home page.