Let be a commutative ring with units. Let and . We are concerned with solving the equation

 (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 . 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 and let be such that

 (30)

Assume that is invertible modulo and let denote by its inverse. Consider an element such that

 (31)

Then the following assertions hold:
1. ,
2. ,
3. is invertible modulo , and thus modulo .

Proof. Since is invertible modulo then is invertible modulo . (This is easy to check: Exercise!) Hence Relation 31 makes sense. In fact, Algorithm  computes given .

Since divides , the following congruence holds

 (32)

 (33)

and we have proved the second claim. Let us prove the first one. Using the Taylor expansion of at and the fact that divides we obtain

 (34)

proving the first claim. Finally, observe that implies . Indeed is a polynomial in . Therefore, is invertible modulo , since is invertible modulo , by hypothesis.

Remark 7   Intuitively, Proposition 8 says that if is a good approximation of a zero of then is a better approximation, at least twice as accurate.

Remark 8   Proposition 8 leads to an algorithm provided that we can
• check whether is invertible modulo and
• compute its inverse modulo in case.
Then for computing the inverse of modulo the idea is to apply the algorithm to itself! That is, to the particular case of

 (35)

This leads to Algorithm 1. Finally recall that for a prime element in an Euclidean domain , the computation of modulo can be done by the Extended Euclidean Algorithm.

Algorithm 1

Theorem 3   Algorithm 1 is correct.

Proof. Let . Then we have

 (36)

In other words is a solution of higher precision. Then proving the theorem turns into proving the invariants for
1. ,
2. ,
3. if then .
The case is clear and we assume that holds. Then by induction hypothesis divides and . Then divides their product, that is

 (37)

Now we calculate

 (38)

Now applying Proposition 8 with , and we obtain the first two invariants. In addition, this leads to

 (39)

for . This implies

 (40)

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

Marc Moreno Maza
2008-01-07