A3 about factoring

Factorization of Multivariate Polynomials Over Finite Fields Author(s): J. von zur Gathen and E. Kaltofen Source: Mathematics of Computation, Vol. 45, No. 171 (Jul., 1985), pp. 251-261 Published by: American Mathematical Society Stable URL: http://www.jstor.org/stable/2008063 Accessed: 19/04/2010 16:55 Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at http://www.jstor.org/page/info/about/policies/terms.jsp. JSTOR's Terms and Conditions of Use provides, in part, that unless you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you may use content in the JSTOR archive only for your personal, non-commercial use. Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained at http://www.jstor.org/action/showPublisher?publisherCode=ams. Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed page of such transmission. JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact [email protected]. American Mathematical Society is collaborating with JSTOR to digitize, preserve and extend access to Mathematics of Computation. http://www.jstor.org MATHEMATICS OF COMPUTATION VOLUME 45, NUMBER 171 JULY 1985, PAGES 251-261 Factorization of Multivariate Polynomials Over Finite Fields By J. von zur Gathen and E. Kaltofen* Abstract. We present a probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in time polynomial in the input size, i.e., in the degree of the polynomial and log (cardinality of field). The algorithm generalizes to multi- variate polynomials and has polynomial running time for densely encoded inputs. A determin- istic version of the algorithm is also discussed, whose running time is polynomial in the degree of the input polynomial and the size of the field. 1. Introduction and Summary of Results. Polynomials with coefficients from a finite field and their factorization properties have been considered for a long time. In 1846, Schonemann proved that univariate polynomials over Z. have the unique factorization property (Schonemann [22, p. 276]). Since there is only a finite number of factor candidates, the factorization problem is immediately shown to be computa- ble. However, an efficient algorithm to compute these factors was not presented until the late 1960's. Berlekamp [3] then devised an algorithm which factors univariate polynomials over a finite field F with q elements in O(qn3) field operations, where n is the degree of the polynomial (see Knuth [16, Section 4.6.2]). This running time is polynomial both in n and q. Soon after, Berlekamp [4] made the running time polynomial in the input size, i.e., using log q rather than q, at the expense of introducing a probabilistic rather than deterministic method. It seems natural to ask whether this can also be accomplished for multivariate, say bivariate polynomials, over F. In particular, given a bivariate polynomial of total degree n with coefficients in F, can one find (probabilistically) its factors in sequential running time polynomial in n and log q? Older algorithms proposed for this problem (e.g., Musser [20, 2.7.2], and Daven- port-Trager [9]) had an exponential worst case running time. The same was true of the Berlekamp-Zassenhaus approach to factoring integer polynomials, until Lenstra-Lenstra-Loviasz [19] (for the univariate case) and Kaltofen [14], [15] (for the multivariate case) provided a polynomial-time solution. In this paper, we give a Received May 31, 1983. 1980 Mathematics Subject Classification. Primary 12C05, 68C20. Key words and phrases. Polynomial factorization, multivariate polynomials, finite fields, probabilistic algorithms. * E. Kaltofen's current address: Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York 12181. A preliminary version of this paper appeared in the Proc. 10th Colloquium on Automata, Lang. and Prog., Springer Lecture Notes Comp. Sci.,v. 154, pp. 250-263. ?1985 American Mathematical Society 0025-5718/85 $1.00 + $.25 per page 251 252 J. VON ZUR GATHEN AND E. KALTOFEN polynomial-time factorization algorithm for bivariate polynomials over a finite field, based on the methods from Kaltofen [14]. Chistov-Grigoryev [8] and Lenstra [18] have also presented polynomial-time algorithms for this problem. Both these papers are based on the short vector algorithm for lattices from Lenstra-Lenstra-Lovasz [19], and are quite different from ours. Our algorithm has two variants: a probabilistic one (Las Vegas) with running time (n log q)O(l), and a deterministic one with running time (nq)0(1), where n is the degree of the input polynomials and q the cardinality of the coefficient field (Section 4.2). In our deterministic version, q could be replaced by log q if one could factor univariate polynomials over finite fields in deterministic time polynomial in log q. Observe that n log q is the input size in a natural "dense" encoding of polynomials. Our description concentrates on the probabilistic variant, which may be the more important one for practical purposes. We also give a parallel variant (Section 4.1) for our algorithm which runs in parallel time O(log2n log q), based on the results for univariate factorization in von zur Gathen [11]. It is straightforward to generalize our algorithm for factoring multivariate poly- nomials (Section 4.3). Again the running time is polynomial in the input size, provided the inputs are encoded as dense polynomials. Chistov-Grigoryev [8] and Lenstra [18] also present multivariate factoring algorithms of polynomial running time. Using an effective Hilbert Irreducibility Theorem and the results presented here, von zur Gathen [12] presents a polynomial-time factoring procedure for sparsely encoded multivariate polynomials. 2. Factoring a Nice Polynomial. The algorithm for factoring an arbitrary poly- nomial f E F[x, y] proceeds in two stages. We first preprocess f into a "nice format", and then factor the nice polynomial. We start by describing the crucial second stage. We assume that an algorithm for factoring univariate polynomials over F is given. This algorithm will be allowed to be probabilistic (Las Vegas), so that it either returns the correct answer or "failure", the latter with small probability. Definition 2.1. Let F be a field, and f E F[x, y]. We call f nice if the following conditions hold: (N1) f (x, 0) E F [ x ] is squarefree. (N2) f is monic with respect to x. Algorithm QUICK FACTORING. Input: A nice polynomialf E F[x, y]. Output: An irreducible factor g E F[x, y] of f. 1. Compute an irreducible monic factor h E F[x] of f(x, 0). If h = f(x, 0), then return f. If the probabilistic univariate procedure returns failure, then return "failure". 2. Set dx = degxf, dy = degyf, and d = 2dxdy. Set E = F[t]/(h(t)), and ao = (t mod h(t)) E E. We use the Newton iteration in steps 3 and 4 to compute MULTIVARIATE POLYNOMIALS OVER FINITE FIELDS 253 b E E[y] such that f(b, y) 0 modyd+ in E[y]. 3. Set s = 1/fx(a0, O) E E, wherefx = af/ax E F[x, y]. (Note that fx(a0, 0) 0 0, since otherwise a0 would be a double zero for f(x, 0), contradicting its squarefreeness.) 4. For k = 1, ... . ,d compute ak = ak-I - sf(ak-1, y) E E[y]. ("mod y i.e., truncating the powers y' of y with 1 > k. Then f(ak) - modyk?1). Set b = ad. 5. Find the minimal i, deg h < i < dx, for which there exist u u,. . E.,u = E F[y] such that deg.uj < dy for 0 j < i, b' + u jbu1 0modyd+l 0< i Compute the corresponding u0, . . , u- 1. 6. Return g = xi + ujxi E- F[x, y]. 0<j< i For the timing analysis, we assume that the factorization procedure used in step 1 to factor a univariate polynomial of degree e takes at most T(e) operations in F. We will later allow a probabilistic procedure (Las Vegas), which either correctly returns an irreducible factor, or "failure". THEOREM 2.2. Let f E F[x, y] be nice, and assume that step 1 of algorithm QUICK FACTORING does not return "failure ". Then the following hold: (i) The output is an irreducible factor off. (ii) Let n be the total degree of f, and dx the degree of f with respect to x. The algorithm can be performed in 0(n3dj4) + T(dx) or 0(n7) + Tr(n) operations in F. Proof. The correctness claim (i) follows just as in Kaltofen [14, Section 4]. The output g will be the irreducible factor of f such that h divides g(x, 0). In applying (ii), we will need the first estimate, which clearly implies the second one. First observe that step 3 can be performed in O(dx) operations in E. Each ak in step 4 takes 0(dx) operations in E[y] (computing mod yk+ 1). By Lemma 2.3, step 4 then takes 0(d 2dx log4 d) operations in E. In step 5, we first compute b2, b3,. . . ,bdx in 0(dx) operations in E[y] (again mod yd+l) or 0(dxd log4 d) operations in E. Then we have to solve a system of at most (d + 1)dx linear equations in at most dx(dy + 1) unknowns over F. (Note that one equation in E corresponds to less than dx equations in F.) Gaussian elimina- tion solves the system in 0((dx(dy + 1))2(d + 1)dx) or 0(d3dx) operations in F. Noting that [E: F] < d, d < ndx < n2, and using Lemma 2.3, we get a total of 0(d 3d + d2d 2log4 d log4 dx) or 0(n3d4) operations in F. L0 254 J. VON ZUR GATHEN AND E. KALTOFEN The following lemma gives an upper bound on the time to perform arithmetic in finite field extensions. The more refined algorithms by Schonhage-Strassen [24], Schonhage [23], and Lempel-Seroussi-Winograd [17] give better bounds on the number of nonscalar operations needed for multiplication. LEMMA 2.3. Let F be an arbitrary field, and h E F[x] of degree d. Then an arithmetic operation (+, -, *, division by an invertible element) in F[x]/(h) can be performed in O(d log4 d) operations in F. If the cardinality #F of F is at least 2d, then it can be performed in O(d log2 d) operations. Proof. Let q = #F. We consider the elements of F[x]/( h) as being represented by polynomials in F[x] of degree less than d (i.e., by its sequence of d coefficients). The last claim is well-known (see Aho-Hopcroft-Ullman [1, 8.3]). If q < 2d, we can (deterministically) compute an irreducible polynomial w E F[t] of degree [logq 2d 1 (see Theorem 3.1). Setting K = F[t]/(w), an operation in F[x]/(h) c K[x]/(h) can be simulated in O(d log2 d) operations in K, and an operation in K costs O(log2 d) operations in F, giving a total of O(d log4 d) operations in F for each operation in F[x]/(h). El Remark 2.4. Some simplifications of the algorithm may be of practical interest. Step 4 only has to be executed for k = 1,. . . , d, where dy (2dX 1) (See Kaltofen [14, Theorem 4.1].) The algorithm can also be performed without the assumption that f is monic with respect to x. If c E F[y] is the leading coefficient, then step 4 has to be executed for k = 1, . . , 8, where [dy(2dx-1) + deg c(dx + 1)1 degh h In step 5, we then have to consider degyuj < dy degc for0 <j <i, cb' + E ujbj-O mody8+, 0<j < i and in step 6, we have to compute v = gcd(c, u0,...,ui) F[y] and return g cx + E j xj. ? - -x' 3. The Preprocessing Stage. In this section we describe the algorithm for factoring an arbitrary bivariate polynomial over a finite field. It converts the input polynomial into a nice polynomial, calls QUICK FACTORING, and then determines a factor of the input polynomial. We first need an algorithm for the gcd of two bivariate polynomials. We use a modular approach for this; see Brown [5]. MULTIVARIATE POLYNOMIALS OVER FINITE FIELDS 255 Algorithm BIVARIATE GCD. Input: Two polynomials f, g E F[x, y], where f is monic with respect to x, and F is an arbitrary field. Output: The monic (with respect to x) gcd h c F[x, y] of f and g. 1. Set dx = max{degxf, degxg}, dy = max{degyf, degyg}, and d = 2dxdy. If d = 0, use a procedure for univariate gcd's. If q = #F < 3d, then do the following. Choose an irreducible monic polynomial w E F[t] of degree [log q 3d 1, and replace F by the extension field F [ t]/( w). 2. Choose any pairwise distinct a1,..., a2d E F such that g(x, ai) has the same degree in x as g. (We need at most 2d + dy < 3d elements in F to locate such evaluation points.) 3. For all i, 1 < i < 2d, compute the monic hi = gcd(f(x, ai), g(x, ai)) = E hijxj E F[x]. 0<j 4. Set m = min{deg hi: 1 < i < 2d}, and choose some M c {1,. . . ,2d} with #M = dy + 1 anddegh1= mforalli EM. 5. For 0 < j < m, interpolate the h 1's: compute bj E F[y] of degree at most d, with bj(ai) = hij for all i E M. (In particular, bm = 1.) 6. Return h = X0,<j,m bjx'. THEOREM 3.1. Let f, g E F[x, y], where f is monic with respect to x, and let d be as in step 1 above. Then algorithm BIVARIATE GCD has the following properties: (i) It correctly computes a gcd off and g. (ii) It can be performed in O(d210g4 d) operations in F. If #F >? 3d, then it takes 0(d 2log2 d) operations. Proof. Let h0 = gcd(f, g) E F[x, y] be monic with respect to x, and f = uh0, g = vh0 with u, v e F[x, y]. Then the resultant r = resx(u, v) E F[y] is a polynomial of degree less than d, and for any a E F with r(a) = 0 and degg(x, a) = degxgwe have gcd(f(x, a), g(x, a)) = ho(x, a). Thus for at least d among h1,. ., h2dwe have h = ho(x, ai), and deg hi > degx h0 for all i. Therefore, some M as in step 4 can be foun'd, and steps 5 and 6 correctly compute h = h0. If q < 3d, then we can find w, as in step 1, deterministically by testing each monic polynomial w E F[t] of degree 1 = [logq 3d 1 for irreducibility. There are at most q' < 3dq < 9d2 such polynomials, and each irreducibility test takes O(log2 d log2log d log log log d log q) or O(log4 d) operations in F (Rabin [21]). Any operation in F[t]/(w) can be simulated by O(log2 d) operations in F. This factor log2 d has to be multiplied to the estimates for steps 3 to6onlyifq < 3d. 256 J. VON ZUR GATHEN AND E. KALTOFEN In step 3, the number of operations is 0(d) for each f(x, ai) and g(x, ai), and 0(dxlog2 dx) for each hi (Aho-Hopcroft-Ullman [1, 8.9]), for a total of 0(d(d + dx log2 dx)) operations. Obviously m < dx, and the interpolations in step 5 take 0(dx(dYlog2d,)) operations (Aho-Hopcroft-Ullman [1, 8.7]). The total is 0(d21log2 d log2 d) operations, and 0(d210g2 d) if q > 3d. El We now describe the algorithm for computing a factor of a bivariate polynomial over a finite field. Algorithm BIVARIATE FACTORING. Input: A polynomial f E F[x, y], where F is a finite field with q elements, and p = char F, the characteristic of F. Output: Either a nonconstant factor g E F[x, y] of f, or "failure". 1. (Check primitivity.) Set dx = degxf, and writef = 2O<i<d f xi with fi E F[y]. Compute the content c= contx(f) = gcd(fo,...jtd) E F[y]. If c is nonconstant, then return c. 2. (Check squarefreeness.) Compute fx = af/ax and fh = af/ay. If fx = fv = 0, then write f = Y f11x'Py'P set g = LyJ and return g. (We have gP = f.) If fx = 0 and fy # 0, then interchange the role of x and y and go to step 1. Now we have fx # 0. Compute the monic g = gcd(f, fx). If g # 1, then return g. 3. (Monic version of f.) Let Jo E F[y] be the leading coefficient of f with respect to x. Set V = fodx -1f ( , y ) E F[x, y]. (v is monic of degree dx with respect to x.) 4. (Extend F.) Set dy =degY v, m=4max*Fdx, d, and d =2dxd. If q=#F>d, then set F* = F. Otherwise choose a prime number / with m < / < 2m. Choose monic polynomials wl,... . W81n E F[t] of degree / at random, and test them for irreducibility. If none is irreducible, return "failure". Otherwise choose an irreducible wi, and set F* = F[t]/(wi). 5. (Good evaluation point.) Set r = discx(v) = resx(v, av E F[y]. (r is a nonzero polynomial of degree < (2d-, - I)dx < d.) Choose c E F* such that r(c) = 0, and set f* = v(x, y - c) E F*[x, y]. (f * is nice.) 6. Call procedure QUICK FACTORING with input f* E F*[x, y], to return g* E F*[x, y]. 7. Set e = degxg*, g1 =f-elg*(xf0, y + c) E F*[x, y], go = contx(gl) E F*[y], g = glIg0E F[x,y], and return g. MULTIVARIATE POLYNOMIALS OVER FINITE FIELDS 257 For a concrete estimate of the running time, we have to implement step 1 of the procedure QUICK FACTORING. The probabilistic version of Berlekamp's uni- variate algorithm due to Cantor-Zassenhaus [7] (see also Knuth [16, 4.6.2]) factors a polynomial of degree e in O(e3 + e2logelogq) operations in F, where q = #F. Other algorithms for this problem are due to Berlekamp [4], Rabin [21], Ben-Or [2], and Camion [6]. This algorithm can be written as a Las Vegas procedure, so that it either returns an irreducible factor or "failure" -the latter with probability at most 2. The algorithm requires O(e log e) random choices from F, and we assume that they can be performed in O(e log e log q) random bit choices. The cost of the Las Vegas univariate factoring procedure in step 1 of QUICK FACTORING is dominated by the cost of other steps. So we can apply that procedure several times, say n + 1 times, to obtain failure probability at most 2- ,i1, where n is the total degree of f. THEOREM 3.2. Let F be a finite field with q elements, and f E F [x, y] of total degree n. Algorithm BIVARIATE FACTORING with input f has the following properties: (i) Iff is irreducible, it either returns f or "failure ". (ii) 1iff is reducible, it either returns a proper factor off or "failure ". (iii) Failure occurs with probability at most 2-. (iv) The algorithm can be performed with O(n710g4 n log2q(n5 + log n logq)) bit operations, and O(n5 log q) random bit choices. Proof. It is well-known how the factorization of f and v in F[x, y] are related; see Knuth [16, Exercise 4.6.2-18], using the coefficient domain F[y]. By a result of von zur Gathen [12, Section 5], the factorizations of v in F[x, y] and F*[x, y] are the same. The relation between factors of v and f * in F*[x, y] is obvious. Also, f * is nice. Note that an 1 as in step 4 exists by Bertrand's Postulate (see Hardy-Wright [13]). In order to see that some c as in step 5 can be found, it is sufficient to show that #F* = ql >, d : q'> 2m+ 1 > 2m2 > d. (The second inequality holds for all m > 1 with m # 3. But for m = 3 we have 1 > 5 and q' > d.) We have now proven (i) and (ii) in the case where no failure occuirs. Failure can either occur in step 6-with probability at most 2n1 by the remark before Theorem 3.2-or in the computation of wi in step 4. There are exactly (ql - q)/l many irreducible monic polynomials of degree 1 in F[x] (Schbnemann [22, Section 46, p. 317]), so that step 4 has failure probability < (1 - q'/ q )81fl (1 - 1)8/fl e-2n -n-1 Therefore the total failure probability is at most 2-. 258 J. VON ZUR GATHEN AND E. KALTOFEN For the timing estimate, first note that d, < n, dy < n2, d = 2dX d < 2n3, 1 < 2m < 2n2, and the total degree n* of f* is not more than n2. Step 1 takes 0(n3) operations, and step 3 0(n4) operations. In step 2, the gcd can be computed in 0(d210g4 d) operations in F by Theorem 3.1, and the pth root in 0(d log q/p) operations in F, since degyf < dy with d from step 4. The prime number 1 can be found deterministically in 0(m"3/210g2 m) bit operations, and w in 0(lnm2 log2 m log log m log q) or 0(n71og3 n log q) operations in F (Rabin [21]). Steps 5 and 7 both take 0(dxd 2) operations. The cost of the algorithm is dominated by the running time for step 6, which is 0((n* )3d4+ n(d3 + d 2logdxlog(q')) or 0(n10 + n5 log n log q) operations in F*. Each operation in F* can be simulated by 0(1 log4 1) operations in F by Lemma 2.3, and 0(1 log4 1 log2 q) bit operations. Thus the total cost is O(n n7log4n log2q(n5 + log n log q)) bit operations. The number of random bit choices is 0(lnl log q) or 0(n5 log q) in step 4, and 0(nd log dx log q) or 0(n2 log n log q) in step 5. 0 We note that if q > d, then the algorithm uses F* = F and runs in O(n3 log2q(n7 + log n log q)) bit operations. Once we have found one nontrivial factor using BIVARIATE FACTORING, we can of course apply the algorithm to this partial factorization. Repeating this yields a probabilistic algorithm which returns either the complete factorization of the input polynomial, or "failure". The total number of bit operations is 0(n81og4n log2q(n5 + log n log q)), and the number of random bit choices is 0(n6log q). The failure probabiliy can be made as small as n 2-2n < 2 -n by repeating the algorithm twice at each stage, in fact less than any prescribed - > 0 by repeating the whole procedure at least (log -)/n times. So we have COROLLARY 3.3. Let F be a finite field with q elements. Polynomials in F[x, y] of total degree n can probabilistically (Las Vegas) be factored completely in time polynomial in n and log q. 4. Some Variants. 4.1. A Parallel Version. The basic subroutines for algorithm BIVARIATE FAC- TORING are a univariate factoring procedure over finite fields, computing uni- variate gcd's, and solving systems of linear equations over a finite field (which also solves the interpolation step in BIVARIATE GCD). In von zur Gathen [11], all these tasks have been shown to be probabilistically solvable in parallel with 0(log2n) operations in F (respectively 0(log2n log2k log p) for factoring). Here n is the total degree of the input polynomial, p = char F, and q = pk = #F. For a complete factorization, one would lift all irreducible factors of f(x, 0) from step 1 of QUICK MULTIVARIATE POLYNOMIALS OVER FINITE FIELDS 259 FACTORING in parallel, using a quadratic Newton procedure (see, e.g., von zur Gathen [10]), and then discard duplicate ones. As our model of parallel computation we can take Boolean circuits. Also a prime number 1 as in step 4 of BIVARIATE FACTORING can be found in parallel with O(log2n) bit operations. The resulting Las Vegas algorithm returns either the complete factorization of the input polynomial, or "failure"; the latter with probability no more than 2-n. The number of processors required is polynomial in n and log q. Thus we have THEOREM 4.1. Let F be a finite field with q = pk elements, where p = char F. Polynomials in F[x, y] of total degree n can probabilistically be factored completely in parallel time O(log2n log 2(kn)log p + log n log q). The second summand comes from the computation of pth roots in step 2 of BIVARIATE FACTORING, and the first summand from step 1 of QUICK FACTORING, where a univariate polynomial of degree at most n over a field with not more than pkn2 elements has to be factored. In step 4 of QUICK FACTORING, each step of the quadratic Newton iteration has to compute s E E[y] such that sfk(ak, y) 1 mod y2k This congruence can be considered as a system of linear equations over the ground field, and solved in parallel time O(log2n). 4.2. A Deterministic Version. Algorithm BIVARIATE FACTORING can be viewed as a reduction from bivariate factoring to univariate factoring over finite fields. All steps of this reduction are deterministic, except the choice of wi E F[t] in step 4. We need wi in order to construct F* with #F* > d, so that step 5 can be executed. But it is sufficient to have w + E F [t] with 1= deg w +> logq d, and use F+= F[t]/(w+). Such an w+ can be found deterministically in time polynomial in d. The problem is that we are not guaranteed that an irreducible factor of f is irreducible in F+[x, y]. Our choice for the degree of w was motivated by the fact that then irreducible factors remain irreducible in F*[x, y] (von zur Gathen [12]), and we can avoid the costly norm computation below. However, the case of w+ as above can be salvaged by introducing the norm N(g) = NF+(X y)/F(x y)(g) = (-1)"res,(w, g) for g E F+[x, y], where we choose g E F[x, y, t] of degree i < 1 in t such that g g mod w (see van der Waerden [25, p. 89]). It is well-known that if g E F+[x, y] is an irreducible factor of f, then N(g) E F[x, y] is a power of an irreducible factor of f (Weyl [26, 1.5]). This irreducible factor is easily found as the gcd of f and N(g). Thus we have THEOREM 4.2. Let F be a finite field with q elements. (i) Factoring bivariate polynomials over F of total degree n is deterministically reducible to factoring univariate polynomials of degree at most n (over a small finite extension field of F). The number of operations for the reduction is polynomial in n and log q. (ii) Bivariate polynomials over F of degree n can be factored deterministically with a number of operations that is polynomial in n and q. Proof. The above discussion has proven (i); we have to factor a univariate polynomial over a finite extension field F+ of F. For (ii), we use any of the deterministic variants of Berlekamp's algorithm. O 260 J. VON ZUR GATHEN AND E. KALTOFEN 4.3. A Multivariate Version. The algorithm can easily be modified for factoring multivariate polynomials over a finite field with q elements. One variable is selected as the main variable, and constants are substituted for the remaining variables. The resulting univariate polynomial is then factored and this factorization lifted. See Kaltofen [15] for details. The running time of the resulting probabilistic algorithm is polynomial in the input size, and polynomial in the input size and q for the deterministic version. The input size for a polynomialf E F[xl,... ,xk] of degree d is O(dklog q) in a "dense encoding". Another measure of size-of greater practical relevance-is the length of a "sparse encoding" of a multivariate polynomial, which is proportional to the number of nonzero terms in the polynomial. Multivariate polynomials can be factored in polynomial time also under this measure, taking input and output size into account (von zur Gathen [12]). 4.4. Remark. Let F be a finite field with q elements. We have (deterministically) reduced the factorization of a bivariate polynomial f E F[x, y] of total degree n to factoring univariate polynomials of degree at most n over a finite extension of F. This problem, in turn, can be reduced to factoring univariate polynomials over F itself, using the method in Berlekamp [4, Section 6]. All reductions are polynomial in n and log q. 4.5. Remark. Our techniques do not allow us to reduce the exponent 7 in the estimate for QUICK FACTORING in Theorem 2.2(ii). However, it would be easy to improve the running time of algorithm BIVARIATE FACTORING. In Remark 2.4 we have indicated how to avoid the necessity of monic inputs. This would result in an O(n7log4n log2q) probabilistic algorithm for factoring a bivariate polynomial of degree n over a finite field with q elements. Open Question. Can one decide the irreducibility of a polynomial f E Zp[x, y] deterministically in time polynomial in deg f and log p? Department of Computer Science University of Toronto Toronto, Ontario M5S 1A4, Canada 1. A. V. AHO, J. E. HOPCROFT & J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. 2. M. BEN-OR, Probabilistic Algorithms in Finite Fields, Proc. 22nd Sympos. Foundations Comp. Sci., IEEE, 1981, pp. 394-398. 3. E. R. BERLEKAMP, "Factoring polynomials over finite fields," Bell System Tech. J., v. 46, 1967, pp. 1853-1859. 4. E. R. BERLEKAMP, "Factoring polynomials over large finite fields," Math. Comp., v. 24, 1970, pp. 713-735. 5. W. S. BROWN, "On Euclid's algorithm and the computation of polynomial greatest common divisors," J. Assoc. Comput. Mach., v. 18, 1971, pp. 478-504. 6. P. F. CAMION, " Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials," IEEE Trans. Inform. Theory, v. 29-3, 1983, pp. 378-385. 7. D. G. CANTOR & H. ZASSENHAUS, "On algorithms for factoring polynomials over finite fields," Math. Comp., v. 36, 1981, pp. 587-592. 8. A. L. CHISTOV & D. Yu. GRIGORYEV, Polynomial-Time Factoring of the Multivariable Polynomials Over a Global Field, LOMI preprint E-5-82, Leningrad, 1982. 9. J. H. DAVENPORT & B. M. TRAGER, Factorization Over Finitely Generated Fields, Proc. 1981 ACM Sympos. Symbolic and Algebraic Computation (P. Wang, ed.) 1981, pp. 200-205. MULTIVARIATE POLYNOMIALS OVER FINITE FIELDS 261 10. J. VON ZUR GATHEN, "Hensel and Newton methods in valuation rings," Math. Comp., v. 42, 1984, pp. 637-661. 11. J. VON ZUR GATHEN, "Parallel algorithms for algebraic problems," SIAM J. Comput., v. 13, 1984, pp. 808-824. 12. J. VON ZUR GATHEN, Factoring Sparse Multivariate Polynomials, Proc. 24th Sympos. Foundations Comp. Sci., IEEE, 1983, pp. 172-179; J. Comput. System Sci. (To appear.) 13. G. H. HARDY & E. M. WRIGHT, An Introduction to the Theory of Numbers, Clarendon Press, Oxford, 1962. 14. E. KALTOFEN, A Polynomial-Time Reduction from Bivariate to Univariate Integral Polynomial Factorization, Proc. 23rd Sympos. Foundations Comp. Sci., IEEE, 1982, pp. 57-64. 15. E. KALTOFEN, "Polynomial-time reduction from multivariate to bivariate and univariate integer polynomial factorization," SIA M J. Comput., v. 15-2, 1985, v. 14, 1985, pp. 469-489. 16. D. E. KNUTH, The Art of Computer Programming, Vol. 2, 2nd ed., Addison-Wesley, Reading, Mass., 1981. 17. A. LEMPEL, G. SEROUSSI & S. WINOGRAD, "On the complexity of multiplication in finite fields," Theoret. Comput. Sci., v. 22, 1983, pp. 285-296. 18. A. K. LENSTRA, Factoring Multivariate Polynomials Over Finite Fields, Proc. 15th ACM Sympos. Theory of Computing, 1983, pp. 189-192. 19. A. K. LENSTRA, H. W. LENSTRA & L. LovAsz, "Factoring polynomials with rational coefficients," Math. Ann., v. 261, 1982, pp. 515-534. 20. D. R. MUSSER, Algorithms for Polynomial Factorization, Ph.D. thesis and TR 134, Univ. of Wisconsin, 1971. 21. M. 0. RABIN, " Probabilistic algorithms in finite fields," SIA M J. Comput., v. 9, 1980, pp. 273-280. 22. T. SCHONEMANN, "Grundzuge einer allgemeinen Theorie der h6heren Congruenzen, deren Modul eine reelle Primzahl ist," J. Reine A ngew. Math., v. 31, 1846, pp. 269-325. 23. A. SCHONHAGE, "Schnelle Multiplication von Polynomen fiber Kdrpern der Characteristic 2," Acta Inform., v. 7, 1977, pp. 395-398. 24. A. SCHONHAGE & V. STRASSEN, "Schnelle Multiplication grosser Zahlen," Computing, v. 7, 1971, pp. 281-292. 25. B. L. VAN DER WAERDEN, Modern Algebra, Vol. 1, Ungar, New York, 1953. 26. H. WEYL, Algebraic Theory of Numbers, Princeton Univ. Press, Princeton, N. J., 1940.