<s>[INST] Number Theoretic Transform (NTT) example not working out 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?
 [/INST] 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.
</s>