Comenzaremos este capítulo con una nota inusual: el algoritmo NTT es bastante simple y puede implementarse en menos de 20 líneas de código. Sin embargo, la idea clave que hace que funcione, curiosamente, no tiene un nombre matemático formal. Así que nos tomaremos la libertad de darle al que creemos que es el teorema central detrás del algoritmo un nombre (subjetivamente) pegadizo:

El Teorema de Preservación de la Imagen para Funciones Multivaluadas

Para explicar el Teorema de Preservación de la Imagen, repasaremos un último concepto (muy simple) sobre las raíces de la unidad, y luego presentaremos el teorema.

Raíces $k$-ésimas de raíces cuadradas anidadas

La definición literal de “raíz $k$-ésima de la unidad” es que la raíz de la unidad $a$ satisface $a^k\equiv1$. Dicho de otra manera:

Por lo tanto, no debería sorprender que si $\omega$ es la raíz cuarta primitiva de la unidad, entonces

Ahora hagamos la misma operación si $\omega$ es la raíz octava primitiva de la unidad. El resultado sería

y la raíz octava de 1 genera todas las raíces octavas de la unidad:

Estas observaciones son simplemente una cuestión de definición. Por supuesto, no queremos calcular directamente la raíz cuadrada de 1. Es mucho más fácil encontrar primero la raíz $k$-ésima primitiva de la unidad y luego generar el conjunto de respuestas para $\sqrt[8]{1}$. Por ejemplo:

Copy
import galois
Fq = 17
k = 8
assert (Fq - 1) % k == 0, "no such subgroup"

GF = galois.GF(Fq)

pr = GF.primitive_root_of_unity(k)

roots = []
for i in range(0,k):
    roots.append(pr**i)
print(roots)

También podemos observar que:

y así sucesivamente. Como se señaló anteriormente, calcular directamente $\sqrt[k]{1}$ no es eficiente. En su lugar, consideramos el siguiente diagrama, donde cada flecha hacia abajo es una raíz cuadrada del número que está encima:

Podemos calcular las raíces octavas de la unidad comenzando con 1 y tomando raíces cuadradas repetidamente.

Para un $k$ arbitrario, el diagrama es el siguiente.

A continuación, se presenta un recorrido por los cálculos de la raíz cuadrada:

La raíz cuadrada de 1 es $\set{1,\omega^{k/2}}$. $\omega^{k/2}$ es congruente con -1

Recuerda del capítulo anterior que la raíz cuadrada de $\omega^m$ es $\omega^{m/2}$ y $-\omega^{m/2}$ (asumiendo que $m$ es par).

Por lo tanto, la raíz cuadrada de $\omega^{k/2}$ es $\set{\omega^{k/4},-\omega^{k/4}}$.

También recuerda que el inverso aditivo de $\omega^i$ es $\omega^{i+k/2}$.

Entonces, para calcular $-\omega^{k/4}$ sin el signo negativo, calculamos $\omega^{k/4+k/2}=\omega^{k/4+2k/4}=\omega^{3k/4}$. Por lo tanto, la raíz cuadrada de $\omega^{k/2}$ es $\set{\omega^{k/4},\omega^{3k/4}}$.

La raíz cuadrada de $\omega^{k/4}$ es ${\omega^{k/8},-\omega^{k/8}}$. Nuevamente, para deshacernos del signo negativo, calculamos $\omega^{k/8+k/2}=\omega^{5k/8}$

El porqué la raíz cuadrada de $\omega^{3k/4}=\set{\omega^{3k/8},\omega^{7k/8}}$ se deja como ejercicio para el lector.

La altura del árbol es $\log_2n$

Calcular las raíces $k$-ésimas de la unidad tomando repetidamente las raíces cuadradas de 1 crea un “árbol” que tiene una altura de $\log_2(n)$.

Conceptualización de los estados intermedios del árbol

El conjunto

es matemáticamente equivalente a las raíces octavas de la unidad. El conjunto también es equivalente a:

Lo cual también es equivalente a:

En otras palabras:

Un breve inciso: funciones multivaluadas e imágenes

