Exact determinant of a circulant matrix The wikipedia gives us a formula for the determinant of a circulant matrix. That is:
$$\mathrm{det}(C) 
= \prod_{j=0}^{n-1} (c_0 + c_{n-1} \omega_j + c_{n-2} \omega_j^2 + \dots + c_1\omega_j^{n-1})= \prod_{j=0}^{n-1} f(\omega_j),$$
with $\omega_j=\exp(2\pi {\rm i}j/n)$ the $n$-th root of unity. 
Assuming a circulant matrix with only entries from $\{-1,1\}$, is there a number theoretic version of this formula which will enable you to compute the determinant exactly and efficiently using only operations on integers?
[This question was also posted to https://math.stackexchange.com/questions/1616049/exact-determinant-of-a-circulant-matrix previously.]
 A: We need to pick a prime $p$ and integer $k \ge 2$ such that $p = nk + 1$. (Alternatively you can choose a positive integer $p > 2n$ (not necessarily prime) such that $n$ divides $\phi(p)$, where $\phi$ is the Euler Totient function. However, I am not sure you can use FFT in the subsequent steps, and may have to resort to manual matrix vector multiplications.)
Next, we need to find a primitive $n$-th root of unity mod $p$. This root can be reused if you have many different circulant matrices of size $n$. This root, which we call $\omega \in \mathbb Z _p$, is needed in the next step when you compute the FFT. Various fast heuristics exist, but note that even a worst case brute force search still runs in $O(p^2 \log(p))$
Using $\omega$, we will compute the number theoretic (mod $p$) FFT of $v$, where $v = (c_0, ... c_{n-1})$. Call the resulting vector $w$. This runs in $O(n \log(n))$
The entries of $w$ are in $\mathbb Z_p$. In your notation, they represent $f(\omega_j)$ mod $p$. Note that your $f(\omega_j)$ are bounded to be in $\{-n, \ldots, n\}$. We will pick integer representatives for the entries of $w$ in $\{-n, \ldots, n\}$, and write that as $\hat w$. The product of the entries in $\hat w$ is your determinant. 
