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$ .

Marc Moreno Maza
2008-03-18