Uso del teorema de convolución para demostrar la equivalencia entre la multiplicación en forma de coeficientes y en forma de puntos

Last updated on Jun 16, 2026

Al principio de esta serie, argumentamos que la multiplicación de dos polinomios de grado $n$ como máximo puede realizarse en un tiempo de complejidad $\mathcal{O}(n)$ si ambos polinomios están en forma de punto-valor.

En la práctica, la dificultad radica en que los polinomios suelen darse en forma de coeficientes, y queremos que el resultado de la multiplicación también esté en forma de coeficientes.

Afortunadamente, estos problemas pueden resolverse utilizando las versiones rápidas de la NTT y la INTT.

Para multiplicar dos polinomios representados en forma de coeficientes en un tiempo $\mathcal{O}(n \log n)$ , el procedimiento es el siguiente:

Utilizando la NTT, los polinomios se convierten de la forma de coeficientes a la forma de punto-valor.
Los polinomios en forma de punto-valor se multiplican punto por punto. Esto puede realizarse en un tiempo de complejidad $\mathcal{O}(n)$ , y el resultado se obtiene en forma de punto-valor.
Se utiliza la INTT para transformar el polinomio resultante de vuelta a la forma de coeficientes.

Utilizando las raíces $n$ -ésimas de la unidad, donde $n$ es una potencia de $2$ , los pasos 1 y 3 pueden realizarse en un tiempo $\mathcal{O}(n \log n)$ .

La única limitación es que debemos imponer un grado máximo de $n-1$ al polinomio resultante. Por lo tanto, la suma de los grados de los dos polinomios que queremos multiplicar no puede superar $n-1$ .

En la práctica, esto no suele ser un problema, ya que por lo general podemos utilizar campos que contengan raíces $n$ -ésimas de la unidad lo suficientemente grandes como para que los grados de los polinomios se mantengan dentro del límite permitido.

Los polinomios de grado inferior a $n-1$ no representan un problema, ya que pueden rellenarse con coeficientes de valor cero hasta el grado $n-1$ .

Sin utilizar las versiones rápidas de la NTT y la INTT, la multiplicación de polinomios tendría una complejidad de tiempo $\mathcal{O}(n^2)$ .

El objetivo de este capítulo es demostrar nuestra afirmación. Mostraremos que multiplicar dos polinomios en forma de coeficientes es equivalente a aplicar la NTT a cada polinomio, realizar la multiplicación punto por punto y, a continuación, aplicar la INTT al polinomio resultante obtenido de esta operación.

Este resultado se conoce como el teorema de convolución en el contexto de la multiplicación de polinomios. En un contexto más general, el teorema de convolución establece que

“la convolución en el dominio original es equivalente a la multiplicación punto por punto en el dominio transformado.”

Para comprender adecuadamente este teorema, debemos empezar por definir qué es la convolución.

Los lectores menos inclinados hacia las matemáticas pueden saltarse este capítulo sin pérdida de continuidad. En el resto del texto, demostramos el teorema de convolución, pero si el lector solo está interesado en su aplicación, es suficiente con aceptar que puede utilizarse para multiplicar polinomios en un tiempo de complejidad $\mathcal{O}(n \log n)$ en lugar de $\mathcal{O}(n^2)$ .

Convolución

La multiplicación de dos polinomios en forma de coeficientes es un ejemplo de una operación de convolución.

Consideremos dos polinomios de grado 2,

f(x) = a_0 + a_1x + a_2 x^2

g(x) = b_0 + b_1 x + b_2 x^2.

La multiplicación en forma de coeficientes da como resultado el polinomio

\begin{aligned} h(x) = f(x)g(x) &= a_0b_0 + a_0b_1 x+a_0b_2x^2 + \\ &+ a_1b_0x + a_1b_1x^2 + a_1b_2x^3 \\ &+ a_2 b_0 x^2 + a_2 b_1 x^3 + a_2b_2x^4. \end{aligned}

Reorganizando esta expresión, obtenemos

\begin{aligned} h(x) = f(x)g(x) &= a_0b_0 \\ &+ (a_0 b_1 + a_1b_0)x \\ &+ (a_0 b_2 + a_1 b_1 + a_2 b_0) x^2 \\ &+ (a_1 b_2 + a_2 b_1) x^3 \\ &+ a_2 b_2 x^4. \end{aligned}

