Mathematics and Algorithms for Computer AlgebraPart 1c 1992 Dr Francis J. Wright – CBPF, Rio de JaneiroJuly 9, 20035: Polynomial GCDs and remaindersequencesThe first and last sections are applications of gcds; the intermediatesections are about how to compute polynomial gcds.1 Squarefree decompositionThis provides a restricted factorization of a polynomial and so could alsobe called squarefree factorization, except that factorization usually impliesfactorization into irreducible factors, which a squarefree decom position isnot. Squarefree decompos ition is much simpler and therefore faster thanfull factorization and requires only formal derivatives and gcds. It is anobvious precursor to a full factorization, but there are many situations inwhich a squarefree decomposition is sufficient – for example, to determinewhether a polynomial is a perfect nthpower, and if so to find its nthroot.This section is based on Mignotte.1.1 The basic theoryLet F be a field, either infinite or finite, which requires a slightly moregeneral formulation than is required for the infinite case alone. The infinitefield case can trivially be generalized to an integral domain by dropping thecondition that polynomials b e monic.Definition 1 f ∈ F [x] is squarefree if it is not divisible by the square ofany non-constant polynomial over F , or equivalently if f has only simpleroots in any field that contains F .1Note that squarefree do es not imply irreducible, although irreducibledoes imply squarefree. For example, over Q:• x2+ 3x + 1 is squarefree and irreducible;• x2+ 3x + 2 = (x + 1)(x + 2) is squarefree but not irreducible;• x2+ 2x + 1 = (x + 1)2is neither squarefree nor irreducible.Let f0be the (formal) derivative of f and let g = gcd(f, f0) be theirmonic gcd. If g = 1 then there does not exist any non-constant polynomialthat divides both f and f0, and hence f is squarefree. Conversely, if f isnot squarefree and possesses, over some field E ≥ F , the decompositionf = λme11· · · mekk, e1≥ 2, ei6=1≥ 1,where the miare distinct monic polynomials over E, then the derivativef0= λme1−11· · · mek−1ks where s =kXi=1eim1· · · mi−1mi+1· · · mk.Therefore, the polynomialme1−11· · · mek−1k6= 1because e1≥ 2 and it divides g = gcd(f, f0), so f, f0are not coprime.Moreover, the quotient f/g divides the product m1· · · mkand therefore f/gis squarefree.Hence we have provedProposition 1 Let f be a non-constant polynomial, with coefficients insome field F . Then f is squarefree if and only if f and its derivative f0are relatively prime. Moreover, the polynomial h = f / gcd(f, f0) is alwayssquarefree, and if f06= 0 and gcd(f, f0) 6= 1 then h is a non-trivial factor off.1.2 Squarefree decomposition in characteristic zeroIf F has characteristic zero then none of the eiin s can vanish and hencef06= 0 and no midivides s. Thereforeg = gcd(f, f0) = me1−11· · · mek−1k6= 12because e1≥ 2, andh = f/g = λm1· · · mkis a squarefree polynomial, which is the product of all the distinct squarefreefactors of f.The aim of squarefree decomposition over a field is to compute a set ofmonic coprime polynomials misuch that the polynomial f, now assumedfor convenience to be monic, has the decompositionf = m1m22· · · mkk, k ≥ 1.If no squarefree factor occurs raised to the power i then mi= 1 and so canbe omitted from the product. It is trivial to make f monic by dividing byits leading coefficient if necessary.1.3 Algorithms for characteristic zeroYun1has analysed this problem is detail, and gives three algorithms. Thefirst is due to Tobey and Horowitz:input: monic f ∈ F [x]g1:= gc d(f, f0); h1:= f /g1; i := 1;while gi6= 1 dobegingi+1:= gc d(gi, g0i); hi+1:= gi/gi+1;mi:= hi/hi+1; i := i + 1end.output: monic mi∈ F [x] such that f = m1m22· · · mkkIt works as follows. Iff = m1m22m33· · · mkktheng1= m2m23· · · mk−1k, h1= m1m2· · · mk,where h1is “the squarefree part” of f. For i > 1,gi= mi+1m2i+2· · · mk−ik, hi= mimi+1mi+2· · · mk,and hence as claimedhi/hi+1= mi.1D. Y. Y. Yun, “On squarefree decomposition algorithms”, in Proc. 1976 AMS Symp.on Symbolic and Algebraic Computing, Yorktown Heights, NY, ed. R. D. Jenk s.3This algorithm literally repeats the same basic algorithm for extracting thesquarefree part. However, the repeated differentiation is not necessary, andis avoided in the following modification due to D. Musser, which leads toexactly the same intermediate variable values as the previous algorithm:input: monic f ∈ F [x]g1:= gc d(f, f0); h1:= f /g1; i := 1;while hi6= 1 dobeginhi+1:= gc d(gi, hi); gi+1:= gi/hi+1;mi:= hi/hi+1; i := i + 1end.output: monic mi∈ F [x] such that f = m1m22· · · mkkYun shows that Musser’s algorithm is more e ffic ient than the first, andalso gives another algorithm of his own, which is more complicated but alsomore efficient than Musser’s.1.4 Squarefree decomposition in nonzero characteristicMignotte shows that none of the three algorithms referred to above workscorrectly in nonzero characteristic, for which everything is more complicated.Suppose that F has characteristic p, and that as before f possesses thedecompositionf = λme11· · · mekk, e1≥ 2, ei6=1≥ 1,and hencef0= λme1−11· · · mek−1ks where s =kXi=1eim1· · · mi−1mi+1· · · mk.Then a polynomial midivides s if and only if p divides ei, so that the termof the sum s in which the factor miwould be absent is itself absent.If p does not divide all the exponents eithen suppose that it divides onlythe first h for 0 ≤ h < k. Then f06= 0,g = gcd(f, f0) = me11· · · mehhmeh+1−1h+1· · · mek−1kandf/g = λmh+1· · · mk.4Alternatively, p divides all the exponents eiif and only if f0= 0. Iff =Pfixiand f0=Pifixi−1= 0 then p divides each i for which fi6= 0.Let pebe the greatest power of p that divides the gcd of all the i such thatfi6= 0. Then e ≥ 1 and f can be written as a composition of the formf = H(xpe), H ∈ F [x].Conversely, if f has such a form then clearly f0= 0.Suppose that F is the Galois Field Fpn= GF (pn). (Any finite field ofcharacteristic p must be isomorphic to Fpnfor some n ∈ Z+.) Clearly peand pn− 1 are coprime, so∃u, v, upe+ v(pn− 1) = 1 , 1 ≤ u < pn.Now recall that F∗pnis a cyclic group of order pn− 1. Then for every a ∈ Fpnwe have that either a = 0 or apn−1= 1, and hence(au)pe= a1−v(pn−1)= a,i.e. auis a root of order peof a. In other words, we can solve the equationApe= a as A = au.Recall