Division with remainder using Newton iteration

Algorithm 3  

Theorem 3   Let $R$ be a commutative ring with identity element. Let $a$ and $b$ be univariate polynomials over $R$ with respective degrees $n$ and $m$ such that $n \geq m \geq 0$ and $b \neq 0$ monic. Algorithm 3 computes the quotient and the remainder of $a$ w.r.t. $b$ in $4 \, {\bf M}(n - m) + {\bf M}({\max}(n-m,m)) + {\cal O}(n)$ operations in $R$

Proof. Indeed, Algorithm 3 consists essentially in

• $3$ multiplications in degree $n -m +1$ , plus operations in $O(n -m + 1)$ operations in $R$ , in order to compute $g$ (by virtue of Theorem 1),
• one multiplication in degree $n -m +1$ to compute $q$ ,
• one multiplication in degree ${\max}(n-m,n)$ , and one subtraction in degree $n$ to compute $r$ .

$\qedsymbol$

Remark 7   If several divisions by a given $b$ needs to be performed then we may precompute the inverse of ${\rm rev}_m (b)$ modulo some powers $x, x^2 , \ldots$ of $x$ . Assuming that $R$ possesses suitable primitive roots of unity, we can also save their DTF.

Remark 8   In Theorem 3, the complexity estimate becomes $3 \, {\bf M}(n - m) + {\bf M}({\max}(n-m,n)) + {\cal O}(n)$ if the middle product technique described in Remark 6 applies. Moreover, if $n -m \leq n$ holds, the ${\cal O}(n)$ can be repalced by ${\cal O}(m)$ .