Polynomial random test for the equivalence problem of integers given by arithmetic circuits

K. Hägele^{1,3}, J. L. Montaña^{2,3}

March 18, 1997

Keywords: straight–line program, complexity, equivalence test, rational reconstruction.

Abstract

In [16], [9], [8], [7] a new approach for the problem of zero-dimensional polynomial system solving is presented, giving both refined lower bounds in terms of intrinsic geometric parameters and a new algorithm. This algorithm is based on effective manipulation of straight–line programs representing the mathematical structures appearing throughout the elimination process. Here we exhibit both theoretical and practical solutions for a central problem related with this algorithm, namely “how to decide equivalence of straight–line programs for integers”.

1 Introduction and summary of results

Consider the following problem:

Problem 1 (Effective Nullstellensatz) Given a sequence of polynomials f_{1}, …, f_{s} ∈ ZZ[X_{1}, …, X_{n}], decide whether the affine algebraic variety V (f_{1}, …, f_{s}) := {x ∈ C^{n} : f_{1}(x) = ⋯ = f_{s}(x) = 0} is empty or not.

In [16], [9], [8], [7] this decision problem is reduced by means of algebraic methods using effective manipulation of straight–line programs representing the mathematical structures appearing throughout the elimination process to the problem of deciding equivalence of straight–line programs for integers. Therefore the main goal of this paper is to establish all the necessary theoretical arguments as well as an effective algorithm for the solution of this equivalence problem.

A short historical survey on contributions to this subject should probably start with the results published by A. Schönhage [22]. Within the more general context of random access machines it is shown that the problem of deciding inequality of straight–line programs over ZZ is in the time complexity class NP (nondeterministic polynomial time algorithms).

The success of the Rabin-Miller primality test [18], [21] inspired several authors to apply similiar techniques in the context of straight–line programs. In [23] J. T. Schwartz gives probabilistic algorithms for the verification of polynomial identities, using a similar notion of straight-line program with variables over Q to represent the resultant as the algorithmic output of an elimination process performed on a system of polynomials. The algorithm supposed there depends directly on the degrees of the input polynomials and lacks a precise complexity analysis.

1: Departamento de Matemáticas, Estadística y Computación. Facultad de Ciencias.

Universidad de Cantabria. E-39071 Santander, Spain

2: Departamento de Matemática e Informática. Campus de Rosadía. Universidad Pública de Navarra.

E-31006 Pamplona, Spain

3: Research was partially supported by the following Spanish grants :

DGCYT PB92–0498–C02–01 and PB93–0472–C02–02

O. Ibarra and S. Moran [12] give a detailed analysis of the complexity of the equivalence problem for straight–line programs representing polynomials, yielding a probabilistic polynomial time algorithm as well as a separation from the case where the ground domain is finite and the problem becomes NP-hard. A good presentation of this type of techniques, resuming the above and own results [27] can be found in the book on polynomial computation [28] by R. Zippel.

A different approach based on a non-uniform complexity model using density arguments is used by J. Heintz and C. P. Schnorr in [11] to establish the existence of short correct test sequences for the equivalence problem for polynomials. In the present paper we adopt this technique to the case of straight–line programs over ZZ, showing the equivalence problem to be in the time-complexity class BP P, space-complexity class P/poly and give an effective randomized version of a BPP class algorithm, see Section 3.

To decide the zero-equivalence of a division-free straight–line program Γ over ZZ of length L, it is sufficient to perform the following algorithm, which has a bounded error probability < \frac{1}{e} on “NO”.

• input Γ,

• compute a set D_{L} of 4L random numbers in the range 1, …, 2^{2L},

• output “YES” iff Γ ≡ 0 (mod D_{L}), else output “NO”.

2 Straight–line programs

In this section we fix the notation, present some of the basic concepts of straight–line programs and give some elemental results on their properties. In our context it is sufficient to consider straight–line programs (short slp) over Q , ZZ, so we will restrict our attention to these cases and refer the reader to [16], [17] for a more generic exposition.

2.1 Basic definitions

Definition 1 Let D be a domain and T_{1}, …, T_{n} variables over D. A straight-line program Γ over D is a computation sequence of the form (x_{−n}, …, x_{L}), where:

• x_{−n} := T_{n}, …, x_{−1} := T_{1} are variables, x_{0} := 1 and

• x_{i} = x_{i_{1}} op x_{i_{2}}, for 1 ≤ i ≤ L, −n ≤ i_{1}, i_{2} < i and op ∈ {+, −, ∗, /}, where

• some nodes x_{L_{1}}, …, x_{L_{m}} are specified as output nodes.

The integer L is called the length of the straight–line program Γ.

If we restrict the admissible operations to {+, −, ∗}, the x_{i} will be polynomials of the ring D[T_{1}, …, T_{n}]. Γ is then called a division free straight–line program over D. If divisions are permitted, the x_{i} are rational functions of D(T_{1}, …, T_{n}).

A straight–line program Γ defined in this way is a very flexible structure, its representation capabilities ranging from integers to rather sophisticated constructions. Here some simple examples of algebraic structures which can be represented by straight–line programs:

• integers (taking D = ZZ and Γ typically division-free),

• polynomials in ZZ[X] (taking D = ZZ, T_{1} := X),

• vectors of rational functions in Q (T_{1}, …, T_{n}) (specifying several output nodes),

• matrices with entries in Q (T_{1}, …, T_{n}) etc.

