Questions

$(1)$

Show that $\omega=2$ is a primitive $8$ -th root of unity in $F$ , and compute the inverse $\omega^{-1}$ of $\omega$ in $F$ .

$(2)$

Trace the algorithm FFT (Algorithm 2 in Section 1.5 in lecture notes) and its subroutine DFT (Algorithm 1 in Section 1.4 in lecture notes) to compute the product $h=fg\in F[x]$ with Maple, where $\omega$ is given as above.