Next: Division with remainder using Newton Up: Division with remainder using Newton Previous: The quotient as a modular

## Modular inverses using Newton iteration

Let R be a commutative ring with unity. Given f R[x] and such that f (0) = 1 compute the polynomials g R[x] such that

 f g   1 modx  and  deg g < . (71)

In Proposition 7 we observe that there if there is a solution, then it is unique.

Proposition 7   If Equation (71) has a solution g R[x] with degree less than then it is unique.

Proof. Indeed, let g1 and g2 be solutions of Equation (71). Then the product f (g1 - g2) is a multiple of x. Since f (0) = 1 then g1(0) - g2(0) must be 0. Hence there is a constant c R and polynomials h1, h2 with degree less than - 1 such that

 g1(x)  =  h1(x) x + c  and  g2(x)  =  h2(x) x + c (72)

It follows that f (h1 - h2) is a multiple of x-1. By repeating the same argument we show that h1(0) = h2(0). Then by induction on we obtain g1 = g2.

Remark 12   Because of modx a solution of Equation (71) can be viewed as an approximation of a more general problem. Think of truncated Taylor expansions! So let us recall from numerical analysis the celebrated Newton iteration and let (g) = 0 be an equation that we want to solve, where a : is a differentiable function. From a suitable initial approximation g0, the sequence, called Newton iteration step,

 gi+1  =  gi - (73)

allows to compute subsequent approximations and converge toward a desired solution. In our case we have (g) = 1/g - f and the Newton iteration step is

 gi+1  =  gi -   =  2gi - f gi2. (74)

Theorem 9   Let R be a commutative ring with unity. Let f be a polynomial in R[x] such that f (0) = 1. Let g0, g1, g2,... be the sequence of polynomials defined for all i 0 by

 (75)

Then for i 0 we have

 f gi   1 modx2i (76)

Proof. By induction on i 0. For i = 0 we have x2i = x and thus

 f gi   f (0) g0   1 × 1   1 modx2i (77)

For the induction step we have

 1 - f gi+1 1 - f (2gi - f gi2) modx2i+1 1 - 2 f gi + f2 gi2 modx2i+1 (1 - f gi)2 modx2i+1 0 modx2i+1
(78)

Indeed f gi   1 modx2i means that x2i divides 1 - f gi. Thus x2i+1 = x2i+2i = x2i x2i divides (1 - f gi)2.

Algorithm 6

Notation 1   We denote by (n) an upper bound for the number of operations in R required to multiply two polynomials of R[x] with degree less than n. We know that M(n) = 2 n2 is such a bound. Moreover if n is a power of 2, say 2r, and if R possesses primitive 2r+1-th roots of unity, then we can choose M(n) = (n log n).

Theorem 10   Algorithm 6 computes the inverse of f modulo x. Moreover, if be a power of 2, then Algorithm 6 requires (()) operations in R.

Proof. Theorem 9 tell us that Algorithm 6 computes the inverse of f modulo x2r. Since x divides x2r, the result is also valid modulo x. We do not give here a proof of the complexity result and we refer to Theorem 9.4 in [vzGG99]. In fact we prefer to give a very brutal explanation about it.

To understand the complexity result one needs to point out the following relation for i = 1 ... r.

 gi   gi-1 modx2i-1 (79)

Indeed, by virtue of Theorem 9 we have

 gi 2gi-1 - f gi-12 modx2i 2gi-1 - f gi-12 modx2i-1 gi-1(2 - f gi-1) modx2i-1 gi-1(2 - 1) modx2i-1 gi-1 modx2i-1
(80)

Therefore when computing gi we only to care about power of x in the range x2i-1 ... x2i. This says that
• half of the computation of gr is made during the last iteration of the for loop,
• a quater is made when computing gr-1 etc.
Now recall that

 + + + ...   =  1 (81)

So roughly the cost of the algorithm is in the order of magnitude of the cost of the last iteration. which consists of
• two multiplications of polynomials with degree less than 2r,
• a multiplication of a polynomial (with degree less than 2r) by a constant,
• truncations modulo x2r
• a subtraction of polynomials with degree less than 2r.
leading to ((2r)) operations in R.

Remark 13   Once again in Algorithm 6 for i = 1 ... r we have

 gi   gi-1 modx2i-1 (82)

So when implementing Algorithm 6 one should be extremely careful in not recomputing the low terms of gi that come from gi-1.

Remark 14   Algorithm 6 can be adapted to the case where f (0) is a unit different from 1 by initializing g0 to the inverse of f (0) instead of 1. If f (0) is not a unit, then no inverse of f modulo x exists. Indeed f g 1 modx implies f (0)g(0) = 1 which says that f (0) is a unit.

Next: Division with remainder using Newton Up: Division with remainder using Newton Previous: The quotient as a modular
Marc Moreno Maza
2003-06-06