2.1.1 Complexity measures for straight–line programs

Once an algebraic structure A is represented by a straight–line program Γ, it is an interesting question to ask about its complexity. First of all, we will have to fix an appropriate notion of complexity measure for straight–line programs. Note however, that there are two inherently different questions which should not be confused:

• Which is the complexity of this particular straight–line program Γ ?

(a question that can be answered by analyzing Γ), and

• which is the intrinsic complexity of the represented structure A ?

(which is far more difficult to answer).

The notion of non-scalar complexity was already considered by Ostrowski (in the context of addition chains, see [20]) and is based on the simple observation, that some operations in a ring D(T_{1}, …, T_{n}) or domain D imply more arithmetic work than others. For example, in the case of polynomials over ZZ[X], it is obviously easier to add two polynomials f, g than to multiply them.

To define the different measures for complexity used in the sequel, let us start with an observation: A straight–line program Γ as defined before is equivalent to a direct acyclic graph (short dag) representing the dependencies of the arithmetic operations of Γ. This can be seen as follows: The initial nodes x_{−n}, …, x_{0} correspond to the leaves of the graph. Now for each arithmetic node x_{i} = x_{i_{1}} op x_{i_{2}} (1 ≤ i ≤ L) of the straight–line program, a node is added to the graph, the vertices directed from the node (representing the result x_{i} of the operation op) to the two operands x_{i_{1}} and x_{i_{2}} (note that the operands might coinceed). In this way, every output node x_{L_{j}} (1 ≤ j ≤ m) has a well defined position in the graph, and it is possible to use the standard notion of depth of a node in a directed acyclic graph.

For the following notions let D = Q , R = Q (T_{1}, …, T_{n}), p ∈ R a polynomial, M a matrix containing entries M_{i,j} ∈ R and q ∈ Q a rational number.

• The depth l of a straight-line program Γ is the the natural number given as the maximum depth of any node of the directed acyclic graph corresponding to Γ.

• A non-scalar node of a straight-line program Γ over a domain D is a node x = y op z, where either y, z ∉ D and op = ∗ or z ∉ D and op = /. Similarly, a non-scalar node of a straight-line program Γ over Q is a node x = y op z with op ∈ {∗, /}.

• The non-scalar depth λ of a straight-line program Γ is the natural number given as the maximum number of non-scalar nodes on any path in the directed acyclic graph (V, E) corresponding to Γ.

• The total complexity or size L of a matrix M, a polynomial p or a rational number q is the natural number given as the minimum length of any straight-line program Γ calculating it.

• The non-scalar complexity or non scalar size Λ of a matrixM, a polynomial p or a rational number q is the natural number given as the minimum non-scalar depth of any straight-line program Γ calculating it.

• Finally, given an integer n ∈ ZZ, we refer by absolute height to | n | and by logarithmic height to ⌈log_{2} | n |⌉.

2.2 Reduction arguments

Restricting ourselves to the case where the domain D is Q in Definition 1, every straight-line program of the so defined form is a representation of an element f of Q(T_{1}, …, T_{n}). Each variable T_{i} can be assigned (independently from the other variables) a parameter q_{i} ∈ Q . Specializing a straight-line program Γ with n input variables T_{1}, …, T_{n} in a point (q_{1}, …, q_{n}) ∈ Q ^{n} will yield a straight-line program with parameters q_{1}, …, q_{n} over Q , which in turn can be evaluated and calculates the value of f(q_{1}, …, q_{n}). In this case we say that Γ has parameters q_{1}, …, q_{n}.

In the following we are interested in straight-line programs without input variables, i.e. straightline programs which, when evaluated, yield rational or integer number results. The following subsection shows that we can restrict our attention to straight-line programs for integers.

Remark: Adapting results from [24], [25], [5], [26] and more recently [6], [3], [4] to the context of straight–line programs one obtains an algorithm for the rational reconstruction of a rational number given by straight–line programs, permitting the recovery of a reduced representation of the rational number disregarding the binary size of the intermediate results of the straight–line programs involved. This allows us to use the following reduction arguments:

2.2.1 Reduction to ZZ

Lemma 2 Let Γ be a straight-line program with parameters q_{1}, …, q_{n} for the rational number q ∈ Q . We can compute in time linear in the length of Γ a division-free straight-line program Γ′ with at most 2n parameters over ZZ that outputs the numerator and denominator of the rational number q computed by Γ.

Proof.– By Definition 1 Γ is a sequence of the form (x_{−n}, …, x_{0}, x_{1}, …, x_{L}), where:

• x_{−n} := q_{n}, …, x_{−1} := q_{1} are parameters, x_{0} = 1, and

• x_{i} = x_{i_{1}} op x_{i_{2}}, for 1 ≤ i ≤ L, −1 ≤ i_{1}, i_{2} < i and op ∈ {+, −, ∗, /}, and

• q = x_{L}.

As x_{i} ∈ Q , we introduce two new nodes y_{i}, z_{i} for each of the nodes x_{i} appearing in Γ and start constructing Γ′. Γ′ will have input nodes x_{−2n}, …, x_{−1} = y_{−n}, …, y_{−1}, z_{−n}, …, z_{−1} with \frac{y_{i}}{z_{i}} = x_{i} for i = −n, …, −1. Now we follow the arithmetic operations appearing in the sequence Γ, keeping separately track of all changes of y_{i}, z_{i} in each step:

