# DFT modulo $p$: how to find the primitive root $\omega_n$.

On complex numbers:

Suppose that we want to find the DFT of the polynomial $$A$$ given in coefficient form

$$a = (a_0, ..., a_{n-1})$$

where $$n$$ is the length $$a$$.

What we do is to

1. Find the $$n$$th primitive root, defined as $$\omega_n = e^{2\pi i/n}$$.
2. Compute the Vandermonde matrix $$V_n$$.
3. Compute $$y = \mathrm{DFT}(a) = V_n a$$, where

$$y_k = \sum_{i=0}^{n-1}a_i\omega_n^{ki}$$

On $$\mathrm{Z}_p$$:

As I understand, when we want to find the DFT of $$A \mod p$$ ($$p$$ - prime) we (according to what I read here):

1. Find a generator $$g$$ of $$\mathbb{Z}_{p}$$.
2. Use $$g$$ to derive $$\omega_n$$ - the $$n$$th (principal) primitive root $$\mod p$$, which is defined by $$\omega_n = g^k$$, where $$k$$ comes from the equation $$\varphi(p) = p-1 = k\cdot n$$. If we found $$k$$ such that the latter equation takes place, then $$\omega_n = g^k$$ is indeed the $$n$$th principal root, because $$\omega_n^n = g^{kn} = g^{p-1} = 1 \mod p$$ (by Euler's Theorem).
3. Compute the Vandermonde matrix and $$y = V_na$$ with all operations $$\mod p$$.

Example

To calculate the DFT of $$a = [6, 0, 10, 7, 2] \mod 11$$ (length $$n = 5$$) we find that one of the generators of $$\mathbb{Z}_{11}$$ is $$6$$, which implies the primitive root $$\omega_n = 6^k = 6^2 = 3 \mod 11$$ (since $$\varphi(11) = 10 = k\cdot 5 = 2\cdot 5$$).

Question: How do I choose $$k$$ when $$p < n$$?

Let illustrate this:

To calculate the DFT of $$a = [-4, 3, 0, 6] \mod 7$$ (length $$n = 4$$) we find that one of the generators of $$\mathbb{Z}_7$$ is $$3$$. To derive $$\omega_n$$ I have to find a number $$k$$ such that $$\varphi(7) = 7 = k\cdot n = k\cdot 4$$, but there is no $$k \in \mathbb{Z}^+$$ that can give $$7$$ when multiplied by $$4$$ and I can't compute $$\omega_n = g^k = 3^k \mod 7$$.

To be precise, in that website they describe the procedure of computing the DFT modulo $$p$$, by defining first a working modulo $$M$$, such that

1. $$1 \leq n < M$$
2. Every element in $$a$$ is in the range $$[0, M)$$.

And then select an integer $$k$$ such that $$p = kn + 1$$, $$p \geq M$$ and $$p$$ - prime.

This kind of make sense to me if I'm the one choosing which $$p$$ to use. But what if that is not the case?

• Let $F$ be a field containing a primitive $N$-th root of unity $\zeta$, for $x \in F^N$ let $X(\zeta^k) = \sum_{n=0}^{N-1} x_n \zeta^{nk}$, then $x_n = \frac{1}{N} \sum_{k=0}^{N-1} \zeta^{-nk} X(\zeta^k)$. If $F = \Bbb{Z/pZ}$ then $N | p-1$. Otherwise for $p \nmid N$ pick $m$ such that $N | p^m-1$ and look at the finite field $F = \Bbb{Z/pZ}\ [t]/(f(t))$ where $f(t) \in \Bbb{Z/pZ}\ [t]$ is a largest irreducible factor of $t^{p^m}-t\in \Bbb{Z/pZ}\ [t]$. – reuns Apr 4 at 2:00