BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1326
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: A New Modular Interpolation Algorithm for Factoring Multivariate 
        Polynomials
AUTHOR:: Rubinfeld, Ronitt
AUTHOR:: Zippel, Richard 
DATE:: January 1993
PAGES:: 16
ABSTRACT::
In this paper, we present a technique that uses a new interpolation scheme to 
reconstruct a multivariate polynomial factorization from a number of 
univariate factorizations. Whereas other interpolation algorithms for 
polynomial factorization depend on various extensions of the Hilbert 
irreducibility theorem, our approach is the first to depend only upon the 
classical formulation. The key to our technique is the interpolation scheme 
for multivalued black boxes originally developed by Ar et. al. [1]. We feel 
that this combination of the classical Hilbert irreducibility theorem and 
multivalued black boxes provides a particularly simple and intuitive approach 
to polynomial factorization.
END:: CORNELLCS//TR93-1326
BODY::
A New Modular Interpolation Algorithm for
Factoring Multivariate Polynomials
Ronitt Rubinfeld
Richard Zippel
TR 93-1326
January 1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
A New Modular Interpolation Algoritlim for
Factoring Multivariate Polynomials
Ronitt Rubinfeld and Richard Zippel
Deptment of Computer Science
Cornell University
Ithaca, NY 14853
January 28,1993
Abstract
In this paper we present a technique that uses a new interpolation scheme to recon-
struct a multivariate polynomial factorization from a number of univariate factoriza-
tions. Whereas other interpolation algorithms for polynomial factorization depend on
various extensions of the Hilbert irreducibility theorem, our approach is the first to de-
pend only upon the classical formulation, The key to our technique is the interpolation
scheme for multivalued black boxes originally developed by Ar et. al. [1]. We feel that
this combination of the classical Hilbert irreducibility theorem and multivalued black
boxes provides a particularly simple and intuitive approach to polynomial factorization.
Various versions of the problem of factoring polynomials, that is, writing a polynomial
as the product of polynornials of smaller degree, have been studied for hundreds of years. In
its earliest form it involved obtaining the zeroes of low degree univariate polynomials and
was the subject of public competitions in the 15th and 16th centuries. In this case, the goal
was to find linear factors with coefficients in a radical extension of the rational numbers, Q.
The modern problem was first solved by Kronecker [25] and can be stated as follows.
Let L be a field and P(X, ..... . , Yn) a polynomial with coefficients in L. P is said to be
irreducible if there do not exist two polynomials Qi, Q2 E L[x,Y1,... ,Yn], neither of which
are elements of L, such that P = Q2. A compiete factorization of P is a set of distinct,
irreducible polynomials P1,... , Pk such that
P(x,Yl,...,Yn)=Piei,P2e2,,Pkek.			(1)
The e2 are greater than or equal to 1 and not all of the Pj need have positive degree in X
and the Yj.
When P is a univariate polynomial, i.e., n = 0, the following is known: If the coefficient
field L is either a finite field, tKp or F??, or the rational integers Q then P can be factored
in polynomial time. In the finite field case any of a number of algorithms can be used
[3--H5, 18, 19,29]. When L is equal to Q various lattice reduction techniques can be used to
factor P in polynomial time [26,27,31].
There are two main approaches to the multivariate factorization problem, the Hensel
(or Newton) approach and the modular interpolation approach. Both approaches reduce
the multivariate problem to a univariate or bivariate problem.
Intuitively the Hensel approach proceeds as follows: First, choose a random n-tuple
,y?) E R? and factor the univariate polynomial P(X,y1,. . . ,y?). This is viewed
as factorization of P(X,Y1,. . .,Yn) modulo the ideal m = (Y1 --H I",.. ,Yn --H Un) Using a
constructive version of Hensel's lemma (or equivalently Newton's method) this factorization
is lifted to one modulo m2, m3 and so on, until we have a factorization modulo mD, where
D is larger than the degree of any variable in P(X, ...... , Yn). This must then be a true
factorization of P(X,Y1,... , Yn) [21,35,36,38].
The modular interpolation approach again chooses random values for the variables
..... . , Yn, but instead of using a single factorization of P, it uses interpolation techniques
to combine many univariate factorizations to produce a multivariate factorization [22].
As described, both approaches reduce multivariate factorization to univariate factor-
ization. The Hilbert irreducibility theorem guarantees that for most random choices the
univariate factorizations have the same number of factors as the multivariate factorizations
and thus the same structure. For technical reasons, the authors of [20, 22] use a different
version of the Hilbert irreducibility theorem that is only valid for reductions to bivariate
factorizations. Their algorithms thus require an additional technique to reduce the required
bivariate factorizations to univariate factorizations.
Our technique overcomes these earlier technical problems, allows us to directly reduce
multivariate factorization to univariate factorization and uses the classical version of the
Hilbert irreducibility theorem. Briefly, we present a new, simple modular scheme for fac-
toring a polynomial P(X,Y1,... , Yn) with integer coefficients:
P(x,Yj,...,Yn)=Pf1(x,Y1,...,Ym)P2e2(x,Y1,...,Yn)???Pk?k(x,Y1,...,Yn)
The classical form of the Hilbert irreducibility theorem states that for almost all choices
of integers ?i,..., ??, the factorization of P(X,vi,... , ??) has the same structure as the
factorization of P(X,Y1,... , Yn). Our first step is to produce a black box ?p1Pk that
on input of ?i,..., y? returns the set of factors of P(X,y1,... , y?). However, for different
inputs, the factor corresponding to Pj may be returned in different positions. Nonetheless,
using the techniques of Ar et. al. [1] we demonstrate how to construct k black boxes, each
representing an individual factor Pj of P. These black boxes can then be interpolated using
sparse polynomial interpolations schemes [2,6,37,39].
The Hilbert irreducibility theorem is described in Section 1. In Section 2 we present
the basic factoring algorithm. It relies on black box interpolation techniques discussed in
Section 3 which in turn rely on well known Hensel techniques for solving equations that are
described in Appendix B.
1			Hilbert Irreducibility Theorem
We make strong use of the Hilbert irreducibility theorem, which says that for almost all
= ....... , y?), where Ui E ?, the univariate polynomial P(X,y1,... , y?) has the same
2
number of irreducible factors as the multivariate polynomial P(X,Y1,... , Yn), and thus the
degree distributions are the same.
We call an n-tuple yi,..., y? Ililbertian for P if the factorization of P(X, yi,... ,
has no more factors than that of P(X,Y1,... , Yn). We need to quantify how often the
factorization of P(X,y1,. . . ,yn) corresponds to that of P(X,Y1, . . . ,Yn). Let the number
of non-Hilbertian n-tuples,(yi,... , y?) with 0 < y? < N, for an irreducible polynomial of
degree d be denoted by R(d, n, N). More generally, the number of non-Hilbertian n-tuples
,y?) for a polynomial P, R(d,n,N) is no greater than kR(d,n,N), where k is the
number of irreducible factors of P.
The classical Hilbert irreducibility theorem asserts that R(N)/N? 0, as N goes to
infinity [9--H14,17,23,24,30,33,34]. The sharpest result is due to Cohen [7]:
n, N) < c(d) N??21 log N,			(2)
where c depends only on the degree of the irreducible polynomial. The distribution of
non-Hilbertian points is invariant under translations of the Yj, so we have the following
proposition.
Proposition 1 Let P(X,Y1, . . . ,Yn) be a polynomial over? and assume that the degree of
X in P is less than D. Let a?,. . . ,a? be any elements of Z. For sufficiently large N, the
number of n-tuples ....... , y?) E Z?, a? < y? < N + a?, for which P(X,y1,.. , yn) factors
differently from P(X,Y1,... , Yn) is less than
R(d, n, N) <c(d) D N??22 log N.
As a consequence of this use of the Hilbert irreducibility theorem, the values used in the
interpolation must be chosen randomly from a large enough domain.
Extensive experience has shown that n-tuples at which an irreducible polynomial is
reducible are exceedingly rare. We thus believe the following conjecture to be true. This
is reinforced by the extensive use of the classical version of Hilbert irreducibility theorem
to factor multivariate polynomials over Q in computer algebra systems, e.g., MACSYMA,
REDUCE and AXIOM.
Conjecture I In the previous proposition, there exists an absolute constants cl, c2 such
that c(d) < c1dc2, i.e.
R(d, n, N) < cidc2 D N??21 log N.
Using this original form of the Hilbert irreducibility theorem and the new techniques
presented in this paper we derive a simple multivariate polynomial factorization algorithm.
Assuming Conjecture 1, our algorithm runs in random polynomial time.
2 Factoring Multivariate Polynomials
Assume that we want to factor a polynomial P(X,Y1,... , Yn) with coefficients in ? For
clarity, assume also that the polynomial is square free and monic as a polynomial in X.
3
Neither of these assumptions affect the complexity or correctness of the algorithm. The
extension to non-square free polynomials is immediate. The extension to non-monic poly-
nomials is less obvious and the details are outlined in Appendix C.
Assume the factorization of P(X,Y1,... ,Yn) is
P(X,Yl,...,Yn)=P1(X,Y1,...,Yn)?P2(X,Y1,...,Yn)?''Pk(X,Y1,...,Yn)
For any Hilbertian point j= (yi,.. ,y?) the factorization of P(X,?1, . . . ,y?) will be
P(X,y1,... = Pjy(X) P2?X). Pk$X),
where P,?(X)=P1(X,u1,... ,un) is a univariate polynomial in X.
We construct a black box ??i?k that represents the setof multivariate polynomials
....... , PkY When given a Hilbertian point (yi, . ,y?) as input, the black box factors the
univariate polynomial P(X,ui,.. , y?) and returns the unordered setof factors
,un) = [P1$x),P2?x),. . . ,Pkjj(X)1.
Such a black box is called a polynomial multivalued black box, since it returns several un-
ordered values on each call and each of these values is a univariate polynomial. By repeatedly
querying this black box, we will recover the factors of P: P1,... , Pk. This process is called
interpolating the black box. Thus, we have reduced the multivariate factorization prob-
lem to factoring univariate polynomials and interpolating "polynomial multivalued black
boxes."
The black boxes we produce differ slightly from those studied by Ar et. al. [1], but
in Section 3 we demonstrate how their techniques can be adapted to recover P1,... , Pk in
random polynomial time. Interpolating the black boxes requires factoring special bivariate
polynomials, Q(Z, e), where we know the complete factorization of Q(Z, ()), for some integer
0. The bivariate polynomials Q(Z, e) have the special property that they have only linear
factors of the form Z --H q1(?) where the q?'s are polynomials in e. With this additional
information, factoring is not needed--Hinstead, much faster, well known Hensel techniques
suffice (Appendix B).
The complete time complexity and probability of success of the factoring algorithm is
given at the end of Section 3.3.
3 Interpolation Schemes
The simplest form of black box is one that represents a single polynomial P(Y1,... , Yn)
with coefficients in Q. We use the notation ?p to indicate such a black box. On input
of Ui,..?, Un E ?, such a black box returns an element of Q, P(ui,... , y?). Given such a
black box it is not difficult to determine P in time polynomial in the number of non-zero
monomials in P [2,6,37,39]. Extensions to black boxes representing rational functions are
given in [22]. We note that the original randomized interpolation algorithm of [37] can use
uniformly distributed evaluation points.
In [1], the concept of a black box is extended to a multivalued black box?p1Pk On
input ?? a multivariate black box returns an unordered set of values fP1(y?,... , Pk(U??,
4
where the Pj(Y) are distinct polynomials. Given a collection oft different k-tuples returned
by such a black box,
?P1(y?),... ,Pk(y?)Y,fP1(y?),...,Pk(yTh)Y,...,?P1(y?),...,Pk(y?)Y,
we want to determine the polynomials P1(Y),... , Pk(Y) We call this process ?ntevpolating
the biack box. Since the values are unordered, we don't know which values in each list cor-
respond with which Pj. To find the correspondence by brute force requires time exponential
in t, thus the standard interpolation techniques for black boxes are inadequate.
Denote the coefficient of X? in the polynomial Pi(X,Y?,... , Yn) by aq, which is a
polynomial in ..... . , Yn. Our approach is to reduce interpolation of the black box ?p1Pk
to independent interpolations of the black boxes v/6a('?)ak,, 0 < j < d, where d bounds
the degree of X in the Pj. On input of integers u = ,un), ?a?i?),..,a?, returns the
unordered set of values aij(u?,... , a?j(y?, which are elements of Q. Each of the black
boxes ??a?1?,?'?kj are then converted into several single valued black boxes ??/6a?,--Hin other
words, the order of the values returned by #a?'?)ak, is determined. This is accomplished
using intermediate univariate multivalued black boxes of the form ???? where the q, are
univariate polynomials in a new variable 0-.
In Section 3.1, we use the techniques of [1] to reduce the univariate case to the problem
of refining linear factors of a bivariate polynomial. The case of ?valued black boxes repre-
senting multivariate polynomials is discussed in Section 3.2 and is reduced to the univariate
problem. In Section 3.3, we deal with multivalued black boxes whose values are polynomi-
als. This is agaln reduced to the univariate case discussed in Section 3.1. Eurthermore, in
all of the following sections calls will be made on randomly distributed points.
3.1 Black Boxes of Univariate Polynomials
Let q1(?),... , q?(?) be distinct univariate polynomials of degree no more than D. Given
a multivalued black box of univariate polynomials ????, we provide a technique for
explicitly determining the q, `s.
The symmetric functions in the qi(O),... , q?(O) are defined to be
ai(0) =qi(O)+q2(O)+...+qk(O),
02(O) = qi(O)q?(O) + qi(O)q?(O) + ... + q?--Hi(0)q?(0),
0k(0) =qi(O)q?(O).. qk(o).
Notice that the symmetric functions can be computed given the values ?qi(O),... ,
without knowing which values correspond with which q?. Therefore, we can construct k
different single valued black boxes ?g?? one for each symmetric function. On input of 0, ??
returns the value oj (0). For each black box ?g?, the univariate polynomial 0j (?) is of degree
no more than iD and can be determined by Lagrangian interpolation in O((iD)2) time and
iD queries. This approach places no constraints on the points used in the interpolation
process.
5
Using these univariate values as coefficients we can explicitly construct the polynomial
Q(Z, e) = Zk --H ?1(o)zk--H1 + a2(o)zk?2 + ... + (?1)kJk(o),
which by construction has only linear factors:
Q(Z,O-) =			--H q1(?))(Z --H q?(O) .			--H
The zeroes of Q(Z,O) are qi(()),...,q?(0), which are the values of?q1??(()) This addi-
tional information allows us to use the Hensel techniques of Section B to quickly find the
factorization of Q(Z, 0-) and thus determine the q?(O-).
Proposition 2 Let q?...., q? be pol?nomials in ?[O-] and the degree of q? is bounded b? D.
Then all of the q?'s can be interpolated from a multivalued black box ??q? using kD + 1
evaluations and time O(k3D2). Furthermore, the evaluations can be made at arbitrar?
points.
Note that Lagrangian interpolation does not depend upon the values chosen for 0. Thus
we can use the same 0's when we need to interpolate several different black boxes at the
same time.
3.2 Black Boxes of Multivariate Polynomials
Given a multivalued black box of multivariate polynomials ?????Pk' we provide a technique
for explicitly determining the p,'s. The approach we use converts the multivalued black box
? into an ordered multivalued black box ??` where the values are always returned in the
same order. Standard interpolation techniques can then be used to recover the ?j'5.
This method is a modification of the one given in Section 3 of [1]. The problem in [1] uses
black boxes that with each call only return the value of an arbitrary Pj. The factorization
problem yields black boxes that return the values of all of the P2 at each call. This additional
information allows our technique to work over arbitrary fields, while that of [1] is only valid
over finite fields.
The concept of a reference point is used to impose an ordering on the values returned
by the v?p1Pk We say that y = (ui?. ,y?) is a reference point if, for all i and j,
pi(V? # p?(y?. Given the range from which the Ui'? are chosen (the interval [0, Np], where
Np is defined in Proposition 4), it can be shown that significantly more than half of the
are reference points. Thus a reference point can be found by choosing a random point
and verifying that it is a reference point. For each black box ??, we need only choose one
reference point. Given the reference point yffl we compute the ordered sequence of reference
values
(3)
Define the multivalued black box 9r,?(0), which on input 0 calls the black box v66(u+ 0
--H y?) and returns v?'5 results. Fixing x, ?, ?:,? is a black box of univariate polynomials
in 0 of degree nD. Applying the techniques described in Section 3.1 to 9:?,', we explicitly
get the unordered set of univariate polynomials
6
By substituting e = 0 into each of the polynomials in Sx?, and comparing with the reference
values (3), we can determine the correspondence between polynomials in Sz and Pi,? ,Pk
By substituting e = 1 into the polynomials in Sz, we can now determine pi(x?,... ,Pk(x?.
This technique allows us to create a set of single valued black boxes (for multivariate
polynomials) from a multivalued black box. It is a simple matter to use the randomized
multivariate polynomial interpolation techniques of [37] to explicitly determine the Pi'?
Proposition 3 Let 9 be a fixed integer and y be a fixed n-tuple. For x such that Xj is
urnjorml? distributed in the interval 0 < Xi < N, there exists an n-dimensional box I of
volume (9N)? such that y + 9 (x --H y? is uniforml? distributed on a subset of I of volume
Proposition 4 Let Pi,... ,Pk be polynomials in Q[Y1,... , Ynj and let the degree of every
Y1 in every Pi is bounded by D. Furthermore, assume that no p? has more than T non-zero
terms. Then with likelihood of success > 1/2 the Pi can be interpolated from a multivalued
black box ???Pk using O((knD)2T) evaluations, inputs have magnitude less than Np =
O((knD)?T)1 bits and time O(kn2DT3 + k5(nD)4T).
Proof: To reconstruct the multivariate polynomials Pi,. ,Pk, we need the values of
Pi, ... ,Pk at nDT evaluation points, where T is the maximum number of non-zero terms
in any Pi. Each ordered set of values of pi,... ,Pk at x is determined by interpolating the
black box 9?,?, described above. The black box 9:Thy represents univariate polynomials of
degree at most nD. So by Proposition 2, we can produce the k univariate polynomials of
each ?:,y with knD + 1 evaluations of ? and O(k3(nD)2) operations.
The multivariate interpolation algorithm requires the values ofp1(?),... ,Pk(x? at knDT
randomly chosen x, at most. So the total number of values of ??? is k(nDT)(knD + 1)
(knD)2T. If j+ 9 (x --H y? is a Hilbertian point, then each of these values can be computed
by a univariate factorization. For success, each of these (knD)2T points must be Hilbertian.
Since knD values of 9 are needed we can assume that all of the 9 are less than knD. The
points j+9 (x--Hy? lie in a box I of volume (knDNp)fl There are at most R(d,n,knDNp)
non-Hilbertian points in this box. By Proposition 3 the points y + 9(x --H y? are uniformly
distributed in a region of I of volume Np?. Therefore the likelihood that a single one of
these points is Hilbertian is at least
1--H c(d)(knDNp)??21log knDNp =1 _ c(d)(knd)??ilog kndNp
Np?			ThNp
The likelihood that (knD)2T points are all Hilbertian is at least
1 --H ?(?)(?n?)n+?3?l0? knDNp
MN?'
for sufficiently large Np. For some constant c3,this expression is greater than 1 --H e when
logNp > c3(nlogknD+logT)/e. E]
1 Q is used to indicate that we have ignored additional log factors.
7
3.3 Polynomial Multivalued Black Boxes
This section extends the results of the previous subsections to black boxes whose values are
polynomials. That is, let Pi,... , Pk be polynomials in Q[Y1,. .. , Yn] [X]:
P1(X,Y1,...,Yn) =aidi(Yi,...,Yn)Xdl +``.+aio(Yi,...,Y?),
Pk(X,Yl,...,Yn) = ak4(Yi,...,Yn)xdk + ... +a?o(Yi,...,Yn),
where the a?1 are polynomials of degree no more than D in ...... , Yn. Let d denote the
maximum of the dj. A po1?nomia1 multivaitted black box for P1,... , Pk is a multivalued black
box whose values are polynomials:
Given ?PlPk, we could use the techniques of Sections 3.1 and 3.2 to reconstruct the
Pj since ?[X] is a ring. However, this is not particularly efficient. Consider the univariate
case, where n = 1. As in Section 3.1, we would construct black boxes for the symmetric
functions in Pj. Since ??iPk has polynomial values, the ?? will also. In particular,
the degree of X in each value of ??k will be dk. Furthermore, the Q polynomial will be
trivariate.
While Hensel techniques can still be used to factor Q in polynomial time, the approach is
somewhat complex. Here we propose an alternative, simpler approach. First, we determine
d, the actual maximum degree of X that appears in any Pj. We then replace the polynomial
valued black box ?PiPk by d + 1, ?multivalued black boxes. The polynomials (in
..... . , Yn) that these black boxes represent can be reconstructed using the techniques of
Sections 3.1 and 3.2. In more detail:
For two purposes, choose a random value 0 < Ujo < N for each of the Y1 and compute:
?P?LPk(YlO,'??,?nO) =
where we number the Q? so that Q? corresponds with Pj. We claim that with high proba-
bility,
(1) the maximum degree of the Q? will be di, and
(2) for every i, j and ?, if a,?(Yj,. . . ,Yn) ? aje(Yi,. . . ,Yn), then a?e(yio,... ,uno) ?
a1e(yio,.. ,yno)
Now construct d + 1 black boxes, ??(i) for 0 < i < d, that represent polynomials
P1
in ??,... , Yn, as follows: the values returned by ?p(t?)p??(yi,... , Un) are the coefficients
of Xi in the polynomials returned by ??iPk(Yl,.'' , Un) Thus ?p(t1)Pk represents the
polynomials
Si = ?ai?(Yi,. . . ,Yn),. . .,a?i(Yi,. . .
The ffp(l?) Pk are ?muThivalued black boxes, for which we can use the techniques of
Sections 3.1 and 3.2 in order to determine the polynomials a??.
8
We reconstruct the Pj(X,Y1,... , Yn)'s using the information in the Qj(X). Let the
coefficient of Xi in Pi be a?). Further, assume Qi(X) has the form
Qi(X) = q??jXd + ... + qio.
Now, for each 0 < j < di, a1? is the entry in S? whose value at ?io, ,?nO is q?? By
property (2), if there is more than 1 such element then they are equal.
Proposition 5 Let P(X, ..... . , Yn) be a pol?nomial over Q, where the degree of X is
not greater than d and the degrees of the Yi are not greater than D. Using the interpola-
tion schemes of Section 3.? with evaluation points chosen with coordinates between 0 and
6(nlogndD), and with tin Proposition 4 chosen between 0 and O(knD), the number of
operations used to determine the factors of P is O(n2d2DT3 + d6(nD)4T) and the number
of univariate factorizations is O((ndD)2T), with high likelihood of success.
Proof: The time complexity of interpolating polynomial multivalued black boxes is the
same as that for ?multivalued black boxes in Proposition 4 except that we may have as
many as d ? valued black boxes to interpolate. The number of values of each black box, k
in Proposition 4 is also bounded by d.
The degree of Pi(X,Y1,. . . ,Yn) in X will differ from that of Pi(X,yi, . . ,y?) if and only
if a??(yi,... , y?) = 0. By the "DeMillo-Lipton-Schwartz-Zippel lemma" (Proposition 7) the
fraction of the n-tuples in ? that have this property is less than nD/N. Thus, with high
probability, d is the maximum degree of the polynomials returned by ?p1Pk(YlO,?? ,
To ensure property (2) the UiO must be chosen such that W(y10,... , uno) # 0, where
W(Y1,...,Yn)= II			II
o<?<d 1<i<j<?k
(aei(Yi,...,Yn) --H ae?(Yi,.. .,Yn)).
The maximum degree of any Yi in W is D(D + 1)(k2), so agaln by using Proposition 7,
the fraction of n-tuples that are accidental zeroes of W is bounded by nD(D + 1)k(k --H
1)/2N. The probability that a randomly chosen n-tuple,(yi,... , y?), will meet all of these
conditions is thus
nDnD(d+1)k(k?1)>			ndDk2			nd3D
1??N+2N? 1--H			N			>1--H N
or N > nd3D. Proposition 4 requires that N be at least this large. ?
Combining this result with the univariate factoring algorithm of V. Miller [27j gives the
following proposition.
Proposition 6 Let P(X1,... , Xn) be a muitivariate pol?nomial over ?, where the de-
gree of each Xi in P is bounded by d, and the sum of the absolute value of the coef-
ficients in P is bounded by H. Then P can be factored into irreducible components in
O(n3d10+?HT + nd3T3) arithmetic operations (for any e > 0). With classical integer mul-
tiplication O(n3d11+?HT + nd3T3) arithmetic operations are required.
9
4 Acknowledgements
This work was supported in part by the Advanced Research Projects Agency of the Depart-
ment of Defense under ONR Contract N00014--H92--HJ--H1989, by ONR Contract N0O014--H92--H
J--H1839, NSF Contract IRI--H9006137 and in part by the U.S. Army Research Office through
the Mathematical Science Institute of Cornell University.
References
[1] Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, and Madhu Sudan. Reconstructing algebraic
functions from mixed data. In 33th Symposium on Foundations of Computer Science, pages
503--H512. ACM, 1992.
[2] Michael Ben Or and Prasoon Tiwari. A deterministic algorithms for sparse multivariate poly-
nomial interpolation. In 20th Symposium on Theory of Computing, pages 301--H309. ACM, 1988.
[3] Elwyn Ralph Berlekamp. Factoring polynomials over finite fields. Bell System technical Journal,
46:1853, 1967.
[4] Elwyn Ralph Berlekamp. Factoring polynomials over large finite fields. Mathematics of Com-
putation, 24(111):713--H735, July 1970.
[5] David G. Cantor and Hans Zassenhaus. A new algorithm for factoring polynomials over finite
fields. Mathematics of Computation, 36(154):587--H592, April 1981.
[6] Michael Clausen, A. Dress, Johannes Grabmeier, and Marek Karpinski. On zero-testing and
interpolation of k-sparse multivariate polynomials over finite fields. Research Report 8522--HCS,
Universita?t Bonn, May 1988.
[7]
[8]
[9]
[10]
[11]
[12]
5. D. Cohen. The distribution of Galois groups and Hilbert's irreducibility theorem. Proceedings
of the London Mathematical Society (3), 43:227--H250, 1981.
Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing.
Information Processing Letters, 7(4):193--H195, June 1978.
K. D5rge. U?ber die Seltenheit der reauziblen Polynome unci cier Normaigieichungen. Mathe-
matische Annalen, 95:247--H256, 1926.
K. D5rge. Zum Hilbertschen Irreduzibllita?tssatz. Mathematische Annalen, 95:84--H97, 1926.
K. Do?rge. Einfacher Beweis des Hilbertschen Irreduzibilita?tssatzes. Mathematische Annalen,
96:176182, 1927.
Torsten Ekedahl. An effective version of the Hilbert irreducibility theorem. In Catherine
Goldstein, editor, S?minaire de Th6orie des Nombres, Paris 1988-1989, volume 91 of Progress
in Mathematics, pages 241--H249, Boston, 1990.
[13] W. Iranz. Untersuchugen zum Hilbertschen Irredunbilita?tssatz. Mathematische Zeitschrift,
33:275--H293, 1931.
[14] Michael D. Fried. On Hilbert's irreducibility theorem. Journal of Number Theory, 6:211--H231,
1974.
[15] Dima Yu. Grigor'ev and Marek Karpinski. The matching problem for bipartite graphs with
polynomial bounded perminants is NC. In ?8th Symposium on Foundations of Computer Sci-
ence, pages 166--H172. ACM, 1987.
10
[16] Dima Yu. Grigor'ev, Marek Karpinski, and Michael F. Singer. Fast parallel algorithms for
sparse multivariate polynomial interpolation over finite fields. S?AM Journal of Computing,
19(6):105?1063, 1990.
[17] David Hilbert. jiber die Irreduzibilitat ganzer rationaler Funktionen mit ganzzahligen Koef-
fizienten. Journai fu?r reine und angewante Mathematik, 110:104--H129,1892.
[18] Ming-Deh A. Huang. Factorization of polynomials over finite fields and decomposition of primes
in algebraic number fields. Journai of Algorithms, 12(3):482--H489, 1991.
[19] Ming-Deh A. Huang. Generalized Riemann hypothesis and factoring polynomials over finite
fields. Journal of Algorithms, 12(3):464--H481, 1991.
[20] Erich Kaltofen. Computing with polynomials given by straight-line programs II: Sparse fac-
torization. In 2?h Symposium on Foundations of Computer Science, pages 451--H457. ACM,
1985.
[21] Erich Kaltofen. A polynomial-time reduction from bivariate to univariate integral polynomial
factorization. SlAM Journal of Computing, 14(2):469--H489, May 1985.
[22]
Erich Kaltofen and Barry Marshall `Irager. Computing with polynomials given by black boxes
for their evaluations: Greatest common divisors, factorization, separation of numerators and
denominators. Journal of Symbolic Computation, 9(3):301--H320, March 1990.
[23] Hans-Wilhelm Knobloch. Zum Hilbertschen Irreduzibilitiitssatz. Abhandiung Mathematische
Seminar Univ. Hamburg, 19:176190,1955.
[24] Hans-Wilhelm Knobloch. Die seltenheit der reduziblen polynome. Jarhesbericht der Deutsche
Mathematische Vergeinung, 59(1): 12--H19,1956.
[25] Leopold Kronecker. Grundziige einer arithmetischen Theorie der algebraischen Gro??en. Journal
f?r reine und angewante Mathematik, 92:1--H122, 1882.
[26] Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and Laslo Lovasz. Factoring polynomials with
rational coefficients. Mathematische Annalen, 261:515--H534,1982.
[27]
Victor 5. Miller. Factoring polynomials via relation-finding. In Danny Dolev, Zvi Galil, and
Michael Rodeh, editors, Theory of Computing and Systems, volume 601 of Lecture Notes in
Computer Science, pages 115--H121, New York, 1992. Springer-Verlag.
[28] E. Ng, editor. EUROSAM `79, volume 72 of Lecture Notes in Computer Science, Berlin-
Heidelberg-New York, 1979. Springer-Verlag.
[29] Lajos R6nyai. Galois groups and factoring polynomials over finite fields. In 30th Symposium
on Foundations of Computer Science, pages 99104. ACM, 1989.
[30] Andrej Schinzel. On Hilbert's irreducibility theorem. Annaies Polinici Mathematici, 16:333--H
340, 1965.
[31]
[32]
[33]
Arnold Scho?nhage. Factorization of univariate integer polynomials by diophantine approxima-
tion and an improved basis reduction algorithm. In Jan Paredaens, editor, Automata, Languages
and Programming, volume 172 of Lecture Notes in Computer Science, pages 436--H447, Berlin-
Heidelberg-New York, 1984. Springer-Verlag.
Jacob T. Schwartz. Probabilistic algorithms for verification of polynomial identities. Journat
of the Association for Computing Machinery, 27:701--H717,1980.
V. G. Sprindzuk. Reducibility of polynomials and rational points on algebraic curves. Soviet
Mathematics, 21:331--H334,1980.
11
[34] V. G. Spnndzuk. Arithmetic specializations in polynomials. Journal fu?r reine und angewante
Mathematik, 340:26--H52, 1983.
[35] Joachim von zur Gathen. Hensel and Newton methods in valuation rings. Mathematics of
Computation, 42(166) :637--H661, April 1984.
[36] Joachim von zur Gathen and Erich Kaltofen. Factoring sparse multivariate polynomials. Journal
of Computer and System Sciences, 31:265--H287, 1985.
[37] Richard Eliot Zippel. Probabilistic algorithms for sparse polynomials. In Ng [28], pages 216--H226.
[38] Richard Eliot Zippel. Newton's iteration and the sparse Hensel algorithm. In Paul Wang,
editor, SYMSAC `81: Proceedings of the 1981 ACM Symposium on Symbohc and Algebraic
Computation, pages 68--H72. Association for Computing Machinery, 1981. Number 505810.
[39] Richard Eliot Zippel. Interpolating polynomials from their values. Journal of Symbohc Com
putation, 9:375--H403, March 1990.
A Example
A simple problem that illustrates the ideas of this paper is factoring
P(X,Y) =x4+2X3-X2Y2+X2+2XY2-Y2,
which is an element of Z [Y\ [X]. Clearly, the maximum degree of Y in any factor of P is
2. The first step is to construct a black box that accepts a value Y = y? and returns the
univariate factors of P(X, y). For almost all y? E Z, P(X, vi) factors into two irreducible
quadratic polynomials:
= ?X2 + a11(y?)X + aio(yi),X2 + a?i(ui)X + a?o(yi)Y.
For this small example we will bound our sample points such that 0 < y < 100, i.e.,
B = 100. Thus the probability that a randomly chosen y will have properties (1) and (2)
is greater than
nD2k2			1. 22. 22
1 --H			= 1 --H			100			84%.
Choosing t = 81 we have
= fX2 + 82X --H 81,X2 --H 80X +81l,
and Q1(X) --H X2+82X--H81 and Q2(X) --H X2--H80X+81. So, unless we have been unlucky,
the maximum degree in X of any factor is 2. We now construct two Z multivalued black
boxes,
= the set of coefficients of the linear terms of ?(y)
?(0) (v) = the set of coefficients of the constant terms of ?(y)
The values of these black boxes are:
ffiff6(1)?ff(O)
1			l2,0l			(1,--H1?
2			?3, --H1)			f2, --H2?
3			?4, --H2?			?3, --H3?
12
Using the technique in Section 3.1 these values can be interpolated to produce (using the
techniques of Section B)
?/6(1)=--H?1+Y,1--HYy and _66(0)=?Y?--HYy.
Let Pj(X, Y) be the factor corresponding to Qj(X). Evaluating the two sets of polyno-
mials above at Y = 81 and comparing the values of Qj(X), we see that
P1(X,Y) = X2+(1+Y)X -?
P2(X,Y) =X2+(1 -Y)X+Y.
So
P(X,Y) = (X2+ (1 +Y)X -Y)(X2+ (1 -Y)X+Y).
Notice that, except for Y = 0, all elements of ? are Hilbertian for this problem.
B Finding Linear Factors of Bivariate Polynomials
In this section we demonstrate that, given the linear factors of Q(Z, 0), the linear factors
of Q(Z, ?) can be found in a very simple fashion.
A subcase of the work in [37,38], is the use of Newton's method to determine the linear
factors of a bivariate square free polynomial Q(Z, e) from the linear factors of Q(Z, 0).
Here we give a complete description of this subcase. For clarity we assume that the leading
coefficient of Z in Q(Z, e) is 1. In Appendix C we describe how this technique can be
adapted to non-momc polynomials.
Let Q(Z, 0-) be a square free monic polynomial over a ring ?[e], where ? is a field.
The linear factors of Q(Z, ?) are of the form Z --H o(?) where ? is a polynomial in e and
= 0. Let a(?) have the form
a(e) =ao+ai(e--H0)+...+ae(e--HOY
In the following paragraphs we develop an iteration formula based on Newton's method
modulo powers of (e --H 0) that allows us to compute a(e) efficiently from Q, 0 and ao,
where Q(ao, 0) = 0. This technique is well known in the computer algebra literature [35,38].
The description is provided here for completeness.
For simplicity, we translate 0 to the origin. Let Q(Z, 0-) = Q(Z, e + 0). Then Z --H ao
will be a zero of Q(Z, 0) and Z --H a?(e) will be a zero of Q(Z, e) where
a = ao+aie+a2&+.??+aee?.
The image of a modulo ek+1 is denoted by a(k). Thus a(O) --H ao a(1) = ao + aie and
a(k) = ao + aie + ... + a?ek
Using the Taylor series expansion, we can write Q(Z, ?) as a polynomial in Z --H a(k?1)
giving
Q(Z, e) --H Q(a(k?1), e) + QI(o(k?1), ?)(Z --H a?k?1)) + Qll(a(k?l),?? (Z --H a(k))2 + ... (4)
2
13
LinearNewton (Q(z,e), 0, a0, ?)
w&?[8Q??) ze==aei?1;
a0;
Q(z,e)
for k=1,...,? do (
set ak to w times the coefficient of ek in Q(a(k?l), e',
0L(k) H			+ a?ek;
a			a(t)(e?o);
return(a);
Figure 1: Procedure to obtain linear factors
In this and all following expressions, primes (`) refer to the partial derivative with respect
to the first argument.
Since Z = a is a zero of Q(Z, e), substituting Z = a into (4) gives
o = Q(a?, e) = Q(a(k?l), e) + Q!(a(k?l), ?)(a --H a(k?l)) t Qll(a(k2?1),e) (a --H 0L(k))2 +
Notice that a --H a(k?l) --H a?ek + a?+iek+l +.... Reducing the above equality modulo ek+1
gives
0 --H Q(a(k?l), e) + QI(a(k?l), ?) ak ek (mod ek+l) (5)
Since 0t(k--H1) is the image of a modulo ek, Q(a(k?l),e) = Omodek. Thus we can write
Q(a((k?l),e) = Q?ekmodek+l where Qk is an element of the field F. Qk is a function of
Q and aO...., ak?1. Dividing by ek in (5) gives
0 = Qk + Q??(a(k?l),e)a? (mod e)
Reducing the expression on the right hand side modulo e is equivalent to substituting e = 0
into the right hand side, so solving for a? gives
Qk			Qk
ak = --H -			--H			-			--H
Qk			____			(6)
Q'(ao,O)
Q?(a(k--Hl)(0),0)			Q'(ao,O)
If the characteristic of F is zero and Q(Z, 0) is square free then Q'(a0, 0) does not vanish,
since Z = ac is a simple zero of Q(Z, 0). If Q(Z, e) has factors over a ring R, then each of
the divisions in (6) will be exact.
We have just provided a formula for computing ak given ao...., a??i. This allows us to
compute a(k) for any value of k efficiently. Since a(e) does not contain any powers of e
greater than e, a(?) --H a(e)(e --H 0).
The procedure in Figure 1 takes Q(Z, e), starting point (0, ao) and a degree bound ? as
inputs and returns a(?), aroot of Q(Z,e) corresponding to (Z,e) = (O,ao). LinearNewton
is a linearly convergent iteration uses O(?) operations and only requires one division.
Quadratically convergent iterations can also be developed and are discussed in [35,38].
14
c Non-Monic Polynomials
If we want to factor a non-monic square free polynomial P(X,Y1,... , Yn) over a field we
proceed as follows. First assume that P is primitive, i.e., no non-constant polynomial in
Yn divides its coefficients. Assume the true factorization of P(X,Yi,...,Yn)is
P(X,Y1,...,Yn)=Pj(X,Y1,...,Yn)???Pk(X,Y1,...,Yn),
where the leading coefficient of P is L(Y1,... , Yn) and the leading coefficient of Pj is
Yn). Construct a multivalued black box, ?p that proceeds as follows. Given
= ....... , y?) it obtains the monic factorization:
=Pl(X).'?Pk(X).
Note that the coefficients of the P(x) are the images of rational functions, not polynomials.
?p then returns the polynomials:
L(U1,...,Yn)?P1(X),...,L(Y1,...,Yn)?Pk(X).
The coefficients of these polynomials are also polynomials, so we can use the techniques of
this paper to compute the polynomials:
P1(x,Y1,. . . ,Yn),. . . ,Pk(X,Yl,. . .
where
L(Y?			,Yn)
Pi(X?Yi??Yn)=?y1,,y;??
v
.P', (?, ?,.o+., ? 1
Since the Pj(X,Yi,... , Yn) are primitive (by Gauss' lemma), Pj is the primitive part of P,
i.e., the quotient of P and the GCD of the coefficients of P (with respect to X).
Since L has no more terms than P(X,Y1,. . . ,Yn), none of the P will have more than
T2 terms, where T is the maximum number of terms of any of the Pj. Thus we have shown
that primitive sparse multivariate polynomials can be factored in polynomial time.
If the polynomial is not primitive then we can still follow this general approach but it
must be done one variable at a time. Inunediately removing the content of P may not be
satisfactory because it has not known how much larger the primitive part of a polynomial
can be thanitsfactorization.
D Probabilistic Zero Testing
Given a black box ?p for a polynomial P(X1,... , Xn) over a field F, one can probabilis-
tically determine if P = 0 by examining ?p(xi,... ,xn) for randomly chosen ?,. If the
value is ever different from zero then P cannot be the zero polynomial. An estimate of the
number of times a non-zero polynomial can take on the value zero is given by the following
proposition.
15
Proposition 7 Let F be a field, f E F[x1,. . . ,Xn] and the degree off in each of Xj be
bounded b? d1. Let Zn(B) be the number of zeroes off, x such that ?? is chosen from a set
with B elements, B  d. Then
Zn(B) < B?--H(B--Hd1)(B?d2)???(B?dn)
0 ((d1 + d2 + .... dn)Bfl?1).
A proof of Proposition 7 is given in [39].
The idea of probabilistic zero testing was independently discovered by at least three
different groups of researchers at aimost the same time. DeMillo and Lipton presented
essentially this result in the context of testing the correctness of algebraic programs [8] in
1978. Schwartz [32], used this result in the context of testing for polynomial identities.
Zippel [37] used Proposition 7 not just to determine if a polynomial was identically zero,
but as part of a complete randomized interpolation algorithm for sparse polynomiais.
If a bound is known for the number of non-zero terms in P, then a deterministic aigo-
rithm for zero-testing and for sparse interpolation can be given. Results along these lines
are given in [2,6,15,16,39].
16
