Questions

$(1)$

Show that the middle product of $f$ and $g$ can easily be obtained from the remainder of $h$ by $x^{2n} - 1$ .

$(2)$

Let ${\omega}$ be a primitive $2n$ -th root of unity. Deduce an algorithm that computes the middle product of $f$ and $g$ at the cost of multiplying two polynomials in ${\mbox{${\mathbb{R}}$}}[x]$ with degree $2n-1$ by means of the FFT-based algorithm studied in class.