Es cierto que las observaciones que hicimos anteriormente son extensiones triviales de la definición de raíces $k$-ésimas. Las implicaciones más interesantes de estas observaciones se mostrarán en la siguiente sección. Sin embargo, será útil introducir primero algo de terminología matemática:

Imagen de una función — si tenemos un conjunto de puntos sobre los que evaluamos una función, el conjunto de evaluaciones es la imagen. Por ejemplo, si la función es $f(x)=2x$ y el dominio sobre el que evaluamos $f$ es $\set{1,2}$, entonces la imagen será $\set{2,4}$. El término rango de una función significa el conjunto de valores que una función podría generar. En nuestro contexto, la imagen de la función se refiere al conjunto real de salidas para un conjunto dado de entradas.

Función multivaluada — una función que puede devolver más de una evaluación para un solo punto en el dominio. Por ejemplo, $\sqrt{x}$ evaluada en 0 devuelve 0, pero $\sqrt{x}$ evaluada en 1 devuelve $\set{1, -1}$.

Nota: La función multivaluada $f(x)=\sqrt{x}$ tiene una imagen más grande que su dominio.

Con estas definiciones en mente, el lector debería comprender las siguientes afirmaciones:

“La imagen de $f(x)=x+1$ en el dominio $\set{0,2}$ es $\set{1,3}$”

“La imagen de la función multivaluada $f(x)=\sqrt{x}$ en el dominio $\set{1}$ es $\set{1,-1}$”

Ahora llegamos a un conjunto de observaciones más interesantes.

La imagen de $f(x)=x$ evaluada en $\set{1,...,\omega^7}$ es la misma que $g(x)=\sqrt[8]{x}$ evaluada en $\set{1}$ (k = 8)

Esta afirmación es una simple reformulación de los conceptos mostrados anteriormente, por lo que no daremos más detalles. La parte interesante es cómo podemos generalizar esto a otras funciones.

El matiz aquí es que $g(x)$ es una función multivaluada que devuelve ocho elementos.

La imagen de $f(x)=ax$ evaluada en las raíces cuartas de la unidad es la misma que la de la función multivaluada $g(x)=a\sqrt[4]{x}$ evaluada en $\set{1}$ (k = 4)

Recuerda, $\sqrt[4]{1}=\set{1,\omega,\omega^2,\omega^3}$, por lo que $a\sqrt[4]{1}=\set{a,a\omega,a\omega^2,a\omega^3}$. Esta es la misma imagen que resulta al evaluar $f$ en cada raíz de la unidad una por una. Dado que $f(x)=ax$

• $f(1)=a$
• $f(\omega)=a\omega$
• $f(\omega^2)=a\omega^2$
• $f(\omega^3)=a\omega^3$

Ejercicio para el lector: Sea $f(x)=ax+c$. ¿Cuál es la imagen de $f(x)$ en las raíces cuartas de la unidad? ¿Cuál es la imagen de la función multivaluada $g(x)=a\sqrt[4]{x}+b$ en el dominio $\set{1}$?

En los siguientes capítulos, mostraremos cómo manejar casos más complejos como $f(x)=x^2+x^3$, pero por ahora, mostraremos cómo calcular realmente funciones multivaluadas para los casos simples que presentamos aquí. Pero primero, demos una definición formal a la observación que hemos hecho hasta ahora sobre la equivalencia de imágenes.

La imagen de $f(x)=x$ evaluada en las raíces cuartas de la unidad es la misma que la de la función multivaluada $g(x)=\sqrt{x}$ evaluada en las raíces segundas de la unidad $\set{1,-1}$ (k = 4)

Este ejemplo es muy similar al anterior, excepto que no “apuntamos” al dominio $\set{1}$, sino a $\set{1,-1}$.

Tenemos que

• $g(1)=\sqrt{1}=\set{1,-1}$
• $g(-1)=\sqrt{-1}=\set{\omega,-\omega}$

Esta es la misma imagen que al evaluar $f$ en $\set{1,\omega,-1,-\omega}$

En resumen, si “encogemos” el dominio en un factor de $r$ y reemplazamos cada $x$ en $f(x)$ por $\sqrt[r]{x}$ para crear una nueva función multivaluada $g$, las imágenes de $f$ y $g$ son idénticas.

