Algoritmo INTT a mano

Last updated on May 5, 2026

Como vimos en el artículo anterior, la Inverse Number Theoretic Transform (INTT) se realiza utilizando una matriz de Vandermonde, al igual que la NTT. Esto demuestra que tanto la evaluación a través de la NTT como la interpolación a través de la INTT son operaciones similares.

El problema de usar directamente la matriz de Vandermonde para la evaluación o interpolación es que multiplicar una matriz $k \times k$ por un vector toma un tiempo $\mathcal{O}(k^2)$ . Afortunadamente, al usar las $k$ -ésimas raíces de la unidad, con $k$ siendo una potencia de 2, se puede usar un método rápido que no depende de la multiplicación de matrices, reduciendo la complejidad temporal a $\mathcal{O}(k \log k)$ .

El método rápido para la NTT se introdujo en el capítulo “NTT Algorithm by Hand.” En este capítulo, estudiaremos el método rápido para la INTT.

La idea es simple: interpretar la interpolación polinómica como una evaluación, permitiendo el uso del mismo método empleado para la NTT.

Evaluación e interpolación

Como repaso, la NTT nos permite transformar un polinomio de grado como máximo $k-1$ desde su forma de coeficientes,

\begin{bmatrix}a_0 \\ a_1 \\ ... \\ a_{k-1} \end{bmatrix}

a su forma de punto-valor,

\begin{bmatrix} f(\omega^0) \\ f(\omega^1) \\ ... \\ f(\omega^{k-1}) \end{bmatrix}

evaluando el polinomio en las $k$ -ésimas raíces de la unidad. A esto se le llama evaluación.

La interpolación es lo opuesto a la evaluación: es el proceso de transformar un polinomio desde su forma de punto-valor a su forma de coeficientes.

La interpolación como evaluación

Las evaluaciones e interpolaciones en las $k$ -ésimas raíces de la unidad son operaciones similares porque ambas se realizan utilizando una matriz de Vandermonde.

Para una mejor visualización, consideremos un polinomio de grado como máximo 3,

f(x) = a + bx + cx^2 + dx^3,

evaluado en las $4$ -tas raíces de la unidad

f(1), f(\omega), f(\omega^{2}),f(\omega^{3}).

La evaluación se puede escribir como

\begin{aligned}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}=\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega & \omega^2 & \omega^3 \\1 & \omega^2 & \omega^4 & \omega^6 \\1 & \omega^3 & \omega^6 & \omega^9\end{bmatrix}\begin{bmatrix}a \\b \\c \\d\end{bmatrix}.\end{aligned}

La interpolación se puede escribir como

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix}= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}. \end{aligned}

Inspirados en la estructura de evaluación, podemos ver $\frac{f(1)}{4}, \frac{f(\omega)}{4}, \frac{f(\omega^2)}{4}$ y $\frac{f(\omega^3)}{4}$ como los coeficientes de un nuevo polinomio $\tilde{f}(x)$ , definido como

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big).

En estos términos, los coeficientes $a,b,c$ y $d$ son las evaluaciones de $\tilde{f}(x)$ en los siguientes puntos:

\begin{aligned} a &= \tilde{f}(1) \\ b &= \tilde{f}(\omega^{-1}) \\ c &= \tilde{f}(\omega^{-2}) \\ d &= \tilde{f}(\omega^{-3}) \\ \end{aligned}

Por lo tanto, podemos interpretar la interpolación como la evaluación de otro polinomio. La observación crucial es que la NTT inversa (INTT) no requiere un algoritmo fundamentalmente distinto.

Una vez que la representación de punto-valor se reinterpreta como el vector de coeficientes de un nuevo polinomio, la interpolación se convierte en una evaluación en un conjunto permutado de raíces de la unidad. En este sentido, la evaluación y la interpolación son la misma operación.

Evitando trabajar con las inversas de las raíces de la unidad

Como se muestra en la transformación

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix}= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}, \end{aligned}

la interpolación implica evaluaciones en las inversas de las raíces de la unidad. Sin embargo, podemos evitar trabajar con inversas.

Consideremos $\omega^{-1}$ . Entre las $4$ -tas raíces de la unidad, es el elemento que, al multiplicarse por $\omega$ , da como resultado 1. Dado que

\omega \cdot \omega^3 = \omega^4 \equiv 1,

tenemos que $\omega^{-1} = \omega^3$ .

De manera similar,

\begin{aligned} \omega^{-2} &= \omega^2, \\ \omega^{-3} &= \omega. \end{aligned}

Por lo tanto, los coeficientes $a,b,c$ y $d$ son las evaluaciones de

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big)

en los siguientes puntos:

\begin{aligned} a &= \tilde{f}(1), \\ b &= \tilde{f}(\omega^{-1}) = \tilde{f}(\omega^{3}), \\ c &= \tilde{f}(\omega^{-2}) = \tilde{f}(\omega^{2}), \\ d &= \tilde{f}(\omega^{-3}) = f(\omega). \\ \end{aligned}

