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 q mathend000# can be computed from a mathend000# and b mathend000# by performing essentially one multiplication in R[x] mathend000#. We start with the equation

a(x)  =  q(x) b(x) + r(x) (2)

where a mathend000#, b mathend000#, q mathend000# and r mathend000# are in the statement of Proposition 1. Replacing x mathend000# by 1/x mathend000# and multiplying the equation by xⁿ mathend000# 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)$$ (3)

In Equation (3) each of the rational fractions a(1/x) mathend000#, b(1/x) mathend000#, q(1/x) mathend000# and r(1/x) mathend000# is multiplied by x^e mathend000# such that e mathend000# is an upper bound for the degree of its denominator. So Equation (3) is in fact an equation in R[x] mathend000#. 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 x mathend000# modulo a power of x mathend000#. Finally we obtain Algorithm 3 for fast division with remainder based on Equation (3).

Definition 1   For a univariate polynomial p = $\Sigma_{{{0}}}^{{{d}}}$ p_ixⁱ mathend000# in R[x] mathend000# with degree d mathend000# and an integer k $\geq$ d mathend000#, the reversal of order k mathend000# of p mathend000# is the polynomial denoted by rev_k(p) mathend000# and defined by

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

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

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

Proposition 2   With a mathend000#, b mathend000#, q mathend000# and r mathend000# as abovce, we have

$$\equiv$$ (6)

Proof. Indeed with Definition 1 Equation (3) reads

rev_n(a)  =  rev_n-m(q) rev_m(b) + x^n-m+1 rev_m-1(r) (7)

leading to the desised result. $\qedsymbol$

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