El ejemplo de la Transformada Teórica de Números (NTT) no funciona

Question

Estoy leyendo sobre la NTT, que es una generalización de la DFT. Estoy trabajando en $\mathbb{F}_5$ con raíz primitiva $w=2 \mod 5$ . Supongamos que quiero calcular el NTT de $x=(1,4)$ . Hasta ahora he obtenido:

$$\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.$$

La aplicación de la NTT inversa debería recuperar $x$ . Pero...

$$\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).$$

Pero esto no es lo mismo que $x$ . ¿Qué estoy haciendo/pensando mal? Estoy pensando que podría tener que ver con la forma en que estoy trabajando con los "inversos", por ejemplo 1/2, en la aritmética modular?

Answer 1

Estás intentando calcular un NTT de longitud $n = 2$ . Has elegido el módulo $p = 5$ con una raíz primitiva $w = 2$ que son apropiados hasta ahora.

La raíz primitiva $w$ tiene orden $p - 1 = 4$ lo que significa $2^4 \equiv 1 \mod 5$ . Pero lo que quieres es un $n$ raíz de la unidad $a$ donde $a^n = a^2 \equiv 1 \mod 5$ . La forma más sencilla de obtenerlo es calcular $a = w^{(p - 1) / n} = w^2 \equiv 4 \mod 5$ . Ahora usando $a$ en lugar de $w$ tenemos:

$$\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}$$

Calculamos la transformada inversa utilizando $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}$$

Notas:

• En tu propia respuesta decías que como necesitas una 2ª raíz de la unidad, necesitabas elegir $p = 3$ . Esto no es cierto - puede elegir cualquier $p = kn + 1$ . Los primos más altos tendrán raíces de orden superior, pero se puede tomar la potencia de una raíz primitiva para obtener el $n$ la raíz que desee.
• Su enfoque de rellenar el vector con ceros puede o no ser apropiado dependiendo de la situación. El relleno está bien cuando el objetivo es calcular una convolución, pero no está bien si el objetivo es calcular el espectro de frecuencia exacto de la entrada.

Answer 2

Creo que esto es correcto. Parece que el problema estaba relacionado con el tamaño del NNT, $n=2$ en mi caso, y el orden de la raíz primitiva de la unidad. Dado que $n=2$ entonces necesitaba elegir un $2$ -raíz enésima de la unidad, lo que significaría cambiar a primo $p=3$ pero entonces esto no funcionaría porque mi vector $(1,4)\equiv(1,1)$ así que pierdo información dadas mis opciones.

Para remediarlo, puedo "rellenar" el vector original para obtener $(1,4,0,0)$ y utilizar prime $p=5$ . Entonces $2$ es un $4$ -ésima raíz de la unidad en $\mathbb{F}_5$ y $x_i<5$ según sea necesario. Nota - Necesito un $4$ -enésima raíz de la unidad porque mi vector es de tamaño $n=4$ . Entonces tenemos $$\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).$$ Para comprobar que esto es correcto, aplicamos el NNT inverso, $$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).$$

Este artículo explica con más detalle cómo se relaciona el orden de la raíz de la unidad con la NTT.