Quadratic Newton Iteration

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

$${\phi}(g) \ = \ 0.$$ (29)

The following Proposition 8 states that Relation (31) computes better and better approximations of solutions of Relation (29) that is, approximations modulo higher and higher powers of $p$ . Comparing to the results of the previous section, this proposition offers a significant improvement: the accuracy doubles at each step, leading to the so-called Quadratic Symbolic Newton Iteration.

Proposition 8   Let ${\phi} \in R[y]$ and let $g \in R$ be such that

$${\phi}(g) \ {\equiv} \ 0 \mod{p}$$ (30)

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

$$h \ {\equiv} \ g - {\phi}(g) \, {{\phi}'(g)}^{-1} \mod{ p^{2}}$$ (31)

Then the following assertions hold:

1. ${\phi}(h) \ {\equiv} \ 0 \mod{ p^{2}}$ ,
2. $h \ {\equiv} \ g \mod{ p}$ ,
3. ${\phi}'(h)$ is invertible modulo $p$ , and thus modulo $p^2$ .

Proof. Since ${\phi}'(g)$ is invertible modulo $p$ then ${\phi}'(g)$ is invertible modulo $p^{2}$ . (This is easy to check: Exercise!) Hence Relation 31 makes sense. In fact, Algorithm  computes ${{\phi}'(g)}^{-1} \mod{ p^{2}}$ given ${{\phi}'(g)}^{-1} \mod{ p }$ .

Since $p$ divides $p^2$ , the following congruence holds

$$h \ {\equiv} \ g - {\phi}(g) \, {{\phi}'(g)}^{-1} \mod{ p}$$ (32)

Since ${\phi}(g) \ {\equiv} \ 0 \mod{p}$ , this leads to

$$h \ {\equiv} \ g \mod{ p}$$ (33)

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 $p^2$ divides $(h -g)^2$ we obtain

$$\begin{array}{rcl} {\phi}(h) & {\equiv} & {\phi}(g) + {{\phi}... ...g)}^{-1} \mod{ p^2} \\ & {\equiv} & 0 \mod{ p^2} \\ \end{array}$$ (34)

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

Remark 7   Intuitively, Proposition 8 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 8   Proposition 8 leads to an algorithm provided that we can

• check whether ${\phi}'(h)$ is invertible modulo $p$ and
• compute its inverse modulo $p$ in case.

Then for computing the inverse of ${\phi}'(g)$ modulo $p$ the idea is to apply the algorithm to itself! That is, to the particular case of

$${\phi}(g) \ = \ 1/g -f$$ (35)

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

Algorithm 1  

Theorem 3   Algorithm 1 is correct.

Proof. Let $g_r \ {\equiv} \ g_{r-1} - {\phi}(g_{r-1}) s_{r-1} \mod{p^{2^r}}$ . Then we have

$$g \ {\equiv} \ g_r \ \mod{ p^{\ell}}$$ (36)

In other words $g_r$ is a solution of higher precision. Then proving the theorem turns into proving the invariants for $i = 0 \cdots r$

1. $g_i \ {\equiv} \ g_0 \mod{ p}$ ,
2. ${\phi}(g_i) \ {\equiv} \ 0 \ \mod{ p^{2^i}}$ ,
3. if $i < r$ then $s_i \, {\phi}'(g_i) \ {\equiv} \ 1 \ \mod{ p^{2^i}}$ .

The case $i = 0$ is clear and we assume that $i > 0$ holds. Then by induction hypothesis $p^{2^{i-1}}$ divides ${\phi}(g_{i-1})$ and $s_{i-1} - {{\phi}'(g_{i-1})}^{-1}$ . Then $p^{2^i}$ divides their product, that is

$${\phi}(g_{i-1}) s_{i-1} \ {\equiv} \ {\phi}(g_{i-1}) {{\phi}'(g_{i-1})}^{-1} \ \mod{ p^{2^i}}.$$ (37)

Now we calculate

$$\begin{array}{rcl} g_i & {\equiv} & g_{i-1} - {\phi}(g_{i-1})... ...g_{i-1}) {{\phi}'(g_{i-1})}^{-1} \ \mod{p^{2^i}} \\ \end{array}$$ (38)

Now applying Proposition 8 with $g = g_{i-1}$ , $h = g_i$ and $m = p^{2^{i-1}}$ we obtain the first two invariants. In addition, this leads to

$$g_i \ \equiv \ g_{i-1} \ \mod{ p^{2^{i-1}} }$$ (39)

for $i < r$ . This implies

$${{\phi}'(g_i)}^{-1} \ \equiv \ {{\phi}'(g_{i-1})}^{-1} \ \equiv \ s_{i-1} \ \mod{ p^{2^{i-1}} }$$ (40)

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