** Next:** Modular inverses using Newton iteration
**Up:** Division with remainder using Newton
** Previous:** Classical division with remainder

We shall see now that the complexity result
of Proposition 5
can be improved.
To do so, we will show that *q* can be computed from *a* and *b*
by performing essentially one multiplication in *R*[*x*].
We start with the equation

*a*(*x*) = *q*(*x*) *b*(*x*) + *r*(*x*) |
(65) |

where *a*, *b*, *q* and *r* are in the statement of
Proposition 5.
Replacing *x* by 1/*x* and multiplying the equation by *x*^{n}
leads to the new equation:
*x*^{n} *a*(1/*x*) = *x*^{n-m}*q*(1/*x*) *x*^{m} *b*(1/*x*) + *x*^{n-m+1}*x*^{m-1} *r*(1/*x*) |
(66) |

In Equation (66)
each of the rational fractions *a*(1/*x*), *b*(1/*x*), *q*(1/*x*) and *r*(1/*x*)
is multiplied by *x*^{e} such that *e* is an upper bound for the degree of its denominator.
So Equation (66) is in fact
an equation in *R*[*x*].
Definition 5 and
Proposition 6
highlight this fact.
Then
Proposition 7
and
Theorem 9
suggest Algorithm 6
which provides an efficient way to compute the inverse
of a univariate polynomial in *x* modulo a power of *x*.
Finally we obtain
Algorithm 7
for fast division with remainder based on
Equation (66).

**Definition 5**
For a univariate polynomial

*p* =

*p*_{i}*x*^{i} in

*R*[

*x*]
with degree

*d* and an integer

*k* *d*, the

*reversal of order* *k*
of

*p* is the polynomial denoted by

*rev*_{k}(

*p*) and defined by

*rev*_{k}(*p*) = *x*^{k} *p*(1/*x*) = *p*_{k-i}*x*^{i}. |
(67) |

When

*k* =

*d* the polynomial

*rev*_{k}(

*p*) is simply denoted by

*rev*(

*p*).
Hence we have

*rev*(*p*) = *p*_{d} + *p*_{d-1}*x* + ^{ ... } + *p*_{1}*x*^{d-1} + *p*_{0}*x*^{d}. |
(68) |

**Proposition 6**
With

*a*,

*b*,

*q* and

*r* as abovce, we have

*rev*_{n}(*a*) *rev*_{n-m}(*q*) *rev*_{m}(*b*) mod*x*^{n-m+1} |
(69) |

*Proof*.
Indeed with Definition

5
Equation (

66)
reads

*rev*_{n}(*a*) = *rev*_{n-m}(*q*) *rev*_{m}(*b*) + *x*^{n-m+1} *rev*_{m-1}(*r*) |
(70) |

leading to the desised result.

**Remark 11**
*If **R* is a field then we know that
*rev*_{n-m}(*q*) is invertible
modulo *x*^{n-m+1}.
Indeed,
*rev*_{n-m}(*q*) has constant coefficient 1 and thus the
gcd of
*rev*_{n-m}(*q*) and *x*^{n-m+1} is 1.
The case where *R* is not a field leads also to a simple
and surprising solution as we shall see in the next section.

** Next:** Modular inverses using Newton iteration
**Up:** Division with remainder using Newton
** Previous:** Classical division with remainder
*Marc Moreno Maza *

2004-04-27