Statement

Let ${\mbox{${\mathbb{K}}$}}$ be a field. We assume that we have at our disposal a fast algorithm for multiplications in ${\mbox{${\mathbb{K}}$}}[x_1]$ . Let $M(d)$ be an upper bound for the number of operations in ${\mathbb{K}}$ required for computing the product of two polynomials ${\mbox{${\mathbb{K}}$}}[x_1]$ with degree at most $d$ .

We would like to derive a fast algorithm for multiplying bivariate polynomials in ${\mbox{${\mathbb{K}}$}}[x_1,x_2]$ . To do so, we consider the following transformation.

Let ${\alpha}_2 > 0$ be a positive integer. Given a bivariate polynomial $f$ we replace every monomial $x_1^{e_1} x_2^{e_2}$ of $f$ by $x_1^{e_1 + {\alpha}_2 e_2}$ obtaining a univariate polynomial $u_f$ . Let $d_1$ be the degree of $f$ w.r.t. $x_1$ and $d_2$ its degree w.r.t. $x_2$ ,