30-6 FFT using modular arithmetic

As defined, the discrete Fourier transform requires us to compute with complex numbers, which can result in a loss of precision due to round-off errors. For some problems, the answer is known to contain only integers, and by using a variant of the $\text{FFT}$ based on modular arithmetic, we can guarantee that the answer is calculated exactly. An example of such a problem is that of multiplying two polynomials with integer coefficients. Exercise 30.2-6 gives one approach, using a modulus of length $\Omega(n)$ bits to handle a $\text{DFT}$ on $n$ points. This problem gives another approach, which uses a modulus of the more reasonable length $O(\lg n)$; it requires that you understand the material of Chapter 31. Let $n$ be a power of $2$.

a. Suppose that we search for the smallest $k$ such that $p = kn + 1$ is prime. Give a simple heuristic argument why we might expect $k$ to be approximately $\ln n$. (The value of $k$ might be much larger or smaller, but we can reasonably expect to examine $O(\lg n)$ candidate values of $k$ on average.) How does the expected length of $p$ compare to the length of $n$?

Let $g$ be a generator of $\mathbb Z_p^*$, and let $w = g^k \mod p$.

b. Argue that the $\text{DFT}$ and the inverse $\text{DFT}$ are well-defined inverse operations modulo $p$, where $w$ is used as a principal $n$th root of unity.

c. Show how to make the $\text{FFT}$ and its inverse work modulo $p$ in time $O(n\lg n)$, where operations on words of $O(\lg n)$ bits take unit time. Assume that the algorithm is given $p$ and $w$.

d. Compute the $\text{DFT}$ modulo $p = 17$ of the vector $(0, 5, 3, 7, 7, 2, 1, 6)$. Note that $g = 3$ is a generator of $\mathbb Z_{17}^*$.

(Omit!)