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 \ \equiv \ g \, h \ \mod{ m}$$ (26)

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

$$f \ \equiv \ \widehat{g} \, \widehat{h} \ \mod{ m^2}$$ (27)

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

$$s g + t h \ \equiv \ 1 \ \mod{ m}$$ (28)

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 1   A solution to the factorization lifting problem of Equation 27 is given by

$$\widehat{g} \ = \ g + t \, e \ \ {\rm and} \ \ \widehat{h} \ = \ h + s \, e \ \ {\rm where} \ \ e \ = \ f - g \, h$$ (29)

Proof. We have the following relations.

$$\begin{array}{rcll} f - \widehat{g} \widehat{h} & = & f - (g ... ... \, g + t \, h) \, e - s \, t\, e^2 & \mod{ m^2} \\ \end{array}$$ (30)

By hypothesis

$$e \ \equiv \ 0 \ \mod{m} \ \ \ \ \ \ {\rm and} \ \ \ \ \ \ (1 - s \, g + t \, h) \ \equiv \ 0 \ \mod{m}$$ (31)

Hence both $(1 - s \, g + t \, h) \, e$ and $e^2$ are mutiple of $m^2$ . It follows that

$$f - \widehat{g} \widehat{h} \ \equiv \ 0 \ \mod{m^2}$$ (32)

$\qedsymbol$

Remark 2   Observe that Proposition 1 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 1 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 1   Consider $f = x^4 - 1$ , $g = x -2$ , $h = x^3 + 2\, x^2 - 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 3   We see with Example 1 that the degrees of $\widehat{g}$ and $\widehat{h}$ are higher that those of $g$ and $h$ . In particular

$${\deg} \, \widehat{g} + {\deg} \, \widehat{h }\ > \ {\deg} \, f$$ (33)

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 2   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 \mod{m}$ then

$$q \equiv 0 \mod{m} \ \ \ \ {\rm and} \ \ \ \ r \equiv 0 \mod{m}$$ (34)

also hold.

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

$$a^{\ast} \ = \ q^{\ast} \, b + r^{\ast} \ \ \ \ {\rm and} \ \ \ \ {\deg} \, r^{\ast} \ < \ {\deg} \, b$$ (35)

Hence we have

$$a \ = \ m \, q^{\ast} \, b + m \, r^{\ast} \ \ \ \ {\rm and} \ \ \ \ {\deg} \, (m \, r^{\ast}) \ < \ {\deg} \, b$$ (36)

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

$$q \ = \ m \, q^{\ast} \ \ \ \ {\rm and} \ \ \ \ r \ = \ m \, r^{\ast}$$ (37)

$\qedsymbol$

Definition 2   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

• $f \ \equiv \ g \, h \ \mod{ m}$ ,
• $s \, g + t \, h \ \equiv \ 1 \ \mod{ m}$ ,
• $h$ is monic,
• ${\deg} \, f \ = \ {\deg} \, g + {\deg} \, h$ ,
• ${\deg} \, s \ < \ {\deg} \, h$ ,
• ${\deg} \, t \ < \ {\deg} \, g$ .

Algorithm 1  

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

Proof. We shall prove the following claims about $g^{\ast}$ and $h^{\ast}$ :

1. $f - g^{\ast} \, h^{\ast} \ \equiv \ 0 \ \mod{ m^2 }$ ,
2. $g^{\ast} \ \equiv \ g \ \mod{ m }$ ,
3. $h^{\ast} \ \equiv \ h\ \mod{ m }$ ,
4. $h^{\ast}$ monic and of the same degree as $h$ ,
5. $g^{\ast}$ of the same degree as $g$ .

We calculate modulo $m^2$ :

$$\begin{array}{rcl} f - g^{\ast} \, h^{\ast} & \equiv & f - (g... ... sg - th)(f - gh) -ste^2 + qe (th + sg) + gh q^2 \\ \end{array}$$ (38)

By assumption we have

• $1 - sg - th \ \equiv 0 \ \mod{ m }$
• $f - gh \ \equiv 0 \ \mod{ m }$

Moreover

$$e \ \equiv 0 \ \mod{ m } \ \ \ \ {\rm and} \ \ \ \ se \equiv qh + r \ \mod{ m^2 }$$ (39)

by Proposition 2 imply

$$q \ \equiv 0 \ \mod{ m }$$ (40)

This leads to

$$f - g^{\ast} \, h^{\ast} \ \equiv \ 0 \ \mod{ m^2 }.$$ (41)

Now the relation defining $g^{\ast}$

$$g^{\ast} \ = \ (q + t \, e + q \, g) \ \mod{ m^2}$$ (42)