Por lo tanto, los coeficientes del polinomio resultante de la multiplicación de $f(x)$ y $g(x)$ son

\begin{aligned} c_0 &= a_0b_0, \\ c_1 &= a_0 b_1 + a_1b_0, \\ c_2 &= a_0 b_2 + a_1 b_1 + a_2 b_0, \\ c_3 &= a_1 b_2 + a_2 b_1, \\ c_4 &= a_2 b_2. \end{aligned}

Estos coeficientes pueden expresarse de forma compacta mediante la fórmula

c_k = \sum_{i=0}^{k} a_i b_{k-i}

para $k=0,1,2,3,4$ , que es el grado del polinomio $h(x)$ . Examinemos esto para uno de los coeficientes, $c_3$ . Para este coeficiente, tenemos

c_3 = \sum_{i=0}^{3} a_i b_{3-i} = a_0 b_3 + a_1 b_ 2 + a_2 b_1 + a_3 b_0.

Dado que tanto $a_3$ como $b_3$ son cero (porque los polinomios $f(x)$ y $g(x)$ tienen grado 2), esto se reduce a

c_3 = a_1 b_2 + a_2 b_1,

como se esperaba.

La operación definida por

c_k = \sum_{i=0}^{k} a_i b_{k-i}

se denomina convolución y suele escribirse como

c_k = (a \ast b)_k,

donde $\ast$ denota el operador de convolución.

El Teorema de Convolución

Nuestro objetivo es demostrar que convertir $f(x)$ y $g(x)$ a la forma de punto-valor, multiplicar los puntos correspondientes y convertir el resultado de vuelta a la forma de coeficientes es equivalente a realizar la convolución de los coeficientes de $f(x)$ y $g(x)$ .

Consideremos los polinomios

f(x)=a_0 + a_1x+a_2x^2 + ... +a_px^p

g(x)=b_0 + b_1x+b_2x^2 + ... +b_qx^q

de grado $p$ y $q$ .

Multiplicar $f(x)$ y $g(x)$ produce un nuevo polinomio $h(x)$ cuyo grado es la suma de los grados $p$ y $q$ de $f(x)$ y $g(x)$ , respectivamente.

Supongamos que el grado de $h(x)$ es $n-1$ .

Por lo tanto, queremos calcular

h(x) = f(x)g(x) = c_0 + c_1 x + c_2 x^2 + \ldots + c_{n-1} x^{n-1}

Si el grado es inferior a $n-1$ , podemos rellenar con ceros los coeficientes de los términos de mayor grado.

Representemos los coeficientes de los polinomios $f(x)$ y $g(x)$ como

\begin{aligned} [a_0, a_1, a_2, ..., a_{n-1}], \\ [b_0, b_1, b_2, ..., b_{n-1}]. \end{aligned}

Algunos de los coeficientes de mayor grado anteriores serán cero, ya que los grados de $f(x)$ y $g(x)$ deben sumar como máximo $n-1$ . Esto no es un problema. Nuestra única restricción es que

deg⁡(f)+deg⁡(g)=deg⁡(h)≤n−1.

Nuestro primer paso es convertir los polinomios $f(x)$ y $g(x)$ de la forma de coeficientes a la forma de punto-valor.

Primer paso: convertir los polinomios a la forma de punto-valor.

Para convertir estos polinomios a la forma de punto-valor, utilizamos la NTT. Al elegir $n$ como una potencia de $2$ , podemos aplicar la transformada rápida. Sin embargo, dado que el resultado final es equivalente a la multiplicación por la matriz de Vandermonde, presentaremos la formulación matricial.

Por ejemplo, para el polinomio $f(x)$ , sus evaluaciones en las raíces $n$ -ésimas de la unidad están dadas por