\frac{y_{i}}{z_{i}} = x_{i} = x_{i_{1}} op x_{i_{2}} = \frac{y_{i_{1}}}{z_{i_{1}}} op \frac{y_{i_{2}}}{z_{i_{2}}}

\begin{matrix}op & y_{i} & z_{i} \\ +, − & y_{i_{1}} ∗ z_{i_{2}} op y_{i_{2}} ∗ z_{i_{1}} & z_{i_{1}} ∗ z_{i_{2}} \\ * & y_{i_{1}} ∗ y_{i_{2}} & z_{i_{1}} ∗ z_{i_{2}} \\ / & y_{i_{1}} ∗ z_{i_{2}} & y_{i_{2}} ∗ z_{i_{1}} \end{matrix}

Observe that every non-scalar operation in Γ produces 2 operations in Γ′, whereas operations +, − cause 4 operations. So the total number of operations in Γ′ is bounded by 4 times the length of Γ. The output nodes y_{L} and z_{L} of Γ′ calculate the numerator and denominator of q.

We say that Γ computes or represents a given integer number n ∈ ZZ if n = x_{L} holds, i.e. the evaluation of Γ yields n. In this case we denote by n(Γ) the integer represented by the straight-line program Γ.

Lemma 3 For every n ∈ ZZ there exists a division-free straight-line program Γ with n(Γ) = n and L = ⌈log_{2}(n)⌉.

Proof.– This follows using the binary representation of n and applying to it evaluation by the ”Horner Schema” at the value 2 in order to construct Γ, see [15]. Given n and its binary representation a_{m}a_{m−1} … a_{0}, we define a polynomial f ∈ ZZ[x] as f(x) := (((a_{m} ∗ x + a_{m−1}) ∗ x + a_{m_{2}}) ∗ x … + a_{0}). The evaluation at x = 2 of the straight-line program associated with f yields n.

Lemma 4 Given a division-free straight-line program Γ of length L for an integer n with n parameters x_{1}, …, x_{n} in ZZ, it is possible to construct a division-free straight-line program Γ′ for n of length L′ ≤ L + 1 + ∑⌈log_{2}|x_{i}|⌉ with one single parameter 0.

Proof.– Apply Lemma 3 to construct a straight-line program Γ_{i} of length ⌈log_{2}|x_{i}|⌉ for every parameter x_{i} of Γ. Then replace the parameter 2 appearing in Γ_{i} by the sequence 1+1 and construct Γ′ from the Γ_{i}. This results in a straight-line program Γ′ of length L′ = L+1+∑_{i=1,...,n}⌈log_{2}|x_{i}|⌉.

Note that, given a straight-line program for a rational number q ∈ Q , by applying Lemma 2 (division-free straight-line programs over ZZ for numerator, denominator of q), reduction of the number of output nodes and Lemma 3 (reduction of parameters) it is possible to restrict one’s attention for the forthcoming theorems to division-free straight-line programs over ZZ with just one parameter 0.

2.2.2 Reduction to the boolean context

As the intention behind our work is to establish praticable algorithms, it is reasonable to check their complexity behaviour in a boolean (i.e. bit level) setting, as this is the only one valid at the hour of implementation, where the arithmetic circuit model does not reflect the crucial parameter space.

Given an arithmetic expression of the form x op y in ZZ_{m}, m ∈ ZZ with op in {+, −, ∗}, it is easy to construct a boolean network with 2⌈log_{2}m⌉ input gates and ⌈log_{2}m⌉ output gates, which simulates the arithmetic operation modulo m including all intermediate results in size (log_{2}m)^{O(1)}.

Definition 5 Given a natural number m ∈ IN and a straight-line program Γ which represents an integer n = n(Γ) ∈ ZZ. Then we denote by Γ_{m} the straight-line program in ZZ_{m} obtained from Γ by replacing in each step the operation applied by its equivalent instruction modulo m. Thus, x_{i} = x_{i_{1}} op x_{i_{2}} is replaced by x_{i} = x_{i_{1}} op x_{i_{2}} (mod m).

The straight-line program Γ_{m} of length L corresponds to a boolean network Γ_{B} of size O(L) · (log_{2}m)^{O(1)}, that calculates the output of Γ. Γ_{B} can be constructed by replacing the arithmetic instructions (mod m) in the nodes of Γ_{m} by the corresponding boolean networks of size ⌈log_{2}m⌉^{2}.

Lemma 6 The straight-line program Γ_{m} computes an integer residue n(Γ_{m}) in ZZ_{m} which equals to n (mod m).

Proof.– By induction on L and using the fact that the reduction modulo m is a homomorphism compatible with the arithmetic operators ’+, −, ∗’ in ZZ.

2.3 Rational Reconstruction

Here we give an algorithm for the rational reconstruction of a rational number given by straight– line programs for numerator, denominator which will allow the recovery of a reduced representation of the rational number disregarding the binary size of the intermediate results of the straight–line programs involved.

This practicable solution overcomes the problem of intermediate expression swell in the binary representation of the intermediate results of the rational numbers used during the computations. First, we recall a few basic algorithms and theorems, taken verbatim from [2] or [15].

Algorithm 7 (Euclid Extended) Given non-negative integers a and b, this algorithm determines (u, v, d) such that au + bv = d and d = gcd(a, b). We use auxiliary variables v_{1}, v_{3}, t_{1}, t_{3}.

