Number Theoretic Transform (NTT) example not working out

Question

I'm reading up on the NTT, which is a generalisation of the DFT. I'm working in $\mathbb{F}_5$ with primitive root $w=2 \mod 5$. Suppose I want to compute the NTT of $x=(1,4)$. So far I have obtained:

$$\hat{x}=\mathcal{N}(x)=\left(\sum_{j=0}^1 2^{jk}x_j\mod 5\right)_{k=0}^1=(1+4,1+2\cdot 4)\equiv(0,4)\mod 5.$$

Applying the inverse NTT should recover $x$. But...

$$\mathcal{N}^{-1}(\hat{x})=\left(\frac{1}{2}\sum_{k=0}^1 2^{-jk}\hat{x}_k\mod 5\right)_{j=0}^1=\left(\frac{1}{2}(0+4),\frac{1}{2}(0+2^{-1}\cdot 4)\right)\equiv(2,1).$$

But this is not the same as $x$. What am I doing/thinking wrong? I'm thinking it could be to do with how I'm working with "inverses", e.g. 1/2, in modular arithmetic?

Answer 1

You are trying to compute an NTT of length $n = 2$. You chose the modulus $p = 5$ with a primitive root $w = 2$, which are appropriate so far.

The primitive root $w$ has order $p - 1 = 4$, which means $2^4 \equiv 1 \mod 5$. But what you want is an $n$th root of unity $a$, where $a^n = a^2 \equiv 1 \mod 5$. The easiest way to obtain this is to compute $a = w^{(p - 1) / n} = w^2 \equiv 4 \mod 5$. Now using $a$ instead of $w$, we have:

$$\begin{align} \hat{x} = \mathcal{N}(x) &= (1a^0 + 4a^0, \: 1a^0 + 4a^1) \\ &= (1\cdot1 + 4\cdot1, \: 1\cdot1 + 4\cdot4) \\ &\equiv (0, \: 2) \mod 5. \end{align}$$

We compute the inverse transform using $a^{-1} \equiv 4 \mod 5$:

$$\begin{align} x = \mathcal{N}^{-1}(\hat{x}) &= (2^{-1})\:(0a^0 + 2a^0, \: 0a^0 + 2a^{-1}) \\ &= (3)\:(0\cdot1 + 2\cdot1, \: 0\cdot1 + 2\cdot4) \\ &\equiv (3)\:(2, \: 3) \\ &\equiv (1, \: 4) \mod 5. \end{align}$$

Notes:

• In your own answer you said that because you need a 2nd root of unity, you needed to choose $p = 3$. This is not true - you can choose any $p = kn + 1$. Higher primes will have higher order roots, but you can take the power of a primitive root to get the $n$th root that you desire.
• Your approach of padding the vector with zeros may or may not be appropriate depending on the situation. Padding is okay when the goal is to compute a convolution, but not okay if the goal is to compute the exact frequency spectrum of the input.

Answer 2

I think this is right. It seems the problem was related to the size of the NNT, $n=2$ in my case, and the order of the primitive root of unity. Since $n=2$ then I needed to choose a $2$-th root of unity, which would mean switching to prime $p=3$, but then this would not work because my vector $(1,4)\equiv(1,1)$ so I lose information given my choices.

To remedy this, I can "pad out" the original vector to obtain $(1,4,0,0)$ and use prime $p=5$. Then $2$ is a $4$-th root of unity in $\mathbb{F}_5$ and $x_i<5$ as required. Note - I need a $4$-th root of unity because my vector is of size $n=4$. Then we have $$\hat{x}=\mathcal{N}(x)=\left(\begin{array}{llll}2^{0\times 0}&2^{0\times 1}&2^{0\times 2}&2^{0\times 3}\\2^{1\times 0}&2^{1\times 1}&2^{1\times 2}&2^{1\times 3}\\2^{2\times 0}&2^{2\times 1}&2^{2\times 2}&2^{2\times 3}\\2^{3\times 0}&2^{3\times 1}&2^{3\times 2}&2^{3\times 3}\end{array}\right)\left(\begin{array}{l}1\\4\\0\\0\end{array}\right)\stackrel{5}{\equiv}\left(\begin{array}{llll}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{array}\right)\left(\begin{array}{l}1\\4\\0\\0\end{array}\right)=\left(\begin{array}{l}5\\9\\17\\13\end{array}\right)\stackrel{5}{\equiv} \left(\begin{array}{l}0\\4\\2\\3\end{array}\right).$$ To check this is correct, we apply the inverse NNT, $$x=\mathcal{N}^{-1}(\hat{x})=4^{-1}\left(\begin{array}{llll}1&1&1&1\\1&2^{-1}&4^{-1}&3^{-1}\\1&4^{-1}&1^{-1}&4^{-1}\\1&3^{-1}&4^{-1}&2^{-1}\end{array}\right)\left(\begin{array}{l}0\\4\\2\\3\end{array}\right)\stackrel{5}{\equiv}4^{-1}\left(\begin{array}{llll}1&1&1&1\\1&3&4&2\\1&4&1&4\\1&2&4&3\end{array}\right)\left(\begin{array}{l}0\\4\\2\\3\end{array}\right)=4^{-1}\left(\begin{array}{l}4\\1\\0\\0\end{array}\right)\stackrel{5}{\equiv} \left(\begin{array}{l}1\\4\\0\\0\end{array}\right).$$

This article explains further how the order of the root of unity is related to the NTT.