The quotient as a modular inverse

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ⁿ leads to the new equation:

$$\left(\vphantom{x^{n-m} q(1/x) }\right. \left.\vphantom{x^{n-m} q(1/x) }\right) \left(\vphantom{x^m \, b(1/x) }\right. \left.\vphantom{x^m \, b(1/x) }\right) \left(\vphantom{ x^{m-1} \, r(1/x) }\right. \left.\vphantom{ x^{m-1} \, r(1/x) }\right)$$ (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 = $\Sigma_{{{0}}}^{{{d}}}$ p_ixⁱ in R[x] with degree d and an integer k $\geq$ d, the reversal of order k of p is the polynomial denoted by rev_k(p) and defined by

$$\Sigma_{{{k-d}}}^{{{k}}}$$ (67)

When k = d the polynomial rev_k(p) is simply denoted by rev(p). Hence we have

rev(p)  =  p_d + p_d-1x + ^... + p₁x^d-1 + p₀x^d. (68)

Proposition 6   With a, b, q and r as abovce, we have

$$\equiv$$ (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. $\qedsymbol$

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.