next up previous
Next: Bibliography Up: Hensel Lifting Previous: Linear Hensel Lifting

Quadratic Hensel Lifting

Let R be a commutative ring with identity element. Let f, g, h be univariate polynomials in R[x] and let m $ \in$ R. We assume that the following relation holds

f  $\displaystyle \equiv$  g h modm (146)

We aim to lift this factorization modulo m into a factorization modulo m2. Hence we want to compute $ \widehat{{g}}$ and $ \widehat{{h}}$ such that

f  $\displaystyle \equiv$  $\displaystyle \widehat{{g}}$ $\displaystyle \widehat{{h}}$ modm2 (147)

We will refer to this problem as the factorization lifting problem. To do so we will assume that we are given two polynomials s and t such that

sg + th  $\displaystyle \equiv$  1 modm (148)

Hence we will say that g and h are coprime modulo m. When R/m is a field then we can compute s and t by applying the Extended Euclidean Algorithm in R[x]/m.


Proposition 16   A solution to the factorization lifting problem of Equation 147 is given by

$\displaystyle \widehat{{g}}$  =  g + t e  and  $\displaystyle \widehat{{h}}$  =  h + s e  where  e  =  f - g h (149)


Proof. We have the following relations.

f - $\displaystyle \widehat{{g}}$$\displaystyle \widehat{{h}}$ = f - (g + t e) (h + s e)  
  = f - g h - g s e - h t e - s t e2  
  = e - (s g + t h) e - s t e2  
  = (1 - s g + t h) e - s t e2  
  $\displaystyle \equiv$ (1 - s g + t h) e - s t e2 modm2
(150)

By hypothesis

e  $\displaystyle \equiv$  0 modm      and      (1 - s g + t h)  $\displaystyle \equiv$  0 modm (151)

Hence both (1 - s g + t h) e and e2 are mutiple of m2. It follows that

f - $\displaystyle \widehat{{g}}$$\displaystyle \widehat{{h}}$  $\displaystyle \equiv$  0 modm2 (152)

$ \qedsymbol$


Remark 24   Observe that Proposition 16 works also if f, g, h are constants of R. In other words, f, g, h do not need to be polynomials! The factorization lifting problem and its solution by Proposition 16 are valid in any commutative ring with identity element. But for this solution to be an algorithm one needs to be able to compute the Bézout coefficients s and t.

Example 7   Consider f = x4 - 1, g = x - 2, h = x3 + 2 x2 - x - 2 and m = 5. We have the following computation in AXIOM 
N := NonNegativeInteger
 

   (1)  NonNegativeInteger
                                            Type: Domain

Z := Integer
 

   (2)  Integer
                                              Type: Domain

U := UnivariatePolynomial(x,Z)
 

   (3)  UnivariatePolynomial(x,Integer)
                                              Type: Domain

m: Z := 5
 

   (4)  5
                                             Type: Integer

f: U := x^4 - 1
 

         4
   (5)  x  - 1
                      Type: UnivariatePolynomial(x,Integer)

g: U := x - 2
 

   (6)  x - 2
                      Type: UnivariatePolynomial(x,Integer)

h: U := x^3 + 2 *x^2 -x -2
 

         3     2
   (7)  x  + 2x  - x - 2
                      Type: UnivariatePolynomial(x,Integer)

e := f - g*h
 

          2
   (8)  5x  - 5
                      Type: UnivariatePolynomial(x,Integer)

K5 := PrimeField(5)
 

   (9)  PrimeField 
                                               Type: Domain

U5 := UnivariatePolynomial(x,K5)
 

   (10)  UnivariatePolynomial(x,PrimeField 5)
                                                Type: Domain

f5: U5 := f :: U5
 

          4
   (11)  x  + 4
                   Type: UnivariatePolynomial(x,PrimeField 5)

g5: U5 := g :: U5
 

   (12)  x + 3
                   Type: UnivariatePolynomial(x,PrimeField 5)

h5: U5 := h ::U5
 

          3     2
   (13)  x  + 2x  + 4x + 3
                    Type: UnivariatePolynomial(x,PrimeField 5)