1. [Initialize] Set u = 1, d = a. If b = 0 set v = 0 and terminate the algorithm,

otherwise set v_{1} = 0 and v_{3} = b.

2. [Finished?] If v_{3} = 0 then set v = (d − au)/b and terminate the algorithm.

3. [Euclidean step] Let q = d (div v_{3}) and t_{3} = d (mod v_{3}). Then set t_{1} = u − qv_{1}, u = v_{1}, d = v_{3}, v_{1} = t_{1}, v_{3} = t_{3} and goto step 2.

Complexity: For a, b < N for some bound N ∈ IN the running time will be at most O(log_{2}^{3} N). For further refinements and practical considerations such as multiprecision arithmetics see [2], [15].

Theorem 8 (Chinese Remainder Theorem) Let m_{1}, …, m_{k} be pairwise coprime integers, such that gcd(m_{i}, m_{j}) = 1 for i ≠ j. Then, for any integers x_{i} ∈ IN there exists an integer x ∈ IN, unique modulo ∏ m_{i}, such that

x ≡ x_{i} (mod m_{i}) for 1 ≤ i ≤ k.

The complexity is of order k times the complexity of the algorithm used for doing extended gcd calculation, for example O(k · log_{2}^{3} N) using the above algorithm.

Algorithm 9 (Inductive Chinese) Given pairwise coprime integers m_{1}, …, m_{k} and integers x_{i}, this algorithm finds an integer x such that x ≡ x_{i} (mod m_{i}) for all i.

1. [Initialize] Set i = 1, m = m_{1}, x = x_{1}.

2. [Finished?] If i = k output x and terminate the algorithm. Otherwise, set i = i + 1 and use the extended euclidean algorithm 7 to compute u, v such that um + vm_{i} = 1.

3. [Compute next x] Set x = umx_{i} + vm_{i}x, m = mm_{i}, x = x (mod m) and goto step 2.

Complexity: as before, see [2].

Using the above algorithm, it is easy to reconstruct the binary representation of an integer given by a straight–line program when given a bound on its size. Note though, that this method is of no practical value at all, if the bound on the binary size is very big. Therefore, the obvious approach for the rational reconstruction by separate recovery of the binary representation for both numerator and denominator from their straight–line programs is not feasable in general.

The following theorem, taken from a different context in [5] (where the exact ractional solutions of a regular system A · x = b of linear equations with integer coefficients are considered), will allow us to obtain an efficient algorithm for our purposes.

Theorem 10 (Dixon) Let s, h > 1 be integers and suppose that there exist integers f, g such that

gs ≡ f (mod h) and | f |, | g | ≤ λ\sqrt{h}

where λ = 0.618 … is a root of λ^{2} + λ − 1 = 0. Let w_{i}/v_{i} (i = 1, 2, …) be the convergents to the continued fraction for s/h and put u_{i} = v_{i}s − w_{i}h. If k is the least integer such that | u_{k} | < \sqrt{h}, then f/g = u_{k}/v_{k}.

The complexity of the algorithm depends on the underlying (modified) extended gcd algorithm used and the value of k. Proof: [5], [14] or [24], [26]. For the underlying properties of continued fractions see [14], [10] or [15].

The following theorem replaces the previously obtained bound h for | f |, | g | by a more suitable one:

Theorem 11 Given a positive rational number q = \frac{A}{B} with positive A, B, gcd(A, B) = 1 and a second representation \frac{U}{V} = \frac{A}{B} of q. Let p be a primenumber p > max(A, B) with gcd(p, U) = gcd(p, V) = 1. Let Ū, V̄ denote the images of U, V mod p^{2}. Then any solution of the congruence

a · V̄ − b · Ū ≡ 0 mod p^{2} with 0 ≤ a, b < p  (1)

will be a valid representation \frac{a}{b} of q.

Proof.– Consider the rational q = \frac{A}{B} and a second solution \frac{C}{D} of the above congruence (1). Let x ≡ Ū · V̄^{−1} mod p^{2}. Remark that by choice of p x is an invertible element in ZZ/p^{2}ZZ. Then A ≡ B · x mod p^{2} and C ≡ D · x mod p^{2}. So A · D · x ≡ B · C · x mod p^{2}, so x(AD − BC) ≡ 0 mod p^{2}. As A, D, B, C are each positive and smaller than p, any solution of (1) is of the form \frac{μ·A}{μ·B} with 1 ≤ μ ≤ [\frac{p}{max(A,B)}].

Application:

Given two positive integers U, V represented by a straight–line program Γ of length L and a bound η on the bit-size of the numerator/denominator of the reduced rational number \frac{A}{B} = \frac{U}{V} with gcd(A, b) = 1, η > max(A, B), we reconstruct A, B in binary representation from the straight–line program Γ in the following way:

• Find a primenumber p > η with gcd(U, p) = gcd(V, p) = 1. This can be easily achieved using modular evaluation of Γ.

• Determine Ū ≡ U mod p^{2} and V̄ ≡ V mod p^{2}.

• Find a solution a, b to the congruence (1): a · V̄ − b · Ū ≡ 0 mod p^{2} with a, b < p using the p-adic reconstruction method given by Theorem 10.

• Reduce a, b by gcd(a, b) (if neccessary) to obtain A, B.

