## Modular inverses using Newton iteration

Let be a commutative ring with identity element. Given and such that compute the polynomials such that

 (8)

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

Proposition 3   If Equation (8) has a solution with degree less than then it is unique.

Proof. Indeed, let and be solutions of Equation (8). Then the product is a multiple of . Since then must be 0 . Hence there is a constant and polynomials with degree less than such that

 (9)

It follows that is a multiple of . By repeating the same argument we show that . Then by induction on we obtain .

Remark 3   Since Equation (8) is an equation in , 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 be an equation that we want to solve, where is a differentiable function. From a suitable initial approximation , the sequence, called Newton iteration step,

 (10)

allows to compute subsequent approximations and converge toward a desired solution. In our case we have and the Newton iteration step is

 (11)

Theorem 1   Let be a commutative ring with identity element. Let be a polynomial in such that . Let be the sequence of polynomials defined for all by

 (12)

Then for we have

 (13)

Proof. By induction on . For we have and thus

 (14)

For the induction step we have

 (15)

Indeed means that divides . Thus divides .

Algorithm 2

Definition 2   A multiplication time is a function such that for any commutative ring with a , for every , any pair of polynomials in of degree less than can be multiplied in at most operations of . In addition, must satisfy , for every , with . This implies the superlinearity properties, that is, for every

 (16)

Example 1   Examples of multiplication times are:
• Classical: ;
• Karatsuba: with some that can be taken equal to ;
• FFT over an arbitrary ring: for some that can taken equal to  [CK91].
Note that the FFT-based multiplication in degree over a ring that supports the FFT (that is, possessing primitive -th root of unity, where is a power of greater than ) can run in operations in , with some .

Theorem 2   Algorithm 2 computes the inverse of modulo in operations in .

Proof. Theorem 1 tell us that Algorithm 2 computes the inverse of modulo . Since divides , the result is also valid modulo . Before proving the complexity result, we point out the following relation for .

 (17)

Indeed, by virtue of Theorem 1 we have

 (18)

Therefore when computing we only care about powers of in the range . This says that
• half of the computation of is made during the last iteration of the for loop,
• a quater is made when computing etc.
Now recall that

 (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 ,
• a multiplication of a polynomial (with degree less than ) by a constant,
• truncations modulo
• a subtraction of polynomials with degree less than .
leading to operations in . But this was not a formal proof, although the principle was correct. Let us give a more formal proof.

The cost for the -th iteration is

• for the computation of ,
• for the product ,
• and then the opposite of the upper half of modulo (which is the upper half ) takes operations.
Thus we have , resulting in a total running time:

 (20)

since for all

Remark 4   Once again in Algorithm 2 for we have

 (21)

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

Remark 5   Algorithm 2 can be adapted to the case where is a unit different from by initializing to the inverse of instead of . If is not a unit, then no inverse of modulo exists. Indeed implies which says that is a unit.

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

 (22)

in Algorithm 2. Consider first the product . It satisfies:

 (23)

Moreover, the polynomials and can be seen as polynomials with degrees less than and respectively. Hence, there exist polynomials with degree less than such that we have:

 (24)

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

 (25)

In other words, the upper part (that is, the terms of degree at least ) of the convolution product of gives us exactly .

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

Consider now that we have computed . Viewing and as polynomials with degrees less than and respectively, there exist polynomials with degree less than such that

 (26)

We know that . Hence, we are only interested in computing . Similarly to the above, we observe that

 (27)

Therefore, using DFT, we can compute at the cost of one multiplication in degree less than .

It follows that, in the complexity analysis above (in the proof of Theorem 2) we can replace by leading to instead of .

Marc Moreno Maza
2008-01-07