res := extendedEuclidean(g5,h5)

                   2
   (14)  [coef1= 2x  + 3x + 4,coef2= 3,generator= 1]

s5: U5 := res.coef1
 

           2
   (15)  2x  + 3x + 4
                    Type: UnivariatePolynomial(x,PrimeField 5)

t5: U5 := res.coef2
 

   (16)  3
                    Type: UnivariatePolynomial(x,PrimeField 5)

g_^ := g + t5 :: U * e
 

            2
   (17)  15x  + x - 17
                         Type: UnivariatePolynomial(x,Integer)

h_^ := h + s5 :: U * e
 

            4      3      2
   (18)  10x  + 16x  + 12x  - 16x - 22
                         Type: UnivariatePolynomial(x,Integer)

factor(f -  g_^  * h_^ )
 

                              4      3     2
   (19)  - 25(x - 1)(x + 1)(6x  + 10x  + 7x  - 10x - 15)
                Type: Factored UnivariatePolynomial(x,Integer)

Remark 25   We see with Example 7 that the degrees of $ \widehat{{g}}$ and $ \widehat{{h}}$ are higher that those of g and h. In particular

deg $\displaystyle \widehat{{g}}$ + deg $\displaystyle \widehat{{h}}$  >  deg f (153)

which may not look satisfactory! To overcome this problem we need to use division with remainder in R[x]. We will take advantage of the following.


Proposition 17   Let a and b be in R[x] such that b is monic. Let q and r be the quotient and the remainder of a w.r.t. b. Let m be in R. If a $ \equiv$ 0 modm then

q $\displaystyle \equiv$ 0 modm    and    r $\displaystyle \equiv$ 0 modm (154)

also hold.


Proof. There exists a * $ \in$ R[x] such that a = m a * . Let q * and r * be the quotient and the remainder of a * w.r.t. b. Then we have

a *   =  q *  b + r *     and    deg r *   <  deg b (155)

Hence we have

a  =  m q *  b + m r *     and    deg (m r * )  <  deg b (156)

Since the quotient and the remainder of a w.r.t. b are unique we have

q  =  m q *     and    r  =  m r * (157)

$ \qedsymbol$

Definition 11   Let f, g, h, s, t be polynomials in R[x] and let m $ \in$ R. We say that (f, g, h, s, t) is a liftable quintet modulo m if the following conditions hold

Algorithm 9  

\fbox{ \begin{minipage}{12 cm} \begin{description} \item[{\bf Input:}] $f,g,h,s,... ...rn} $(g^{\ast}, h^{\ast}, s^{\ast}, t^{\ast})$\ \\ \end{tabbing}\end{minipage}}

Theorem 18   Algorithm 9 works correctly. Let n = deg f. If R = $ \mbox{${\mathbb Z}$}$ and all input polynomials have max-norm less than m2 then it requires $ \cal {O}$($ \bf M$(n) $ \bf M$(log m)) word operations.

Proof. We shall prove the following claims about g * and h * :
  1. f - g *  h *   $ \equiv$  0 modm2,
  2. g *   $ \equiv$  g modm,
  3. h *   $ \equiv$  h modm,
  4. h * monic and of the same degree as h,
  5. g * of the same degree as g.
We calculate modulo m2:

f - g *  h * $\displaystyle \equiv$ f - (g + te + qg)(h + se - qh)
  = f - gh - gse + gqh - teh - tese + teqh - qgh - qgse + qgqh
  = f - gh - gse - teh - tese + teqh - qgse + qgqh
  = e - (sg + th)e - ste2 + qe(th + sg) + ghq2
  = (1 - sg - th)(f - gh) - ste2 + qe(th + sg) + ghq2
(158)

By assumption we have Moreover

e  $\displaystyle \equiv$ 0 modm    and    se $\displaystyle \equiv$ qh + r modm2 (159)

by Proposition 17 imply

q  $\displaystyle \equiv$ 0 modm (160)

This leads to

f - g *  h *   $\displaystyle \equiv$  0 modm2. (161)

Now the relation defining g *

g *   =  (q + t e + q g) modm2 (162)