Utilizando el hecho de que $\omega^2 = -1$ , podemos reescribir esto como

\begin{aligned} a &= \tilde{f}(1), \\ b &= \tilde{f}(\omega^{3}) = \tilde{f}(-\omega), \\ c &= \tilde{f}(\omega^{2}) = \tilde{f}(-1), \\ d &= \tilde{f}(\omega^{}). \\ \end{aligned}

Realizando la INTT a mano

Un polinomio de grado como máximo $k-1$ , donde $k$ es una potencia de 2, puede evaluarse en las $k$ -ésimas raíces de la unidad usando el método rápido explicado en el capítulo NTT Algorithm by Hand.

Las evaluaciones de

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big)

en los puntos $\tilde{f}(1), \tilde{f}(-1), \tilde{f}(\omega)$ y $\tilde{f}(-\omega)$ se ilustran a continuación.

La idea es agrupar las potencias pares e impares como

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega^2) x^2) + x(f(\omega) + f(\omega^3) x^2)\big),

y evaluar $\tilde{f}(x)$ en $\sqrt{\sqrt{1}}$ . En cada evaluación de una raíz cuadrada interna, la expresión se ramifica en dos, una por cada valor de la raíz cuadrada. Esto continúa hasta que no queden raíces cuadradas, punto en el cual el procedimiento termina.

Obtenemos

\begin{aligned} a&= \tilde{f}(1) = \frac{1}{4}\big( f(1)+f(\omega)+ f(\omega^2)+f(\omega^3)\big), \\ b&= \tilde{f}(-\omega) = \frac{1}{4}\big( f(1)-f(\omega^2) - \omega( f(\omega)-f(\omega^3))\big), \\ c&= \tilde{f}(-1) = \frac{1}{4}\big( f(1)+f(\omega^2) - ( f(\omega)+f(\omega^3))\big), \\ d&= \tilde{f}(\omega) = \frac{1}{4}\big( f(1)-f(\omega^2) + \omega( f(\omega)-f(\omega^3))\big). \\\end{aligned}

Confirmemos que esto coincide con el resultado obtenido de la matriz de Vandermonde:

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix}= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}. \end{aligned}

Usando

\begin{aligned} \omega^{-1} &= \omega^3 = - \omega, \\ \omega^{-2} &= \omega^2 = -1, \\ \omega^{-3} &= \omega, \end{aligned}

lo reescribimos como

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix}= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & - \omega & -1 & \omega \\1 & -1 & 1 & -1 \\1 & \omega & -1 & -\omega\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\ f(\omega^2) \\f(\omega^3)\end{bmatrix}. \end{aligned}

Esto nos lleva a

\begin{alignat*}{3} a &= \tilde{f}(1) &\;=\;& \frac{1}{4}\big( f(1)+f(\omega)+ f(\omega^2)+f(\omega^3)\big), \\ b &= \tilde{f}(-\omega) &\;=\;& \frac{1}{4}\big( f(1)-f(\omega^2) - \omega( f(\omega)-f(\omega^3))\big), \\ c &= \tilde{f}(-1) &\;=\;& \frac{1}{4}\big( f(1)+f(\omega^2) - ( f(\omega)+f(\omega^3))\big), \\ d &= \tilde{f}(\omega) &\;=\;& \frac{1}{4}\big( f(1)-f(\omega^2) + \omega( f(\omega)-f(\omega^3))\big). \end{alignat*}

que son las mismas expresiones obtenidas por el algoritmo rápido.

La diferencia clave es que el algoritmo rápido se ejecuta en tiempo $\mathcal{O}(k \log k)$ , mientras que la multiplicación directa de matrices toma un tiempo $\mathcal{O}(k^2)$ .

Polinomios de grado $k-1$

Lo que hicimos en la sección anterior para un polinomio de grado $3$ puede extenderse a polinomios de cualquier grado.

Supongamos que tenemos un polinomio $f(x)$ evaluado en las $k$ -ésimas raíces de la unidad, donde $k$ es una potencia de $2$ :

f(\omega^0), f(\omega^1), f(\omega^2), ..., f(\omega^{k-1})

Para recuperar los coeficientes del polinomio $f(x)$ , de grado como máximo $k-1$ , que pasa por estos puntos, definimos un nuevo polinomio $\tilde{f}(x)$ como

\tilde{f}(x) = \frac{1}{k}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + ...+ f(\omega^{k-1}) x^{k-1}\big)

Los coeficientes de $f(x)$ están dados entonces por

\begin{aligned} a_0 &= \tilde{f}(\omega^0) \\ a_1 &= \tilde{f}(\omega^{-1}) = \tilde{f}(\omega^{k-1}) \\ a_2 &= \tilde{f}(\omega^{-2}) = \tilde{f}(\omega^{k-2}) \\ ... \\ a_{k-1} &= \tilde{f}(\omega^{-(k-1)}) = \tilde{f}(\omega^{1}) \\ \end{aligned}

Este artículo es parte de una serie sobre la Number Theoretic Transform en nuestro ZK Book