Statement

Let ${\mathbb{R}}$ be a commutative ring and let $n > 0$ be a power of $2$ . Let ${\omega}$ be a primitive $2n$ -th root of unity. We consider the following polynomial $m = x^n - x - 1$ in ${\mbox{${\mathbb{R}}$}}[x]$ . Let $f = {\Sigma}_{k=0}^{k=n-1} f_k x^k$ and $g = {\Sigma}_{k=0}^{k=n-1} g_k x^k$ be two polynomials of degree less than $n$ . The goal of this exercise is to show that one can compute $fg \mod{\ m}$ asymptotically at the cost of multiplying two polynomials in ${\mbox{${\mathbb{R}}$}}[x]$ with degree $n-1$ . Let $q$ and $r$ be the quotient and the remainder in the division of $fg$ by $m$ . We define the polynomial $c = -q x + r$ .