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$ 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)$$ (2)

where $a$ , $b$ , $q$ and $r$ are in the statement of Proposition 1. Replacing $x$ by $1/x$ and multiplying the equation by $x^n$ leads to the new equation:

$$x^n \, a(1/x) \ = \ \left(x^{n-m} q(1/x) \right) \ \left(x^m \, b(1/x) \right) \ + \ x^{n-m+1} \left( x^{m-1} \, r(1/x) \right)$$ (3)

In Equation (3) 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 (3) is in fact an equation in $R[x]$ . 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$ modulo a power of $x$ . 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_i x^i$ in $R[x]$ with degree $d$ and an integer $k \geq d$ , the reversal of order $k$ of $p$ is the polynomial denoted by ${\rm rev}_k(p)$ and defined by

$${\rm rev}_k(p) \ = \ x^k \, p(1/x) \ = \ {\Sigma}_{k-d}^{k} \ p_{k-i} x^i.$$ (4)

When $k = d$ the polynomial ${\rm rev}_k(p)$ is simply denoted by ${\rm rev}(p)$ . Hence we have

$${\rm rev}(p) \ = \ p_d + p_{d-1} x + \cdots + p_1 x^{d-1} + p_0 x^d.$$ (5)

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

$${\rm rev}_n (a) \ \equiv \ {\rm rev}_{n-m}(q) \ {\rm rev}_m (b) \ \ \mod{ \ x^{n-m+1} }$$ (6)

Proof. Indeed with Definition 1 Equation (3) reads

$${\rm rev}_n (a) \ = \ {\rm rev}_{n-m}(q) \ {\rm rev}_m (b) + x^{n-m+1} \ {\rm rev}_{m-1}(r)$$ (7)

leading to the desised result. $\qedsymbol$

Remark 2   If $R$ is a field then we know that ${\rm rev}_{n-m}(q)$ is invertible modulo $x^{n-m+1}$ . Indeed, ${\rm rev}_{n-m}(q)$ has constant coefficient $1$ and thus the gcd of ${\rm 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.