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}$ in $6 n \, {\log} n + O(n)$ operations in ${\mathbb{R}}$ . 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$ .