Modular inverses using Newton iteration

f g $\displaystyle \equiv$ 1 modx and deg g < $\displaystyle \ell$ .

(71)

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. 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^-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 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 $\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,

g_i+1 = g_i - $\displaystyle {\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

g_i+1 = g_i - $\displaystyle {\frac{{ 1/g_i - f}}{{ - 1/{g_i}^2}}}$ = 2g_i - f g_i².

(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 g₀, g₁, g₂,... be the sequence of polynomials defined for all i $\geq$ 0 by

$\displaystyle \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.$ $\displaystyle \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

f g_i $\displaystyle \equiv$ 1 modx^2ⁱ

(76)

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

f g_i $\displaystyle \equiv$ f (0) g₀ $\displaystyle \equiv$ 1 × 1 $\displaystyle \equiv$ 1 modx^2ⁱ

(77)

For the induction step we have

1 - f g_i+1	$\displaystyle \equiv$	1 - f (2g_i - f g_i²)	modx^2ⁱ⁺¹
	$\displaystyle \equiv$	1 - 2 f g_i + f² g_i²	modx^2ⁱ⁺¹
	$\displaystyle \equiv$	(1 - f g_i)²	modx^2ⁱ⁺¹
	$\displaystyle \equiv$	0	modx^2ⁱ⁺¹

(78)

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

Algorithm 6

$\fbox{ \begin{minipage}{10 cm} \begin{description} \item[{\bf Input:}] $f \in R[... ...) \ \mod{x^{2^i}} $\ \\ \> {\bf return} $g_r$\ \\ \end{tabbing}\end{minipage}}$

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. 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^{2^r}. Since x divides x^{2^r}, 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.

g_i $\displaystyle \equiv$ g_i-1 modx^{2^i-1}

(79)

Indeed, by virtue of Theorem 9 we have

g_i	$\displaystyle \equiv$	2g_i-1 - f g_i-1²	modx^2ⁱ
	$\displaystyle \equiv$	2g_i-1 - f g_i-1²	modx^{2^i-1}
	$\displaystyle \equiv$	g_i-1(2 - f g_i-1)	modx^{2^i-1}
	$\displaystyle \equiv$	g_i-1(2 - 1)	modx^{2^i-1}
	$\displaystyle \equiv$	g_i-1	modx^{2^i-1}

(80)

Therefore when computing g_i we only to care about power of x in the range x^{2^i-1 ...}x^2ⁱ. 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

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

g_i $\displaystyle \equiv$ g_i-1 modx^{2^i-1}

(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 exists. Indeed f g $\equiv$ 1 modx implies f (0)g(0) = 1 which says that f (0) is a unit.