Further refinements of this technique, applied in the context of polynomial factorization or polynomial gcd computations can be found in [24, 25, 6, 4] and the literature cited therein. For implementation purposes consider [3], which gives a suitably adapted version of Jebelean’s modified extended gcd algorithm ([13]), yielding a speedup of factor 2 over the standard algorithm cited here (Algorithm 7 + Lehmer/binary improvements).

2.4 Bounds and Probability

Lemma 12 For all straight-line programs Γ over ZZ the absolute height of the represented integer is bounded by the depth l of Γ: |n(Γ)| ≤ 2^{2^{l}}.

Proof.– By induction on l. For l = 0 the absolute height of the integer calculated by Γ is bounded by the absolute height of the input parameters, which is 0. A straight-line program of depth l + 1 has at least one node of depth l +1, which can use at most 2 input nodes of depth l whose absolute heights are bounded by 2^{2^{l−1}} by assumption. Using the operation ∗ to obtain maximum growth, it follows |n(Γ)| ≤ 2^{2^{l−1}} ∗ 2^{2^{l−1}} = 2^{2^{l}}.

Lemma 13 For all L ∈ IN the number of straight-line programs of length L is bounded by

3^{L}(\frac{1}{6}(L + 1)(L + 2)(2L + 3) − 1)

Proof.– As every x_{i} in the straight-line program Γ is the result of an operation op ∈ {+, −, ∗}, and there are L many x_{i}, we have 3^{L} possible combinations of operations. For every x_{i} we have the freedom to choose two inputs x_{i_{1}}, x_{i_{2}}, where i_{1}, i_{2} < i so we have i − 1 + 2 (recall the definition of a straight-line program, it starts with x_{−1} = 0, x_{0} = 1) possible candidates for each i_{1}, i_{2}, which multiplies to (i + 1)(i + 1). This sums to ∑_{i=1}^{L} (i + 1)^{2} = \frac{1}{6}(L + 1)(L + 2)(2L + 3) − 1.

This estimate will now be replaced by a far more coarse one, which has the advantage of being easier to handle in the oncoming calculations. To improve readability, let us write S(L) := ∑_{i=1}^{L}(i + 1)^{2}, F (L) := 3^{L}S(L) = 3^{L}(\frac{1}{6}(L + 1)(L + 2)(2L + 3) − 1).

Lemma 14 The number of straight-line programs of length L ∈ IN is bounded by 2^{4L}.

Proof.– F (1) = 12 < 16 = 2^{4}, F (2) = 9 · 13 < 2^{4·2}, F (3) = 27 · 29 < 2^{4·3}. For L > 3 by induction on L, using Lemma 15. Assume the statement holds for L − 1, so F (L − 1) ≤ 2^{4(L−1)}.

F (L) =  3 · 3^{L−1}S(L)  = 3 · 3^{L−1}S(L − 1) + 3 · 3^{L−1}(L + 1)^{2}
= 3 · F (L − 1) + 3 · 3^{L−1}(L + 1)^{2} ≤ 6 · F (L − 1)
≤  6 · 2^{4(L−1)}  < 2^{4} · 2^{4(L−1)} = 2^{4L}

Lemma 15

∀L ∈ IN, L > 3 : (L + 1)^{2} ≤ S(L − 1)

Proof.– For L = 4: 25 = 5^{2} < 2^{2} + 3^{2} + 4^{2} = 29. For L > 4 by induction on L:

L^{2} ≤ S(L − 2) = ∑_{i=2}^{L−1} i^{2} ⟺ L^{2} + 2L + 1 ≤ S(L − 2) + L^{2} ⟺ (L + 1)^{2} ≤ S(L − 1)

We are going to make use of a weak form of the prime number theorem, as found in [19].

Theorem 16 (Čebyšev) Let π(x) denote the function

π : IR^{+} → IN_{0} : π(x) = #{p ∈ IN, p prime, p ≤ x}

Then there exist positive constants c_{1}, c_{2} > 0 with c_{1} = 1 + O(1), such that

c_{1} \frac{x}{log x} ≤ π(x) ≤ c_{2} \frac{x}{log x}

Proof.– [19], Chapter III.4

The estimations in the following part characterize quite well the dependencies between the parameters L, the range of moduli R and the growth of the number of straight–line programs in function of L. A first step is to estimate the number of prime divisors for a given number. As these numbers will be chosen from a fixed range in a second step, we parametrize the binary size of the number by a polynomial p. To avoid purely technical problems, we define a simple condition which will ensure that all arithmetic operations performed to obtain the estimates are admissible.

Definition 17 For p ∈ ZZ[x] we define the (∗)-condition :

p is strictly positive and p(L) ≥ 2L ∀L ∈ IN (*)

As the estimations are a bit coarse, it is necessary to assure that they are valid for all natural numbers greater than a fixed small starting number, which is exposed in the following Lemma:

Lemma 18 Let f(x) := \frac{2^{p(x)}}{p(x)} − 2^{x}. For all p ∈ ZZ[x] satisfying the (∗) condition exists L_{0} ∈ IN such that for all L ∈ IN with L > L_{0} f(L) > 0. Furthermore, for p ∈ ZZ[x] satisfying

• p(L) = 2L ∀L ∈ IN holds L_{0} = 2

• p(L) ≥ 4L ∀L ∈ IN holds L_{0} = 0

Proof.– \frac{2^{p(L)}}{p(L)} − 2^{L} > 0 ⟺ 2^{p(L)} > p(L) · 2^{L} ⟺ p(L) − L > log_{2}p(L). This holds for p(L) = 2L for L > 2, for p(L) ≥ 4L for L > 0.

