Statement

Let ${\mathbb{K}}$ be a field and let $m \in {\mbox{${\mathbb{K}}$}}[x]$ be a polynomial of degree $d \geq 2$ . We aim at computing in ${\mbox{${\mathbb{K}}$}}[x] / \langle m \rangle$ as fast as possible. Let ${\ell} \in {\mbox{${\mathbb{K}}$}}[x]$ be another polynomial with degree strictly less than $d$ and such that ${\ell}$ and $m$ are relatively prime. Let $u, v \in {\mbox{${\mathbb{K}}$}}[x]$ such that

$$u \, {\ell} + v \, m = 1, \ \ {\deg}(u) < {\deg}(m), \ \ {\rm and} \ \ {\deg}(v) < {\deg}( {\ell} ).$$

We consider the application ${\Phi}$ from ${\mbox{${\mathbb{K}}$}}[x] / \langle m \rangle$ to itself mapping $\overline{a}$ to $\overline{{\ell} a}$ . We shall see that $\overline{u} {\Phi}(\overline{a}) {\Phi}(\overline{b})$ can be computed in $3 M(d) + O(d)$ operations in ${\mathbb{K}}$ for a suitable choice of ${\ell}$ . For $\overline{a}, \overline{b} \in {\mbox{${\mathbb{K}}$}}[x] / \langle m \rangle$ define ${\alpha} = {\Phi}(\overline{a})$ and ${\beta} = {\Phi}(\overline{b})$ . Then,

• define ${\gamma} = \overline{u} {\Phi}(\overline{a}) {\Phi}(\overline{b})$ .
• let $(q_1, f_1)$ be the quotient-and-remainder in the division of ${\alpha} {\beta}$ by ${\ell}$ ,
• let $(q_2, f_2)$ be the quotient-and-remainder in the division of $v f_1$ by ${\ell}$ ,
• let $f_3 := f_1 - m \, f_2$