together with e  $ \equiv$  0 modm and q  $ \equiv$  0 modm imply

g *   $\displaystyle \equiv$  g modm (163)

Similarly we have

h *   $\displaystyle \equiv$  h modm (164)

Now observe that by definition of r we have

deg r  <  deg h (165)

Then since

h *   =  (h + r) modm2 (166)

we obtain

h monic    and    deg h  =  deg h * (167)

These last relations together with

f  $\displaystyle \equiv$  g *  h *  modm2 (168)

imply

deg g * = deg f - deg h *
  = deg f - deg h
  = deg g
(169)

This concludes this proof. We refer to Theorem 15.11 in [vzGG99] for the other claims of the theorem. $ \qedsymbol$

Example 8   Consider f = x4 - 1, g = x - 2, h = x3 + 2 x2 - x - 2 and m = 5. Using Proposition 16 we computed

$\displaystyle \widehat{{g}}$  =  15x2 + x - 17    and    $\displaystyle \widehat{{h}}$  =  10x4 + 16x3 + 12x2 - 16x - 22 (170)

Now using the improved formula of Algorithm 9 we have the following AXIOM session 
N := NonNegativeInteger
 

   (1)  NonNegativeInteger
                                            Type: Domain

Z := Integer
 

   (2)  Integer
                                            Type: Domain

U := UnivariatePolynomial(x,Z)
 

   (3)  UnivariatePolynomial(x,Integer)
                                            Type: Domain

m: Z := 5
 

   (4)  5
                                           Type: Integer

f: U := x^4 - 1
 

         4
   (5)  x  - 1
                   Type: UnivariatePolynomial(x,Integer)

g: U := x - 2
 

   (6)  x - 2
                   Type: UnivariatePolynomial(x,Integer)

h: U := x^3 + 2 *x^2 -x -2
 

         3     2
   (7)  x  + 2x  - x - 2
                   Type: UnivariatePolynomial(x,Integer)

e := f - g*h
 

          2
   (8)  5x  - 5
                   Type: UnivariatePolynomial(x,Integer)

K5 := PrimeField(5)
 

   (9)  PrimeField 5
                                            Type: Domain

U5 := UnivariatePolynomial(x,K5)
 

   (10)  UnivariatePolynomial(x,PrimeField 5)
                                            Type: Domain

f5: U5 := f :: U5
 

          4
   (11)  x  + 4
              Type: UnivariatePolynomial(x,PrimeField 5)

g5: U5 := g :: U5
 

   (12)  x + 3
              Type: UnivariatePolynomial(x,PrimeField 5)

h5: U5 := h ::U5
 

          3     2
   (13)  x  + 2x  + 4x + 3
              Type: UnivariatePolynomial(x,PrimeField 5)

res := extendedEuclidean(g5,h5)
 

                   2
   (14)  [coef1= 2x  + 3x + 4,coef2= 3,generator= 1]
Type: Record(coef1: UnivariatePolynomial(x,PrimeField 5),
coef2: UnivariatePolynomial(x,PrimeField 5),
generator: UnivariatePolynomial(x,PrimeField 5))

s5: U5 := res.coef1
 

           2
   (15)  2x  + 3x + 4
              Type: UnivariatePolynomial(x,PrimeField 5)

s: U := s5 :: U
 

           2
   (16)  2x  + 3x + 4
                   Type: UnivariatePolynomial(x,Integer)

t5: U5 := res.coef2
 

   (17)  3
              Type: UnivariatePolynomial(x,PrimeField 5)

t: U := t5 :: U
 

   (18)  3
                   Type: UnivariatePolynomial(x,Integer)

R25 := IntegerMod(25)
 

   (19)  IntegerMod 25
                                            Type: Domain

U25 := UnivariatePolynomial(x,R25)
 

   (20)  UnivariatePolynomial(x,IntegerMod 25)
                                            Type: Domain

e25 := f::U25 - g::U25 * h::U25
 

           2
   (21)  5x  + 20
             Type: UnivariatePolynomial(x,IntegerMod 25)

e : U := e25 :: U
 

           2
   (22)  5x  + 20
                   Type: UnivariatePolynomial(x,Integer)

