Modular inverses using Newton iteration

Let R be a commutative ring with identity element. Given f $\in$ R[x] and $\ell$ $\in$ $\mbox{${\mathbb N}$}$ such that f (0) = 1 compute the polynomials g $\in$ R[x] such that

$$\equiv \ell \ell$$ (71)

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

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

Proof. Indeed, let g₁ and g₂ be solutions of Equation (71). Then the product f (g₁ - g₂) is a multiple of x^$\ell$. Since f (0) = 1 then g₁(0) - g₂(0) must be 0. Hence there is a constant c $\in$ R and polynomials h₁, h₂ with degree less than $\ell$ - 1 such that

g₁(x)  =  h₁(x) x + c  and  g₂(x)  =  h₂(x) x + c (72)

It follows that f (h₁ - h₂) is a multiple of x^$\ell$-1. By repeating the same argument we show that h₁(0) = h₂(0). Then by induction on $\ell$ we obtain g₁ = g₂. $\qedsymbol$

Remark 12   Since Equation (71) is an equation in R[x]/$\langle$x^$\ell$$\rangle$, a solution of this equation an 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 $\phi$(g) = 0 be an equation that we want to solve, where a $\phi$ : $\mbox{${\mathbb R}$}$ $\longmapsto$ $\mbox{${\mathbb R}$}$ is a differentiable function. From a suitable initial approximation g₀, the sequence, called Newton iteration step,

$${\frac{{{\phi}(g_i)}}{{{\phi}'(g_{i})}}}$$ (73)

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

$${\frac{{ 1/g_i - f}}{{ - 1/{g_i}^2}}}$$ (74)

Theorem 9   Let R be a commutative ring with identity element. Let f be a polynomial in R[x] such that f (0) = 1. Let g₀, g₁, g₂,... be the sequence of polynomials defined for all i $\geq$ 0 by

$$\left\{\vphantom{ \begin{array}{rcl} g_0 & = & 1 \\ g_{i+1} & \equiv & 2 g_i - f \, {g_i}^2 \ \mod{x^{2^{i+1}}} \end{array} }\right. \begin{array}{rcl} g_0 & = & 1 \\ g_{i+1} & \equiv & 2 g_i - f \, {g_i}^2 \ \mod{x^{2^{i+1}}} \end{array}$$ (75)

Then for i $\geq$ 0 we have

$$\equiv$$ (76)

Proof. By induction on i $\geq$ 0. For i = 0 we have x²ⁱ = x and thus

$$\equiv \equiv \equiv$$ (77)

For the induction step we have

1 - f gi+1	$$\equiv$$	1 - f (2gi - f gi2)	modx2i+1
	$$\equiv$$	1 - 2 f gi + f2 gi2	modx2i+1
	$$\equiv$$	(1 - f gi)2	modx2i+1
	$$\equiv$$	0	modx2i+1

(78)

Indeed f g_i  $\equiv$  1 modx²ⁱ means that x²ⁱ divides 1 - f g_i. Thus x²ⁱ⁺¹ = x²ⁱ⁺²ⁱ = x²ⁱ x²ⁱ divides (1 - f g_i)². $\qedsymbol$

Algorithm 6  

Notation 1   We denote by $\bf M$(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 n² is such a bound. Moreover if n is a power of 2, say 2^r, and if R possesses primitive 2^r+1-th roots of unity, then we can choose M(n) = $\cal {O}$(n log n).

Theorem 10   Algorithm 6 computes the inverse of f modulo x^$\ell$. Moreover, if $\ell$ be a power of 2, then Algorithm 6 requires $\cal {O}$($\bf M$($\ell$)) operations in R.

Proof. Theorem 9 tell us that Algorithm 6 computes the inverse of f modulo x^2r. Since x^$\ell$ divides x^2r, the result is also valid modulo x^$\ell$. 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.

$$\equiv$$ (79)

Indeed, by virtue of Theorem 9 we have

gi	$$\equiv$$	2gi-1 - f gi-12	modx2i
	$$\equiv$$	2gi-1 - f gi-12	modx2i-1
	$$\equiv$$	gi-1(2 - f gi-1)	modx2i-1
	$$\equiv$$	gi-1(2 - 1)	modx2i-1
	$$\equiv$$	gi-1	modx2i-1

(80)

Therefore when computing g_i we only care about power of x in the range x^{2i-1 ...} x²ⁱ. This says that

• half of the computation of g_r is made during the last iteration of the for loop,
• a quater is made when computing g_r-1 etc.

Now recall that

$${\frac{{1}}{{2}}} {\frac{{1}}{{4}}} {\frac{{1}}{{8}}}$$ (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 2^r,
• a multiplication of a polynomial (with degree less than 2^r) by a constant,
• truncations modulo x^2r
• a subtraction of polynomials with degree less than 2^r.

leading to $\cal {O}$($\bf M$(2^r)) operations in R. $\qedsymbol$

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

$$\equiv$$ (82)

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

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