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

$$\phi$$ (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

$$\phi \equiv$$ (110)

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

$$\equiv \phi \phi \prime$$ (111)

Then the following assertions hold

1. $\phi$(h)  $\equiv$  0 modp²
2. h  $\equiv$  g modp
3. $\phi$^$\prime$(h) is invertible modulo p

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

Since p divides p², the following congruence holds

$$\equiv \phi \phi \prime$$ (112)

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

$$\equiv$$ (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 p² divides (h - g)² we obtain

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

(114)

proving the first claim. Finally, observe that h  $\equiv$  g modp implies $\phi$^$\prime$(h)  $\equiv$  $\phi$^$\prime$(g)modp. Indeed $\phi$^$\prime$ is a polynomial in R[x]. Therefore, $\phi$^$\prime$(h) is invertible modulo p, since $\phi$^$\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

• check whether $\phi$^$\prime$(g) is invertible modulo p and
• compute its inverse modulo p in case.

Then for computing the inverse of $\phi$^$\prime$(h) modulo p the idea is to apply the algorithm to itself! That is, to the particular case of

$$\phi$$ (115)

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

Algorithm 8  

Theorem 14   Algorithm 8 is correct.

Proof. Let g_r  $\equiv$  g_r-1 - $\phi$(g_r-1)s_r-1modp^2r. Then we have

$$\equiv \ell$$ (116)

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

1. g_i  $\equiv$  g₀modp,
2. $\phi$(g_i)  $\equiv$  0 modp²ⁱ,
3. if i < r then s_i $\phi$^$\prime$(g_i)  $\equiv$  1 modp²ⁱ.

The case i = 0 is clear and we assume that i > 0 holds. Then by induction hypothesis p^2i-1 divides $\phi$(g_i-1) and s_i-1 - $\phi$^$\prime$(g_i-1)^-1. Then p²ⁱ divides their product, that is

$$\phi \equiv \phi \phi \prime$$ (117)

Now we calculate

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

(118)

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

$$\equiv$$ (119)

for i < r. This implies

$$\phi \prime \equiv \phi \prime \equiv$$ (120)

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