## The quotient as a modular inverse

We shall see now that the complexity result of Proposition 1 can be improved. To do so, we will show that can be computed from and by performing essentially one multiplication in . We start with the equation

 (2)

where , , and are in the statement of Proposition 1. Replacing by and multiplying the equation by leads to the new equation:

 (3)

In Equation (3) each of the rational fractions , , and is multiplied by such that is an upper bound for the degree of its denominator. So Equation (3) is in fact an equation in . Definition 1 and Proposition 2 highlight this fact. Then Proposition 3 and Theorem 1 suggest Algorithm 2 which provides an efficient way to compute the inverse of a univariate polynomial in modulo a power of . Finally we obtain Algorithm 3 for fast division with remainder based on Equation (3).

Definition 1   For a univariate polynomial in with degree and an integer , the reversal of order of is the polynomial denoted by and defined by

 (4)

When the polynomial is simply denoted by . Hence we have

 (5)

Proposition 2   With , , and as abovce, we have

 (6)

Proof. Indeed with Definition 1 Equation (3) reads

 (7)