Now we can estimate the number of moduli within a fixed range which are useful for a simple non-zero congruence test and the probability that a number chosen at random is useful.

Lemma 19 Given an integer number k ∈ ZZ of bounded size 1 ≤ |k| ≤ 2^{2^{L}}, let p ∈ ZZ[x] satisfy the (∗) condition and define the range of moduli R := {r ∈ IN : 1 ≤ r ≤ 2^{p(L)}}. Then for all L ∈ IN starting from L > L_{0} (L_{0} as given in Lemma 18) the number of moduli r ∈ R for which k ≢ 0 (mod r) is greater than \frac{2^{p(L)}}{p(L)} − 2^{L}. Furthermore, the probability for a random r ∈ R that k ≢ 0 (mod r) holds, is ≥ \frac{1}{2p(L)}.

Proof.– By Čebyšev’s prime number theorem, the number of primes smaller than 2^{p(L)} is greater than \frac{2^{p(L)}}{p(L)} . Since the number of prime divisors of k is at most log_{2} k ≤ 2^{L}, there are at least

\frac{2^{p(L)}}{p(L)} − 2^{L} prime numbers smaller than 2^{p(L)} which do not divide k. Since the cardinality of R is

2^{p(L)}, the probability that k ≢ 0 (mod r) is ≥ (\frac{2^{p(L)}}{p(L)} − 2^{L}) · (\frac{1}{2^{p(L)}} ) = \frac{1}{p(L)} − \frac{1}{2^{p(L)−L}} ≥ \frac{1}{p(L)} − \frac{1}{2^{p(L)}} ≥ \frac{1}{p(L)} − \frac{1}{2p(L)} = \frac{1}{2p(L)}.

Corollary 20 As a direct practical application of Lemma 19 we conclude that for p(L) = 2L (thus the range of moduli becomes R := {r ∈ IN : 1 ≤ r ≤ 2^{2L}}), when given a natural number k ∈ ZZ with 1 ≤ |k| ≤ 2^{2^{L}}, L > 2, for a randomly chosen r ∈ R the probability that k ≢ 0 (mod r) is ≥ \frac{1}{4L}.

2.5 Complexity classes

Here we give a short description for each of the two complexity classes involved, a rather abstract definition together with a more application-oriented interpretation of its significance in our context. Note that they are based on different complexity measures (time/space).

Problem 2 (Decision Problem) Given a set A, and a property P which induces an equivalence relation on A, decide, whether x ∈ A has property P or not.

2.5.1 BPP

The class of Bounded Error Probabilistic Polynomial Time Algorithms (with uniform complexity measure time): Algorithms of polynomial running time using probabilistic methods and information on the actual input to choose a criterion by which to decide whether x has the property P or not. If the answer given by the algorithm is ”Yes”, it is always correct, and when the answer is ”No”, the error probability is bounded by \frac{1}{2}.

In practice, this type of algorithm is quite common, a well-known example is the Rabin-Miller Primality Test. The main idea is to iterate several tests on the same input, each time using a random number depending on the size of the input to perform certain congruence tests. As the probability of error is bounded by \frac{1}{2} for each test, a small number of iterations is sufficient to achieve a practical error bound which is smaller than the fault tolerance of the computer used to perform the tests.

Observe that, using Corollary 20, it is easy to derive a BPP-complexity class zero equivalence test for integers given by straight–line programs.

2.5.2 P/poly

The class P/poly (with non-uniform complexity measure space = boolean network size): The complexity class of algorithms of Polynomial size, which, once given a polynomial size advice (depending only on the the class of the input), will accept deterministically exactly those inputs possessing property P. The answer given by a P/poly algorithm with a correct advice is always correct, and the advice will be valid for the whole set A, independent from the actual input of the algorithm.

The problem here becomes how to find advice, as in most cases an exhaustive search for such an advice or the verification of suitability of a candidate for a valid advice is prohibitive (exponential time) and when using some function to construct a likely candidate the probability of error given for a P/poly test depends on that function.

Note, that from a theoretical point of view, once one has a correct advice (and happens to know this), the advice will be valid for testing the whole set A, and there is no need to iterate the algorithm with different choices.

In our case, a random number generator is used to construct a candidate, and density arguments on the amount of bad versus good candidates for advice are used to estimate this error probability. If the error probability is not sufficiently small, iterations are used to lower it as desired.

2.6 Correct test sequences

The following concept of correct test sequences for straight–line programs was introduced in [11] for polynomials and has been translated to the context of straight-line programs over ZZ, Q . We establish the existence of a polynomial size advice in the form of a correct test sequence for the equivalence problem for integers given by straight–line programs as well as a density theorem for the quantity of correct test sequences.

An import difference lies in the idea, that there exist decision criteria which hold globally for a whole class of inputs, and do not depend on further information taken from the particular input the algorithm is run on.

Definition 21 Given F a subset of ZZ and given a finite subset M = {m_{1}, …, m_{t}} of ZZ, we say that M is a correct test sequence for F if for any n ∈ F the following implication holds:

n ≡ 0 (mod M) ⇒ n = 0,

where n ≡ 0 (mod M) means that n ≡ 0 (mod m_{i}) for 1 ≤ i ≤ t. We say that a correct test sequence M is bounded by a polynomial f ∈ ZZ (or short f-bounded) if the logarithmic height of all m ∈ M is bounded by f.

