UNIVERSITY OF CALIFORNIADepartment of Electrical Engineeringand Computer SciencesComputer Science DivisionCS 282 Prof. R. FatemanSpring, 2004Additional Notes on Polynomial GCDs, Hensel constructionThese notes cover a number of topics that are covered in any of the typical texts. We providethis discussion here to try to touch on some of the highlights and offer some perspective.First we demonstrate that interpolation can be done as a special case of Garner’s Algorithm byappropriately choosing our (relatively prime) mo duli.As an example, we choose the moduli mi, to be linear polynomials,m1= x − b1m2= x − b2. . .mn= x − bnand by f(x) mod mi, we shall mean f(bi). Recall from lecture that we computec1= m−11mod m2c2= (m2m1)−1mod m3. . .cn−1= (mn−1. . . m1)−1mod mnIf we are now given n + 1 points (b1, u1), . . . (bn+1, un+1), we may compute the nthdegreepolynomial which goes through these points by Garner’s Algorithm.Example: Suppose m1= x , m2= x − 1, and m3= x − 2. Thenc1= m−11mod m2= (x−1)x=1= 1c2= (m2m1)−1mod m3= (x−1(x − 1)−1)x=2= 1/2Now suppose that we wish to determine the polynomial of degree two passing through the points(0,5), (1,2) and (2,1). Then1Additional Notes on Polynomial GCDs, Hensel construction 2v1= u1mod m1= (5)x=0= 5v2= (u2− v1) · c1mod m2= ((2 − 5) · 1)x=1= −3v3= (u3− (v1+ m1v2)) · c2mod m3= (1 − (5 + x) · (−3) · 1/2)x=2= (3x − 42)x=2= 1and nowu = v3m2m1+ v2m1+ v1= 1 · x · (x − 1) + (−3) · x + 5 = x2− 4x + 5The above interpolation algorithm computes the unique polynomial of degree n passing throughthe given n − 1 distinct points.The interpolation algorithm given above is one of a number of alternatives. This is usuallycalled Newton’s Interpolation Formula. Other formulations (basically rearrangements with thesame number of operations) include Lagrange and divided differences interpolation. Additionalmaterial on interpolation may be found in any introductory numerical analysis, or see Knuth’sreference [1]. The relevant time bounds for any of these methods for interpolation at an arbitrary setof points are are n(n+1)/2 divisions (or evaluations) and n(n + 1) subtractions. The generalizationof this to v > 1 variables represents a considerable cost in the interpolation phase of the modularGCD algorithm. It will turn out that we can improve upon this, under ce rtain circumstances, byusing another approach.In our lectures we discussed sparse interpolation as invented by R. Zippel [1979] for his sparsepolynomial GCD.The best polynomial GCD algorithms in the early 1970s appear to be the ones based on Hensel’sLemma or variants. Let’s give this a try:Let us try to convince you of the relevance of p-adic Representation here.Recall the notion of p-adic number representation as the representation of integers (or reals) invarious number “systems”. We are all familiar with decimal, binary and other representations ofnumbers (We used base-3 representations in class.). We may even construct system with somewhatmore exotic bases, such as negative bases and, as we shall see shortly, polynomial bases. If p and Nare integers, then the p-adic representation of N is (a0, a1, . . . , am) where for i = 1, . . . , m we have0 < ai< pN = a0p0+ a1p1+ . . . + ampmFor instance, the 3-adic representation of the integer 65 is (2,0,1,2).If p and N are integers, thenthe p-adic representation of N is (a0, a1, . . . , am) where for i = 1, . . . , m we have 0 < ai< pN = a0p0+ a1p1+ . . . + ampmFor instance, the 3-adic representation of the integer 65 is (2,0,1,2).We can extend this notion to polynomials. If p(x) and q(x) are polynomials, then the p-adicrepresentation of q is (a1, a2, . . . , am) where for i = 1, . . . , m −1, aiis in an integer, amis a nonzerointeger andAdditional Notes on Polynomial GCDs, Hensel construction 3q(x) = a0p(x)0+ a1p(x)1+ . . . + amp(x)mFor instance the (x − 1) − adic representation of x3is (1,3,3,1).We can extend this notion to polynomials. If p(x) and q(x) are polynomials, then the p-adicrepresentation of q is (a1, a2, . . . , am) where for i = 1, . . . , m −1, aiis in an integer, amis a nonzerointeger andq(x) = a0p(x)0+ a1p(x)1+ . . . + amp(x)mFor instance the (x − 1) − adic representation of x3is (1,3,3,1).Such items are mere curiosities, as you have also seen the representation of various numbersapproximately, and to successively higher “accuracy” 3-adically, including√7 and 1/2.We shall now consider how this might be used as a way of starting from an answer we know only“approximately” modulo p to successively more accurate “higher degree” approximations modulopk. Eventually, for large enough k, these approximations will be complete. And if we have beenable to do this faster than by interpolation, we can save time. (For sparse problems, this is whathappens).The Hensel ConstructionOur major application for improving our approximations is to have a method of computingfrom a factorization of a polynomial in a finite field, a factorization of the polynomial in a largercomputation structure. Note that this is quite close to what we do when computing GCDs viathe modular algorithm, building up the image of the GCD to a polynomial of higher degree or apolynomial in more variables. The alternative we consider here is that given through the HenselAlgorithm, described here and first suggested for this application in reference [2].The original linear Hensel Construction lifts a factorization from mod pito mod pi+1at the ithstep while the more quadratic construction due to Zassenhaus lifts a factorization from mod p2ito mod p2i+1. Nevertheless, the linear version may require so much less computation at each stepthat it may be the algorithm of choice in lifting to a given modulus.The Linear Hensel AlgorithmLet u(x) be a monic1(leading coefficient = 1) polynomial in Z[x] and assume v1(x) · w1(x) =u(x) mod p and GCD(v1, w1) = 1 mod p where p is a prime. The algorithm computes a sequenceof pairs of polynomials ((vi, wi))i=1,...,nsuch thatvi(x) · wi(x) = u(x) mod piStep I1This assumption is, in general, unwarranted, and overcoming it makes the algorithm messy.Additional Notes on Polynomial GCDs, Hensel construction 4Compute by means of the Extended Euclidean Algorithm generalized to polynomials, two poly-nomials a(x) and b(x) in Zp[x] such that(i) deg(a) < deg(w1),(ii) deg(b) < deg(v1)(iii) (a(x)v1(x) + b(x)w1(x) = 1) mod pStep IINow suppose we are given
View Full Document