together with $e \ \equiv \ 0 \ \mod{ m }$ and $q \ \equiv \ 0 \ \mod{ m }$ imply

$$g^{\ast} \ \equiv \ g \ \mod{ m }$$ (43)

Similarly we have

$$h^{\ast} \ \equiv \ h\ \mod{ m }$$ (44)

Now observe that by definition of $r$ we have

$${\deg}\, r \ < \ {\deg}\, h$$ (45)

Then since

$$h^{\ast} \ = \ (h + r) \ \mod{ m^2}$$ (46)

we obtain

$$h \ {\rm monic} \ \ \ \ {\rm and} \ \ \ \ {\deg}\, h \ = \ {\deg}\, h^{\ast}$$ (47)

These last relations together with

$$f \ \equiv \ g^{\ast} \, h^{\ast} \ \mod{ m^2 }$$ (48)

imply

$$\begin{array}{rcl} {\deg}\, g^{\ast} & = & {\deg}\, f - {\deg... ...\ & = & {\deg}\, f - {\deg}\, h \\ & = & {\deg}\, g \end{array}$$ (49)

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

Example 2   Consider $f = x^4 - 1$ , $g = x -2$ , $h = x^3 + 2\, x^2 - x - 2$ and $m = 5$ . Using Proposition 1 we computed

$$\widehat{g} \ = \ 15x^2 + x - 17 \ \ \ \ {\rm and} \ \ \ \ \widehat{h} \ = \ 10x^4 + 16x^3 + 12x^2 - 16x - 22$$ (50)

Now using the improved formula of Algorithm 1 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 6   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^{\ast}, h^{\ast}, s, t \in R[x]$ such that

1. $s g + t h \ {\equiv} \ 1 \ \mod{ m}$
2. the leading coefficients of $g$ and $h$ are not zero divisors modulo $m$
3. the polynomials $g$ and $g^{\ast}$ have the same leading coefficients, the same degree and coincide modulo $m$
4. the polynomials $h$ and $h^{\ast}$ have the same leading coefficients, the same degree and coincide modulo $m$
5. $g h \ \equiv \ g^{\ast} h^{\ast} \ \mod{ m^{\ell}}$

Then we have

$$g \ {\equiv} \ g^{\ast} \ \mod{ m^{\ell}} \ \ \ \ {\rm and} \ \ \ \ h \ {\equiv} \ h^{\ast} \ \mod{ m^{\ell}}$$ (51)

Proof. We assume to the contrary that

$$g \ {\not\equiv} \ g^{\ast} \ \mod{ m^{\ell}} \ \ \ \ {\rm or} \ \ \ \ h \ {\not\equiv} \ h^{\ast} \ \mod{ m^{\ell}}$$ (52)

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

$$g^{\ast} - g \ = \ u \, m^i \ \ \ \ {\rm and} \ \ \ \ h^{\ast} - h \ = \ v \, m^i$$ (53)

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

$$\begin{array}{rcl} 0 & {\equiv} & g^{\ast} h^{\ast} - g h \mo... ...st} - g) \\ & = & g^{\ast} v \, m^i + h u \, m^i \\ \end{array}$$ (54)

This means that $m^{\ell}$ divides $g^{\ast} v \, m^i + h u \, m^i$ . In other words there exist $w \in R[x]$ such that

$$(g^{\ast} v + h u) m^i \ = \ m^{\ell} \, w$$ (55)

Since $m$ is not a zero divisor in $R$ we have

$$(g^{\ast} v + h u) \ = \ m^{{\ell}-i} \, w$$ (56)

which implies

$$g^{\ast} v + h u \ {\equiv} \ 0 \mod{ m}$$ (57)

Recall also that we have

$$t h \ {\equiv} \ 1 - s g \mod{ m}$$ (58)

and

$$g^{\ast} \ {\equiv} \ g \mod{ m} \ \ \ \ {\rm and} \ \ \ \ h^{\ast} \ {\equiv} \ h \mod{ m}$$ (59)

Therefore we obtain the following calculation modulo $m$

$$\begin{array}{rcl} 0 & {\equiv} & t (g^{\ast} v + h u ) \\ & ... ...} v + (1 - s g) u \\ & {\equiv} & (t v - s u) g + u \end{array}$$ (60)

This shows that $g$ divides $u$ modulo $m$ . However from $g^{\ast} - g \ = \ u \, m^i$ together with the facts that $g^{\ast}$ and $g$ have same leading coefficient and degree shows that

$${\deg} \, u \ < \ {\deg} \, g$$ (61)

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

$$u \ {\equiv} \ 0 \mod{ m}$$ (62)

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