Modular inverses using Newton iteration

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

$$\equiv \ell \ell$$ (8)

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

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

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

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

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

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

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

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

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

Theorem 1   Let R mathend000# be a commutative ring with identity element. Let f mathend000# be a polynomial in R[x] mathend000# such that f (0) = 1 mathend000#. Let g₀, g₁, g₂,... mathend000# be the sequence of polynomials defined for all i $\geq$ 0 mathend000# 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}$$ (12)

Then for i $\geq$ 0 mathend000# we have

$$\equiv$$ (13)

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

$$\equiv \equiv \equiv$$ (14)

For the induction step we have

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

(15)

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

Algorithm 2  

mathend000#

Definition 2   A multiplication time is a function ${\ensuremath{\mathsf{M}}}: {\mbox{${\mathbb N}$}} \longrightarrow {\mbox{${\mathbb R}$}}$ mathend000# such that for any commutative ring R mathend000# with a 1 mathend000#, for every n $\in$ $\mbox{${\mathbb N}$}$ mathend000#, any pair of polynomials in R[x] mathend000# of degree less than n mathend000# can be multiplied in at most ${\ensuremath{\mathsf{M}}}(n)$ mathend000# operations of R mathend000#. In addition, ${\ensuremath{\mathsf{M}}}$ mathend000# must satisfy ${\ensuremath{\mathsf{M}}}(n) / n \geq {\ensuremath{\mathsf{M}}}(m) / m$ mathend000#, for every m, n $\in$ $\mbox{${\mathbb N}$}$ mathend000#, with n $\geq$ m mathend000#. This implies the superlinearity properties, that is, for every m, n $\in$ $\mbox{${\mathbb N}$}$ mathend000#

$$\mathsf {M} \geq \mathsf {M} \mathsf {M} \geq \mathsf {M} \mathsf {M} \mathsf {M} \geq$$ (16)

Example 1   Examples of multiplication times are:

• Classical: d $\longmapsto$ 2d² mathend000#;
• Karatsuba: d $\longmapsto$ C d^log₂(3) mathend000# with some C mathend000# that can be taken equal to 9 mathend000#;
• FFT over an arbitrary ring: d $\longmapsto$ C d log(d )log(log(d )) mathend000# for some C mathend000# that can taken equal to 64 mathend000# [CK91].

Note that the FFT-based multiplication in degree d mathend000# over a ring that supports the FFT (that is, possessing primitive n mathend000#-th root of unity, where n mathend000# is a power of 2 mathend000# greater than 2d mathend000#) can run in C d log(d ) mathend000# operations in R mathend000#, with some C $\geq$ 18 mathend000#.

Theorem 2   Algorithm 2 computes the inverse of f mathend000# modulo x^$\ell$ mathend000# in $3 \ensuremath{\mathsf{M}}(\ell) + 0(\ell)$ mathend000# operations in R mathend000#.

Proof. Theorem 1 tell us that Algorithm 2 computes the inverse of f mathend000# modulo x^2r mathend000#. Since x^$\ell$ mathend000# divides x^2r mathend000#, the result is also valid modulo x^$\ell$ mathend000#. Before proving the complexity result, we point out the following relation for i = 1 ^... r mathend000#.

$$\equiv$$ (17)

Indeed, by virtue of Theorem 1 we have

gi	$$\equiv$$	2gi-1 - f gi-12	mod x2i
	$$\equiv$$	2gi-1 - f gi-12	mod x2i-1
	$$\equiv$$	gi-1(2 - f gi-1)	mod x2i-1
	$$\equiv$$	gi-1(2 - 1)	mod x2i-1
	$$\equiv$$	gi-1	mod x2i-1

(18)

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

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

Now recall that