\begin{bmatrix} f(1) \\ f(\omega) \\ f(\omega^2) \\ \vdots \\ f(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega & \omega^{2} & \cdots & \omega^{n-1} \\1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(n-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2\\ \vdots \\ a_{n-1} \end{bmatrix}.

De manera similar, para $g(x)$ ,

\begin{bmatrix} g(1) \\ g(\omega) \\ g(\omega^2) \\ \vdots \\ g(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega & \omega^{2} & \cdots & \omega^{n-1} \\1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(n-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} b_0 \\ b_1 \\ b_2\\ \vdots \\ b_{n-1} \end{bmatrix}.

Estas operaciones matriciales pueden escribirse por componentes como

f(\omega^i) = \sum_{r=0}^{n-1} a_r \omega^{ri}

g(\omega^i) = \sum_{s=0}^{n-1} b_s \omega^{si}.

Por ejemplo, la evaluación de $f(\omega^2)$ está dada por

f(\omega^2) = \sum_{r=0}^{n-1} a_r \omega^{r2} = a_0 \omega^{0 \cdot 2} + a_1 \omega^{1 \cdot 2} + a_2 \omega^{2 \cdot 2} + \ldots + a_{n-1} \omega^{{(n-1)} \cdot 2}

Segundo paso: realizar la multiplicación punto por punto de los polinomios en forma de punto-valor.

Ahora multiplicamos las evaluaciones de $f(x)$ y $g(x)$ punto por punto para obtener las evaluaciones del polinomio producto $h(x)$ :

\begin{aligned} h(\omega^0)&= f(\omega^0)g(\omega^0) \\ h(\omega^1)&= f(\omega^1)g(\omega^1) \\ &\vdots \\ h(\omega^{n-1})&= f(\omega^{n-1})g(\omega^{n-1}) \end{aligned}

En notación de índices, esto puede escribirse como

h(\omega^i) = f(\omega^i) g(\omega^i).

Utilizando las expresiones para $f(\omega^i)$ y $g(\omega^i)$ obtenidas en el paso anterior, obtenemos

h(\omega^i) = \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si}\right).

Para recapitular, lo que queremos demostrar es que si aplicamos la INTT al polinomio $h(x)$ en su forma de punto-valor (la forma anterior), el resultado es el mismo que realizar la convolución de $f(x)$ y $g(x)$ .

Último paso: aplicar la INTT al polinomio $h(x)$ en forma de punto-valor

La Transformada Inversa de Teoría de Números (Inverse Number Theoretic Transform) sobre las raíces $n$ -ésimas de la unidad se realiza utilizando la matriz de Vandermonde $V(\omega^{-1})$ escalada por un factor de $\frac{1}{n}$ .

Por lo tanto, al aplicar la INTT al conjunto de puntos $h(\omega^i)$ , obtenemos el polinomio $h(x)$ en forma de coeficientes:

\begin{bmatrix} c_0 \\ c_1 \\ c_2\\ \vdots \\ c_{n-1} \end{bmatrix} = \frac{1}{n}\begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega^{-1} & \omega^{-2} & \cdots & \omega^{-(n-1)} \\1 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2(n-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{-(n-1)} & \omega^{-2(n-1)} & \cdots & \omega^{-(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} h(\omega^0) \\ h(\omega^1) \\ h(\omega^2) \\ \vdots \\ h(\omega^{n-1}) \end{bmatrix}

Esto puede escribirse por componentes como

c_p = \frac{1}{n} \sum_{i=0}^{n-1} h(\omega^i) \omega^{-ip}.

Usando el hecho de que $h(\omega^i)$ está dado por

h(\omega^i) = \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right),

tenemos que

c_p = \frac{1}{n} \sum_{i=0}^{n-1} \underbrace{\left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right)}_{h(\omega^i)} \omega^{-ip}.

Esta expresión es extensa, pero puede simplificarse aplicando la propiedad de ortogonalidad de las raíces de la unidad.

Primero, agrupemos todas las potencias de $\omega$ :

\begin{aligned} c_p &= \frac{1}{n} \sum_{i=0}^{n-1} \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right) \omega^{-ip} && \text{\small La expresión obtenida arriba} \\ &= \frac{1}{n} \sum_{i=0}^{n-1} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)\,\omega^{ri}\,\omega^{si}\,\omega^{-ip} && \text{\small Agrupar las sumas y términos} \\ &= \frac{1}{n} \sum_{i=0}^{n-1} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)\,\omega^{i(r+s-p)} && \text{\small Combinar los exponentes de }\omega^i \\ &= \frac{1}{n} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s) \left( \sum_{i=0}^{n-1} \omega^{i(r+s-p)} \right) && \text{\small Aislar la suma de las raíces de la unidad}. \end{aligned}

La expresión anterior indica que podemos utilizar la ortogonalidad de las raíces de la unidad para simplificarla.