Lemma 22 Let F_{L} denote the set of all integers having a straight-line program of length L. Let p ∈ ZZ[x] satisfy the conditions of Lemma 18 and q ∈ ZZ[x] a polynomial with q(L) > 8Lp(L) ∀L ∈ IN. Then the quantity of p(L)-bounded correct test sequences D_{L} of cardinality q(L) is at least

2^{p(L)q(L)}(1 − 2^{− \frac{q(L)}{2p(L)} +4L}).

Proof.– By definition, for F = F_{L}, M = {1, …, 2^{p(L)}}, each subset D_{L} of q(L) random numbers in the range 1..2^{p(L)} satisfying the conditions of Definition 21 for all Γ of length L is a correct test sequence for the set F_{L}. Thus, it is enough to calculate a lower bound for the number of subsets D_{L} that have this property. The total number of subsets D_{L} of q(L) random numbers in the range 1..2^{p(L)} is 2^{p(L)q(L)}. According to Lemma 19, for one random r ∈ R the probability that k ≡ 0 (mod r) is ≤ 1 − \frac{1}{2p(L)}. So, for L > L_{0} the probability, that one random set of q(L) integers ∈ R is not a correct test sequence is bounded by

(1 − \frac{1}{2p(L)})^{q(L)} = ((1 − \frac{1}{2p(L)})^{2p(L)})^{q(L)} < (\frac{1}{2})^{\frac{q(L)}{2p(L)}} = 2^{− \frac{q(L)}{2p(L)}} .

So the number of distinct subsets D_{L} of q(L) random integers in the range 1, …, 2^{p(L)} failing to be

a correct test sequence for at least one Γ of size L is bounded by 2^{p(L)q(L)− \frac{q(L)}{2p(L)}} . Since by Lemma 14 the cardinality of F_{L}, i.e. the set of all possible straight-line programs of size L is < 2^{4L}, it follows that the total number of subsets D_{L} not giving a correct test sequence for all Γ ∈ F_{L} for L > L_{0} is bounded by 2^{− \frac{q(L)}{2p(L)} +4L}. So, finally, the number of correct test sequences for F_{L} is bounded from below by the following quantity:

2^{p(L)q(L)}(1 − 2^{− \frac{q(L)}{2p(L)} +4L)}).

The following two corollaries state the size of the boolean network encoding the obtained correct test sequences.

