next up previous
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 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

f g  $\displaystyle \equiv$  1 modx$\scriptstyle \ell$  and  deg g < $\displaystyle \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 g1 and g2 be solutions of Equation (71). Then the product f (g1 - g2) is a multiple of x$\scriptstyle \ell$. Since f (0) = 1 then g1(0) - g2(0) must be 0. Hence there is a constant c $ \in$ R and polynomials h1, h2 with degree less than $ \ell$ - 1 such that

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

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


Remark 12   Since Equation (71) is an equation in R[x]/$ \langle$x$\scriptstyle \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 g0, the sequence, called Newton iteration step,

gi+1  =  gi - $\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

gi+1  =  gi - $\displaystyle {\frac{{ 1/g_i - f}}{{ - 1/{g_i}^2}}}$  =  2gi - f gi2. (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 g0, g1, g2,... 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 gi  $\displaystyle \equiv$  1 modx2i (76)


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

f gi  $\displaystyle \equiv$  f (0) g0  $\displaystyle \equiv$  1 × 1  $\displaystyle \equiv$  1 modx2i (77)

For the induction step we have

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

Indeed f gi  $ \equiv$  1 modx2i means that x2i divides 1 - f gi. Thus x2i+1 = x2i+2i = x2i x2i divides (1 - f gi)2. $ \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 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) = $ \cal {O}$(n log n).


Theorem 10   Algorithm 6 computes the inverse of f modulo x$\scriptstyle \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 x2r. Since x$\scriptstyle \ell$ divides x2r, the result is also valid modulo x$\scriptstyle \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.

gi  $\displaystyle \equiv$  gi-1 modx2i-1 (79)

Indeed, by virtue of Theorem 9 we have

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

Therefore when computing gi we only care about power of x in the range x2i-1 ... x2i. This says that 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 leading to $ \cal {O}$($ \bf M$(2r)) operations in R. $ \qedsymbol$


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

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


next up previous
Next: Division with remainder using Newton Up: Division with remainder using Newton Previous: The quotient as a modular
Marc Moreno Maza
2004-04-27