next up previous
Next: Hensel Lifting Up: Symbolic Newton Iteration Previous: Linear Newton Iteration

Quadratic Newton Iteration

Let R be a commutative ring R with units. Let p $ \in$ R and $ \phi$ $ \in$ R[y]. We are concerned with solving the equation

$\displaystyle \phi$(g)  =  0. (109)

The following Proposition 15 states that Relation (111) computes better and better approximations of solutions of Relation (109) that is, approximations modulo higher and higher powers of p. W.r.t. Theorem 12 this proposition offers a significant improvement: the accuracy doubles at each step, leading to the so-called Quadratic Symbolic Newton Iteration.

Proposition 15   Let $ \phi$ $ \in$ R[y] and let g, h $ \in$ R be such that

$\displaystyle \phi$(g$\displaystyle \equiv$  0 modp (110)

Assume that $ \phi$$\scriptstyle \prime$(g) is invertible modulo p and let denote by $ \phi$$\scriptstyle \prime$(g)-1 its inverse. Consider an element h $ \in$ R such that

h  $\displaystyle \equiv$  g - $\displaystyle \phi$(g$\displaystyle \phi$$\scriptstyle \prime$(g)-1modp2 (111)

Then the following assertions hold
  1. $ \phi$(h$ \equiv$  0 modp2
  2. h  $ \equiv$  g modp
  3. $ \phi$$\scriptstyle \prime$(h) is invertible modulo p

Proof. Since $ \phi$$\scriptstyle \prime$(g) is invertible modulo p then $ \phi$$\scriptstyle \prime$(g) is invertible modulo p2. (This is easy to check: Exercise!) Hence Relation 111 makes sense. In fact, Algorithm 6 computes $ \phi$$\scriptstyle \prime$(g)-1modp2 given $ \phi$$\scriptstyle \prime$(g)-1modp.

Since p divides p2, the following congruence holds

h  $\displaystyle \equiv$  g - $\displaystyle \phi$(g$\displaystyle \phi$$\scriptstyle \prime$(g)-1modp (112)

Since $ \phi$(g$ \equiv$  0 modp, this leads to

h  $\displaystyle \equiv$  g modp (113)

and we have proved the second claim. Let us prove the first one. Using the Taylor expansion of $ \phi$ at h and the fact that p2 divides (h - g)2 we obtain

$\displaystyle \phi$(h) $\displaystyle \equiv$ $\displaystyle \phi$(g) + $\displaystyle \phi$$\scriptstyle \prime$(g)(h - g)modp2
  $\displaystyle \equiv$ $\displaystyle \phi$(g) - $\displaystyle \phi$$\scriptstyle \prime$(g)$\displaystyle \phi$(g$\displaystyle \phi$$\scriptstyle \prime$(g)-1modp2
  $\displaystyle \equiv$ 0 modp2

proving the first claim. Finally, observe that h  $ \equiv$  g modp implies $ \phi$$\scriptstyle \prime$(h$ \equiv$  $ \phi$$\scriptstyle \prime$(g)modp. Indeed $ \phi$$\scriptstyle \prime$ is a polynomial in R[x]. Therefore, $ \phi$$\scriptstyle \prime$(h) is invertible modulo p, since $ \phi$$\scriptstyle \prime$(g) is invertible modulo p, by hypothesis.

$ \qedsymbol$

Remark 21   Intuitively, Proposition 15 says that if g is a good approximation of a zero of $ \phi$ then h is a better approximation, at least twice as accurate.

Remark 22   Proposition 15 leads to an algorithm provided that we can Then for computing the inverse of $ \phi$$\scriptstyle \prime$(h) modulo p the idea is to apply the algorithm to itself! That is, to the particular case of

$\displaystyle \phi$(g)  =  1/g - f (115)

This leads to Algorithm 8. Finally recall that for a prime element p in an Euclidean domain R, the computation of $ \phi$$\scriptstyle \prime$(g)-1 modulo p can be done by the Extended Euclidean Algorithm.

Algorithm 8  

\begin{minipage}{12 cm}
\item[{\bf Input:}] ${\ell} \...
...}) s_{r-1} \mod{ p^{\ell}}$\ \\
\> {\bf return} $g$\end{tabbing}\end{minipage}}

Theorem 14   Algorithm 8 is correct.

Proof. Let gr  $ \equiv$  gr-1 - $ \phi$(gr-1)sr-1modp2r. Then we have

g  $\displaystyle \equiv$  gr modp$\scriptstyle \ell$ (116)

In other words gr is a solution of higher precision. Then proving the theorem turns into proving the invariants for i = 0 ... r
  1. gi  $ \equiv$  g0modp,
  2. $ \phi$(gi$ \equiv$  0 modp2i,
  3. if i < r then si $ \phi$$\scriptstyle \prime$(gi$ \equiv$  1 modp2i.
The case i = 0 is clear and we assume that i > 0 holds. Then by induction hypothesis p2i-1 divides $ \phi$(gi-1) and si-1 - $ \phi$$\scriptstyle \prime$(gi-1)-1. Then p2i divides their product, that is

$\displaystyle \phi$(gi-1)si-1  $\displaystyle \equiv$  $\displaystyle \phi$(gi-1)$\displaystyle \phi$$\scriptstyle \prime$(gi-1)-1 modp2i. (117)

Now we calculate

gi $\displaystyle \equiv$ gi-1 - $\displaystyle \phi$(gi-1)si-1 modp2i
  $\displaystyle \equiv$ gi-1 - $\displaystyle \phi$(gi-1)$\displaystyle \phi$$\scriptstyle \prime$(gi-1)-1 modp2i

Now applying Proposition 15 with g = gi-1, h = gi and m = p2i-1 we obtain the first two invariants. In addition, this leads to

gi  $\displaystyle \equiv$  gi-1 modp2i-1 (119)

for i < r. This implies

$\displaystyle \phi$$\scriptstyle \prime$(gi)-1  $\displaystyle \equiv$  $\displaystyle \phi$$\scriptstyle \prime$(gi-1)-1  $\displaystyle \equiv$  si-1 modp2i-1 (120)

Now, si is obtained by one Newton step for inversion (see Algorithm 6). Therefore the third invariant follows. $ \qedsymbol$

next up previous
Next: Hensel Lifting Up: Symbolic Newton Iteration Previous: Linear Newton Iteration
Marc Moreno Maza