Ahora definiremos formalmente el concepto que hemos estado ilustrando.

El teorema central de NTT: Teorema de Preservación de la Imagen para Funciones Multivaluadas

Sea $\omega$ la raíz $k$-ésima primitiva de la unidad y $\langle\omega\rangle=\set{1,\omega,\omega^2,...}$ las raíces $k$-ésimas de la unidad definidas en $\mathbb{F}_q$.

Sea $k$ una potencia de 2.

Sea $f(x)$ un polinomio en $\mathbb{F}_q$. Sea $r$ una potencia de 2 menor o igual a $k$.

Sea $g(x)$ una función multivaluada creada reemplazando cada $x$ en $f(x)$ por $\sqrt[r]{x}$.

Sea el dominio $\langle\omega\rangle^r$ el conjunto $\set{\omega^r|\omega\in \langle\omega\rangle}$. Nota que si $r=k$ entonces $\langle\omega\rangle^r=\set{1}$.

La imagen de $f$ en $\langle\omega\rangle$ es exactamente igual a la imagen de $g$ en $\langle\omega\rangle^r$.

¡Es de suma importancia que el lector comprenda el teorema anterior, ya que es el concepto clave en el que se basa la Number Theoretic Transform!

Aquí hay algunos ejemplos para reforzar el concepto:

• La imagen de $f(x)=x$ en las raíces cuartas de la unidad es igual a la imagen de $g(x)=\sqrt{x}$ en las raíces segundas de la unidad (como se mostró en la sección anterior).
• La imagen de $f(x) =x$ en las raíces 16-ésimas de la unidad es igual a la imagen de $g(x)=\sqrt{x}$ en las raíces octavas de la unidad.
• La imagen de $f(x) =x$ en las raíces k-ésimas de la unidad es igual a la imagen de $g_1(x)=\sqrt{x}$ en las raíces k/2-ésimas de la unidad.
• La imagen de $g_1(x)=\sqrt{x}$ en las raíces k/2-ésimas de la unidad es igual a la imagen de $g_2(x)=\sqrt[4]{x}$ en las raíces k/4-ésimas de la unidad.

La siguiente sección muestra ejemplos donde $f(x)$ es ligeramente más compleja.

Ejemplos del Teorema de Preservación de la Imagen para $f(x)=ax+b$

Sea $f(x)=ax+b$ y el dominio sean las raíces cuartas de la unidad $\set{1,\omega,\omega^2,\omega^3}$.

Sea $f_1$ la función multivaluada $a\sqrt{x}+b$ y el dominio sea $\set{1,-1}$ o, de manera equivalente, $\set{1,-\omega^2}$.

Sea $f_2$ la función multivaluada $a\sqrt[4]{x}+b$ y el dominio sea $\set{1}$.

Las imágenes de $f$, $f_1$ y $f_2$ son idénticas: $\set{a+b,a\omega+b,a\omega^2+b,a\omega^3+b}$

Conexión con NTT

Recuerda que el objetivo de NTT es evaluar $f(x)$ en las raíces $k$-ésimas de la unidad en un tiempo de $\mathcal{O}(n\log n)$. En otras palabras, queremos calcular la imagen de $f$ en las raíces $k$-ésimas de la unidad.

Probablemente puedas adivinar hacia dónde va esto.

Calcular la imagen de $f(x)$ en las raíces $k$-ésimas de la unidad es equivalente a calcular la imagen de una nueva función $g(x)$ definida de tal manera que para cada $x$ en $f$, $x\rightarrow\sqrt[k]{x}$ evaluada en $\set{1}$.

Sin embargo, esto deja una pregunta abierta:

Expandir $\sqrt[k]{x}$ en $\set{1,...,\omega^{k-1}}$ no conduce directamente a una aceleración. Algorítmicamente, expandir un $\sqrt[k]{1}$ en las raíces $k$-ésimas de la unidad es lo mismo que evaluar $f(x)$ en los $k$ puntos. ¿De qué nos sirve esta forma alternativa de evaluar $f(x)$?

En el próximo capítulo, demostraremos cómo evaluar funciones multivaluadas utilizando la expansión de raíces cuadradas y explicaremos cómo este enfoque puede evitar cálculos redundantes.