$${\frac{{1}}{{2}}} {\frac{{1}}{{4}}} {\frac{{1}}{{8}}}$$ (19)

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 mathend000#,
• a multiplication of a polynomial (with degree less than 2^r mathend000#) by a constant,
• truncations modulo x^2r mathend000#
• a subtraction of polynomials with degree less than 2^r mathend000#.

leading to $2 {\ensuremath{\mathsf{M}}}(2^r) + O(2^r)$ mathend000# operations in R mathend000#. But this was not a formal proof, although the principle was correct. Let us give a more formal proof.

The cost for the i mathend000#-th iteration is

• $\ensuremath{\mathsf{M}}(2^{i-1})$ mathend000# for the computation of g_i-1² mathend000#,
• $\ensuremath{\mathsf{M}}(2^i)$ mathend000# for the product f g_i-1² mod x²ⁱ mathend000#,
• and then the opposite of the upper half of fg_i-1² mathend000# modulo x²ⁱ mathend000# (which is the upper half g_i mathend000#) takes 2^i-1 mathend000# operations.

Thus we have $\ensuremath{\mathsf{M}}(2^i) + \ensuremath{\mathsf{M}}(2^{i-1}) + 2^{i-1} \le \frac{3}{2} \, \ensuremath{\mathsf{M}}(2^i) + 2^{i-1}$ mathend000#, resulting in a total running time:

$$\sum_{{1\le{i}\le{r}}}^{} {\frac{{3}}{{2}}} \mathsf {M} \le {\frac{{3}}{{2}}} \mathsf {M} \sum_{{1\le{i}\le{r}}}^{} \mathsf {M} \mathsf {M} \ell \ell$$ (20)

since $2\ensuremath{\mathsf{M}}(n) \le \ensuremath{\mathsf{M}}(2n)$ mathend000# for all n $\in$ $\mbox{${\mathbb N}$}$ mathend000# $\qedsymbol$

Remark 4   Once again in Algorithm 2 for i = 1 ^... r mathend000# we have

$$\equiv$$ (21)

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

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

Remark 6   Let us take a closer look at the computation of

g_i-1(2 - f g_i-1) mod x²ⁱ (22)

in Algorithm 2. Consider first the product f g_i-1 mathend000#. It satisfies:

$$\equiv$$ (23)

Moreover, the polynomials f mathend000# and g_i-1 mathend000# can be seen as polynomials with degrees less than 2ⁱ mathend000# and 2^i-1 mathend000# respectively. Hence, there exist polynomials S, T $\in$ R[x] mathend000# with degree less than 2^i-1 mathend000# such that we have:

f g_i-1 = 1 + Tx^2i-1 + Sx²ⁱ. (24)

We are only interested in computing T mathend000#. In order to avoid computing S mathend000#, let us observe that we have

$$\equiv$$ (25)

In other words, the upper part (that is, the terms of degree at least 2^i-1 mathend000#) of the convolution product of f g_i-1 mathend000# gives us exactly T mathend000#.

So let us assume from now on that we have at hand a primitive 2ⁱ mathend000#-th root of unity, such that we can compute DFT's. Therefore, we can compute T mathend000# at the cost of one multiplication in degree less than 2^i-1 mathend000#.

Consider now that we have computed 2 - f g_i-1mod x²ⁱ mathend000#. Viewing 2 - f g_i-1 mathend000# and g_i-1 mathend000# as polynomials with degrees less than 2ⁱ mathend000# and 2^i-1 mathend000# respectively, there exist polynomials U, V, W $\in$ R[x] mathend000# with degree less than 2^i-1 mathend000# such that

g_i-1(2 - f g_i-1) = U + Vx^2i-1 + Wx²ⁱ (26)

We know that g_i-1  $\equiv$  U mod x^2i-1 mathend000#. Hence, we are only interested in computing V mathend000#. Similarly to the above, we observe that

$$\equiv$$ (27)

Therefore, using DFT, we can compute V mathend000# at the cost of one multiplication in degree less than 2^i-1 mathend000#.

It follows that, in the complexity analysis above (in the proof of Theorem 2) we can replace $\ensuremath{\mathsf{M}}(2^i) + \ensuremath{\mathsf{M}}(2^{i-1})$ mathend000# by $\ensuremath{\mathsf{M}}(2^{i-1}) + \ensuremath{\mathsf{M}}(2^{i-1})$ mathend000# leading to $2\,\ensuremath{\mathsf{M}}(\ell) + O({\ell})$ mathend000# instead of $3\,\ensuremath{\mathsf{M}}(\ell) + O({\ell})$ mathend000#.