Corollary 23 As each of the q(L) moduli in D_{L} has binary size p(L), any correct test sequence D_{L} as appearing in Lemma 22 [Bhas a binary codification of size O(q(L) · p(L)).

Corollary 24 For all polynomials p ∈ ZZ[x] satisfying the (∗) condition, q ∈ ZZ[x] with q(L) > 8Lp(L) ∀L ∈ IN, there exists L_{0} as in Lemma 18 such that for all L > L_{0} every p(L)-bounded correct test sequence D_{L} of cardinality q(L) has a binary codification of size O(q(L) · p(L)).

3 Results and Applications

3.1 Space complexity class P/poly

The main result of this paper is the following theorem, establishing the existence of a non-uniform P/poly class algorithm for the zero-equivalence test for division-free straight-line programs over ZZ. As the complexity measure for the P/poly complexity class is space, we will have to discuss the existence of the algorithm in terms of boolean networks.

Theorem 25 For all L ∈ IN exists a boolean network C_{L} whose size and input parameters are polynomial in L, which accepts exactly the set of all division free straight-line programs over ZZ of length L encoding the integer 0. The algorithm represented by C_{L} uses as advice a correct test sequence D_{L} which has a boolean network Q of size polynomial in L. Moreover, for every fixed size L, the logarithmic height of all intermediate results in C_{L} is bounded polynomially in L.

Proof.– It is enough to consider, for every fixed length L, a correct test sequence D_{L} given by Lemma 22 and its binary codification Q of polynomial size O(p(L) · q(L)) as given by Lemma 23 and the arithmetic network C_{L} which simulates the following algorithm:

• input Γ with size(Γ) ≤ L,

• choose a correct test sequence D_{L} of q(L) integers according to Lemma 22,

• accept Γ as a representation of 0 iff n(Γ) ≡ 0 (mod D_{L}).

Since D_{L} has polynomial cardinality and each m ∈ D_{L} has polynomial logarithmic height the theorem follows.

3.2 Time complexity class BPP

As a practical application of Corollary 20 it follows that the zero-equivalence problem for straightline programs over ZZ is bounded error probabilistically decidable in polynomial time, i. e., is in the uniform complexity class BPP (see [1, Chapter 6] for a detailed definition of this complexity class). For a similar result on straight-line programs representing polynomials refer to [12].

Theorem 26 The zero-equivalence problem for division free straight-line programs representing integer numbers is bounded error probabilistically decidable in polynomial time.

Proof.– Let Γ be a division free straight-line program of length L over ZZ. The following algorithm probabilistically decides if Γ computes the integer 0.

• input Γ,

• compute a set D_{L} of 4L random numbers in the range 1, …, 2^{2L},

• output “YES” iff Γ ≡ 0 (mod D_{L}), else output “NO”.

Observe that when the answer is NO it is certain that n(Γ) is not zero. Hence the probability of error becomes when the answer is YES and n(Γ) ≠ 0. Apply Lemma 19 and Corollary 20 to see that the probability of error is bounded by (1 − \frac{1}{4L})^{4L} < \frac{1}{e}. Since all the computations in the algorithm are modulo r the theorem follows.

Corollary 27 As a direct consequence of Theorem 26 and Lemma 2 we conclude that the zeroequivalence problem for division free straight-line programs representing rational numbers is bounded error probabilistically decidable in polynomial time, using the reduction arguments in Subsection 2.2.

References

[1] J. L. Balcázar, J. Díaz, and J. Gabarró. Structural complexity I . EATCS 11. Springer, 1988.

[2] H. Cohen. A Course in Computational Algebraic Number Theory. Springer, 1993.

[3] G. E. Collins and M. J. Encarnación. Efficient Rational Number Reconstruction. Journal of Symbolic Computation, vol. 20 (3):pp. 287–297, 1995.

[4] G. E. Collins and M. J. Encarnación. Improved Techniques for Factoring Univariate Polynomials. Journal of Symbolic Computation, vol. 21 (3):pp. 313–??, 1996.

[5] J. Dixon. Exact solution of linear equations using p-adic expansions. Numer. Math., vol. 40:pp. 137– 141, 1982.

[6] M. J. Encarnación. On a modular algorithm for computing GCDs of polynomials over algebraic number fields. In ACM, ed., ISSAC’94. Proceedings of the International Symposium on Symbolic and Algebraic Computation. ACM Press, 1994.

[7] M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower Bounds for Diophantine Approximation. In Proceedings of MEGA’96 . 1996.

[8] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight–Line Programs In Geometric Elimination Theory. to appear in J. of Pure and App. Algebra, 1995.

[9] M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. When Polynomial Equation Systems can be solved fast ? In G.Cohen, H. Giusti, and T. Mora, eds., Applied Algebra, Algebraic Algorithms and Error Corecting Codes, Proc. AAECC-11 , vol. 948 of LNCS, pp. 205–231. Springer, 1995.

[10] Hardy and Wright. An Introduction to the Theory of Numbers. Clarendon Press, 1979.

[11] J. Heintz and C. P. Schnorr. Testing Polynomials which are easy to compute. In Logic and Algorithmic, vol. 30 of Monographie de l’Enseignement Mathématique, pp. 237–254. 1982.

[12] O. H. Ibarra and S. Moran. Equivalence of Straight-line Programs. Journal of the ACM , vol. 30:pp. 217–228, 1983.

[13] T. Jebelean. Improving the Multiprecision Euclidean Algorithm. Lecture Notes in Computer Science, vol. 722:pp. 45–??, 1993.

[14] A. Y. Khinchin. Continued Fractions. Translated from Russian by P. Wynn, P. Noordhoff Ltd., Grooningen, 1963. Also by H. Eagle, The University of Chicago Press, 1964 . The University of Chicago Press, 1935.

[15] D. E. Knuth. The Art of Computer Programming: Semi-numerical Algorithms, vol. 2. Addison-Wesley, 1981.

[16] T. Krick and L. M. Pardo. Une approche informatique pour l’ approximation diophantienne. C. R. Acad. Sci. Paris, vol. 318 (1):pp. 407–412, 1994.

[17] T. Krick and L. M. Pardo. A Computational Method for Diophantine Approximation. In L. González-Vega and T. Recio, eds., Algorithms in Algebraic Geometry and Applications. Proc. MEGA’94 , vol. 143 of Progress in Mathematics, pp. 193–254. Birkhäuser Verlag, 1996.

[18] G. L. Miller. Riemann’s hypothesis and tests for primality. Jrnl. Comp. Sys. Sci., vol. 13:pp. 300–317, 1976.

[19] W. Narkiewiecz. Number Theory. World Scientific Publishing, 1983.

[20] A. M. Ostrowski. On two problems in abstract algebra connected with Horner’s rule. In Studies in Math. and Mech. presented to Richard von Mises, pp. 40–48. Academic Press, 1954.

[21] M. O. Rabin. A Probabilistic Algorithm for Testing Primality. Journal of Number Theory, vol. 12, 1980.

[22] A. Schönhage. On the power of random access machines. In H. A. Maurer, ed., Proceedings of the 6th Colloquium on Automata, Languages and Programming, vol. 71 of LNCS, pp. 520–529. Springer, July 1979.

[23] J. T. Schwartz. Probabilistic algorithms for verification of polynomial identities. In ISSAC ’79: Proc. Int’l. Symp. on Symbolic and Algebraic Computation, Lecture Notes in Computer Science, Vol. 72. Springer-Verlag, 1979.

[24] P. Wang. A p-adic algorithm for univariate partial fractions. In P. Wang, ed., SYMSAC ’81: Proceedings of the 1981 ACM Symposium on Symbolic and Algebraic Computation, pp. 212–217. Association for Computing Machinery, 1981.

[25] P. Wang. Early detection of true factors in univariate polynomial factorization. In Proceedings of the 1983 European Conference on Computer Algebra, vol. 722, pp. 225–235. Springer, 1983.

[26] P. Wang, M. Guy, and J. H. Davenport. p-adic reconstruction of rational numbers. SIGSAM Bulletin, vol. 16 (2), 1982.

[27] R. Zippel. Interpolating Polynomials from their Values. J. Symbol. Comput., vol. 9:pp. 147–175, 1990.

[28] R. Zippel. Effective Polynomial Computation. ECS 241. Kluwer Academic Publishers, 1993.