2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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]$. $\endgroup$ – reuns Apr 4 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.