res := monicDivide(s*e, h)
 

                                          2
   (23)  [quotient= 10x - 5,remainder= 80x  + 75x + 70]
Type: Record(quotient: UnivariatePolynomial(x,Integer),
             remainder: UnivariatePolynomial(x,Integer))

q25: U25 := res.quotient :: U25
 

   (24)  10x + 20
             Type: UnivariatePolynomial(x,IntegerMod 25)

r25: U25 := res.remainder :: U25
 

           2
   (25)  5x  + 20
             Type: UnivariatePolynomial(x,IntegerMod 25)

g_* := (g::U25 + t::U25 * e25 + q25 * (g::U25)) :: U
 

   (26)  x + 18
                   Type: UnivariatePolynomial(x,Integer)

h_* := (h::U25 + r25) :: U
 

          3     2
   (27)  x  + 7x  + 24x + 18
                   Type: UnivariatePolynomial(x,Integer)

(f - g_* * h_*) :: U25
 

   (28)  0
             Type: UnivariatePolynomial(x,IntegerMod 25)

Theorem 19   Let R be a commutative ring with identity element, an element m $ \in$ R which is not a zero divisor, an integer $ \ell$ $ \in$ $ \mbox{${\mathbb N}$}$ and nonzero univariate polynomials g, h, g * , h * , s, t $ \in$ R[x] such that
  1. sg + th  $ \equiv$  1 modm
  2. the leading coefficients of g and h are not zero divisors modulo m
  3. the polynomials g and g * have the same leading coefficients, the same degree and coincide modulo m
  4. the polynomials h and h * have the same leading coefficients, the same degree and coincide modulo m
  5. gh  $ \equiv$  g * h *  modm$\scriptstyle \ell$
Then we have

g  $\displaystyle \equiv$  g *  modm$\scriptstyle \ell$    and    h  $\displaystyle \equiv$  h *  modm$\scriptstyle \ell$ (171)

Proof. We assume to the contrary that

g  $\displaystyle \not\equiv$ g *  modm$\scriptstyle \ell$    or    h  $\displaystyle \not\equiv$ h *  modm$\scriptstyle \ell$ (172)

Let 1 $ \leq$ i < $ \ell$ be maximal such that mi both divides g * - g and h * - h. Thus there exist polynomials u, v $ \in$ R[x] such that

g * - g  =  u mi    and    h * - h  =  v mi (173)

and also m does not divide u or v. We may assume that m does not divide u. Now we have

0 $\displaystyle \equiv$ g * h * - gh modm$\scriptstyle \ell$
  = g * (h * - h) + h(g * - g)
  = g * v mi + hu mi
(174)

This means that m$\scriptstyle \ell$ divides g * v mi + hu mi. In other words there exist w $ \in$ R[x] such that

(g * v + hu)mi  =  m$\scriptstyle \ell$ w (175)

Since m is not a zero divisor in R we have

(g * v + hu)  =  m$\scriptstyle \ell$-i w (176)

which implies

g * v + hu  $\displaystyle \equiv$  0 modm (177)

Recall also that we have

th  $\displaystyle \equiv$  1 - sg modm (178)

and

g *   $\displaystyle \equiv$  g modm    and    h *   $\displaystyle \equiv$  h modm (179)

Therefore we obtain the following calculation modulo m

0 $\displaystyle \equiv$ t(g * v + hu)
  $\displaystyle \equiv$ tg * v + thu
  $\displaystyle \equiv$ tg * v + (1 - sg)u
  $\displaystyle \equiv$ (tv - su)g + u
(180)

This shows that g divides u modulo m. However from g * - g  =  u mi together with the facts that g * and g have same leading coefficient and degree shows that

deg u  <  deg g (181)

Since the leading coefficient of g is not a zero divisor modulo m we must have

u  $\displaystyle \equiv$  0 modm (182)

A contradiction. Therefore the theorem is proved. $ \qedsymbol$

next up previous
Next: Bibliography Up: Hensel Lifting Previous: Linear Hensel Lifting
Marc Moreno Maza
2004-04-27