Recordemos que la propiedad de ortogonalidad de las raíces de la unidad está dada por

\sum_{i=0}^{n-1} (\omega^{i})^{r-s}=\begin{cases}n, & \text{si } r\equiv s \pmod{n},\\[6pt]0, & \text{en caso contrario}.\end{cases}

Utilizando la fórmula anterior para la suma aislada de raíces de la unidad en $c_p$ , notamos que

\sum_{i=0}^{n-1} \omega^{i(r+s-p)}

es igual a $n$ si $s = p-r \pmod{n}$ (o equivalentemente $r=p-s \pmod{n}$ ), y cero en caso contrario.

Esto puede representarse como $n$ multiplicado por la delta de Kronecker:

\sum_{i=0}^{n-1} \omega^{i(r+s-p)} = n \delta_{s,p-r}

Reemplazando

\sum_{i=0}^{n-1} \omega^{i(r+s-p)}

en la expresión para $c_p$ , tenemos que

c_p = \frac{1}{n} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)(n \delta_{s, p-r})

Las constantes $\frac{1}{n}$ y $n$ se cancelan:

c_p = \frac{1}{\cancel{n}} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)(\cancel{n} \delta_{s, p-r})

Más importante aún, al sumar sobre el índice $s$ , todos los términos se anulan excepto cuando $s=p-r$ . Esto se debe a la ortogonalidad de las raíces de la unidad.

Como resultado, la sumatoria sobre $s$ colapsa, y podemos reemplazar la sumatoria en $b_s$ por el único elemento $b_{p-r}$ . Obtenemos

c_p = \sum_{r=0}^{n-1} a_r b_{p-r}

¡Esta es exactamente la fórmula de la convolución!

Recordemos lo que hicimos:

Aplicamos la NTT a los polinomios $f(x)$ y $g(x)$ , convirtiendo sus representaciones de coeficientes en representaciones de punto-valor, es decir, vectores que contienen sus evaluaciones en las raíces $n$ -ésimas de la unidad:

\big(f(1), f(\omega), \ldots, f(\omega^{n-1})\big)\quad \text{y} \quad\big(g(1), g(\omega), \ldots, g(\omega^{n-1})\big)

Multiplicamos estos valores de evaluación punto por punto, lo que significa que para cada raíz de la unidad $\omega^i$ calculamos

h(\omega^i)=f(\omega^i)g(\omega^i)

obteniendo la representación en punto-valor del polinomio producto $h(x)$ .

Aplicamos la INTT a este vector de valores

\big(h(1), h(\omega), \ldots, h(\omega^{n-1})\big)

para recuperar la representación de coeficientes de $h(x)$ .

Demostramos que estos tres pasos producen exactamente el mismo resultado que multiplicar los polinomios $f(x)$ y $g(x)$ , es decir, convolucionando los coeficientes de $f(x)$ y $g(x)$ .

Sin embargo, mientras que la convolución directa tiene una complejidad de tiempo $\mathcal{O}(n^2)$ , el procedimiento anterior puede ejecutarse en un tiempo $\mathcal{O}(n \log n)$ , produciendo el mismo polinomio final.

Esto es exactamente lo que establece el teorema de convolución. De manera más formal, podemos escribirlo de la siguiente manera:

Sean $f$ y $g$ dos polinomios en su forma de coeficientes. Sea $*$ la operación de convolución y $\cdot$ la multiplicación.

Sea $\mathcal{F}(f)$ la aplicación de la NTT a $f$ —es decir, mientras que $f$ es el vector de coeficientes, $\mathcal{F}(f)$ es el vector de evaluaciones— y sea $\mathcal{F}^{-1}(\mathcal{F}(f))$ la aplicación de la INTT a $\mathcal{F}(f)$ . Entonces,

f *g =\mathcal{F}^{-1}(\mathcal{F}(f)\cdot\mathcal{F}(g)).

Otra forma de expresar el teorema de convolución es

\mathcal{F}(f *g) =\mathcal{F}(f)\cdot\mathcal{F}(g).

Esta es una transformación lineal y puede entenderse de la siguiente manera: la convolución en el dominio de los coeficientes es equivalente a la multiplicación punto por punto en el dominio de punto-valor.

Este artículo forma parte de una serie sobre la Transformada de Teoría de Números en nuestro ZK Book