El Number Theoretic Transform (NTT) es un algoritmo para evaluar un polinomio en un campo finito sobre n valores en tiempo O(n log n).
Normalmente, evaluar un polinomio toma tiempo O(n), por lo que evaluar el polinomio n veces tomaría O(n²).
NTT reduce el tiempo de ejecución al reutilizar el trabajo entre las evaluaciones de polinomios. El algoritmo NTT también permite acelerar la multiplicación y división de polinomios. Esta serie de tutoriales enseña cómo funciona el algoritmo NTT y por qué funciona. Este artículo presenta la serie de tutoriales de NTT y proporciona una tabla de contenido para el resto de los tutoriales al final.
Esta también es una serie de tutoriales sobre la Fast Fourier Transform
Dudamos mucho sobre si llamar a esto una “Fast Fourier Transform Tutorial Series” o una “Number Theoretic Transform Tutorial Series”. Funcionalmente, los algoritmos son idénticos — la única diferencia es si usamos un campo finito o números complejos.
Los lectores interesados en aprender cómo funciona la Fast Fourier Transform también pueden seguir esta serie y terminar entendiendo ambos.
Acerca de esta serie de tutoriales de NTT
Aunque es posible describir el algoritmo NTT de manera concisa (ver la siguiente sección), entender cómo funciona es sorprendentemente difícil. Esta serie de tutoriales:
- introduce incrementalmente el conjunto de trucos matemáticos en los que se basa NTT
- guía al lector a través de un viaje para redescubrir NTT desde los primeros principios
- proporciona pruebas matemáticas opcionales de correctitud a lo largo del camino para los lectores interesados en el rigor
El algoritmo NTT es bastante pequeño y se puede generar en un solo intento mediante una IA. Considera el resultado de Gemini a continuación. No te preocupes por entender el código todavía; por ahora, solo nota lo corto que es. Construiremos hasta llegar a lo que está haciendo a lo largo de esta serie.
Prompt: create the NTT algorithm in Python. Show it evaluates the polynomial f(x) = x^2 + 2x + 3 correctly. Use the finite field order 17.
Aquí está el código resultante (con ediciones muy menores para mejorar la legibilidad y ahorrar espacio).
def ntt(a, omega, q):
"""
Performs the Number Theoretic Transform (NTT) on list 'a'
over the finite field modulo 'q' using primitive root 'omega'.
"""
N = len(a)
if N == 1:
return a
# Split into even and odd coefficients
a_even = ntt(a[0::2], (omega * omega) % q, q)
a_odd = ntt(a[1::2], (omega * omega) % q, q)
y = [0] * N
w = 1
for i in range(N // 2):
w_a_odd = (w * a_odd[i]) % q
y[i] = (a_even[i] + w_a_odd) % q
y[i + N // 2] = (a_even[i] - w_a_odd) % q
w = (w * omega) % q
return y
def direct_evaluate(x, q):
"""Directly evaluates f(x) = x^2 + 2x + 3 mod q"""
return (x**2 + 2 * x + 3) % q
# --- Configuration ---
q = 17 # Finite field order
omega = 4 # Primitive 4th root of unity mod 17
# f(x) = 3 + 2x + 1x^2 + 0x^3
coefficients = [3, 2, 1, 0]
# 1. Run NTT
ntt_result = ntt(coefficients, omega, q)
# 2. Run Direct Evaluation for Verification
evaluation_points = [(omega**k) % q for k in range(4)]
direct_result = [direct_evaluate(x, q) for x in evaluation_points]
assert (
ntt_result == direct_result
), "Mismatch between NTT and direct evaluation!"
print("\nSuccess! The NTT evaluated the polynomial correctly.")
Casi todo el trabajo se realiza en estas 14 líneas de código, excluyendo las líneas en blanco:
N = len(a)
if N == 1:
return a
# Split into even and odd coefficients
a_even = ntt(a[0::2], (omega * omega) % q, q)
a_odd = ntt(a[1::2], (omega * omega) % q, q)
y = [0] * N
w = 1
for i in range(N // 2):
w_a_odd = (w * a_odd[i]) % q
y[i] = (a_even[i] + w_a_odd) % q
y[i + N // 2] = (a_even[i] - w_a_odd) % q
w = (w * omega) % q
return y
Sin embargo, la brevedad del algoritmo oculta su complejidad.
Dónde se equivocan la mayoría de los tutoriales sobre FFT / NTT
Al hojear el código anterior, el lector puede ver que el algoritmo NTT, en su núcleo, se basa en dividir los coeficientes del polinomio en partes pares e impares, y muchos tutoriales sobre el tema (así como las explicaciones de IA) intentan explicar NTT a través del lente de la división par-impar.
Sin embargo, como aprenderemos, dividir los coeficientes por su paridad es incidental a trucos matemáticos más profundos en los que se basa NTT.
Fundamentalmente, redescubrir NTT requiere responder “¿por qué es posible reutilizar cálculos entre las evaluaciones de polinomios?” no “¿qué tiene de especial la división entre pares e impares?”.
Consideremos, por ejemplo, si evaluamos el polinomio en los puntos y . A simple vista, no nos dice nada sobre a qué debería ser igual . Por ejemplo, elevar al cuadrado no te da ninguna información sobre qué es al cuadrado.
No es inmediatamente obvio que evaluar polinomios pueda ser más rápido que .
Nuestro objetivo en esta serie es redescubrir, desde los primeros principios, cómo evaluar un polinomio en un punto reduce el trabajo requerido para evaluarlo en otro punto.
El lector debería repasar la serie en el orden que se indica a continuación. Cada capítulo introduce un subconcepto pequeño y digerible que debe ser interiorizado, ya que los capítulos posteriores se construyen unos sobre otros.
Motivación para esta serie de tutoriales
Uno pensaría que, dado lo fundamental que es el algoritmo NTT para la ingeniería moderna, habría una plétora de tutoriales que van más allá de describir su mecánica y explican por qué funciona. Sin embargo, encontramos que las explicaciones existentes son insuficientes, así que creamos esta. Encontrarás muchas perspectivas nuevas en esta serie que no encontrarás en ningún otro lugar. Nos esforzamos por desarrollar nuevos modelos mentales simplificados, no por resumir contenido existente.
Además, el algoritmo NTT refleja estructuralmente el FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). Saber a un nivel profundo por qué funciona el algoritmo NTT hace que el algoritmo FRI sea más fácil de aprender.
De hecho, el término “Fast” en FRI proviene del hecho de que el algoritmo FRI se parece mucho a la Fast Fourier Transform (el algoritmo NTT).
Prerrequisitos para esta serie de tutoriales
Esperamos familiaridad básica con campos finitos y aritmética modular. Definiremos un “subgrupo” en esta serie, por lo que el lector ya debería estar familiarizado con el concepto de un grupo. Leer los primeros seis capítulos del ZK Book debería ser suficiente.
También esperamos conocimientos básicos de álgebra lineal, como las inversas de matrices.
No se requiere un conocimiento profundo del álgebra abstracta. Solo necesitamos fluidez con el vocabulario básico enumerado anteriormente.
Un enfoque motivado para el álgebra abstracta
Muchos lectores encontrarán nuestro tratamiento de los subgrupos y las raíces de la unidad en un campo finito más atractivo que una exposición matemática típica porque presentamos los conceptos en los contextos donde aparecen “en el mundo real”.
No intentamos dar un tratamiento completo a los temas de álgebra abstracta que cubrimos, solo a las partes que:
- aparecen en el mundo real (en este caso, el algoritmo NTT)
- son prerrequisitos para comprender las aplicaciones del mundo real
- proporcionan marcos de trabajo simplificadores para los conceptos del mundo real
Todo lo demás lo cortamos implacablemente o lo marcamos como lectura opcional para los lectores con mayor inclinación matemática. Escribimos esta serie para ingenieros de software, no para matemáticos.
Erratas y comentarios
Si notas algún error o problema en el texto, por favor abre un issue o un pull request en https://github.com/RareSkills/zk-book/tree/prod
Tabla de contenido
Multiplicación de polinomios en forma de puntos. Este capítulo motiva la necesidad de evaluar un polinomio en tiempo subcuadrático.
Subgrupos multiplicativos. Los subgrupos son un prerrequisito para comprender las raíces de la unidad.
Teorema fundamental de los grupos cíclicos. Las raíces de la unidad forman un subgrupo cíclico, y este teorema ilustra cómo se comportan.
Raíces de la unidad en campos finitos. El algoritmo NTT solo funciona si evaluamos un polinomio en las “raíces de la unidad”, las cuales introduce este capítulo. Para aquellos que leen esta serie para entender la Fast Fourier Transform, las raíces de la unidad en un campo finito se comportan de manera idéntica a las raíces de la unidad en los números complejos, es decir, .
Raíces de la unidad congruentes a -1. Dado que las raíces de la unidad forman un subgrupo, cada raíz de la unidad tiene una inversa (que se puede calcular de manera eficiente).
Visualización de raíces de la unidad en el círculo unitario. Este capítulo muestra cómo trazar las raíces de la unidad en un campo finito en un círculo unitario y cómo visualizar fácilmente las inversas aditivas en el subgrupo de las raíces de la unidad.
Matrices de Vandermonde. Las matrices de Vandermonde representan la evaluación de polinomios como la multiplicación de los coeficientes del polinomio y los puntos en los que se evalúan.
Elevación al cuadrado de las raíces de la unidad. Este capítulo es un prerrequisito para el capítulo del Teorema de preservación de la imagen.
Raíces de la unidad elevadas a k/2. Este capítulo es (también) un prerrequisito para el capítulo del Teorema de preservación de la imagen.
Raíces cuadradas de las raíces de la unidad. Este capítulo es (otro más) prerrequisito para el capítulo del Teorema de preservación de la imagen.
Teorema de preservación de la imagen. La idea clave en la que se basa NTT, por extraño que parezca, no tiene un nombre formal, por lo que inventamos el nombre “teorema de preservación de la imagen”. Este capítulo introduce la idea de que evaluar un polinomio en un dominio pequeño permite la reutilización de cálculos en un dominio mayor.
Funciones multivaluadas de raíz cuadrada. Una función multivaluada devuelve un conjunto de valores en lugar de un solo valor. Esto nos da “dos evaluaciones por el precio de una”.
NTT a mano. El algoritmo NTT tiene varias variantes de implementación. Creamos nuestra propia implementación que se presta bien para ser calculada con lápiz y papel para que los estudiantes puedan experimentar el algoritmo de manera visceral.
Campos finitos amigables con FFT. Este artículo enumera los campos finitos que se utilizan en la práctica para NTT y pruebas de conocimiento cero.
Ortogonalidad de las raíces de la unidad. Este capítulo es un prerrequisito para la Inverse Number Theoretic Transform y la Inversa de una matriz de Vandermonde.
Inverse Number Theoretic Transform. La Inverse Number Theoretic Transform “deshace” la Number Theoretic Transform. Toma un conjunto de puntos y devuelve un polinomio en forma de coeficientes.
Inversa de una matriz de Vandermonde. Este capítulo demuestra que la inversa de una matriz de Vandermonde es otra matriz de Vandermonde. Este hecho hace que demostrar la correctitud del algoritmo Inverse Number Theoretic Transform sea trivial.
Inverse Number Theoretic Transform a mano. Los tres capítulos anteriores establecen que la inversa de una matriz de Vandermonde es también una matriz de Vandermonde. Por lo tanto, podemos reutilizar el algoritmo Number Theoretic Transform como la Inverse Number Theoretic Transform con solo un pequeño cambio.
Teorema de convolución (Opcional). El teorema de convolución nos permite crear una prueba elegante de que la multiplicación elemental de polinomios es equivalente a realizar NTT, multiplicación punto a punto, y luego INTT.
Grafos de flujo de señales. NTT se modela frecuentemente con grafos de flujo de señales. Este capítulo es un repaso rápido sobre el tema.
Grafos de flujo de señales en NTT. Aquí, construimos el grafo de flujo de señales para el algoritmo presentado en NTT a mano. El grafo resultante se utilizará para razonar sobre el algoritmo.
Decimation in Time y Decimation in Frequency. El algoritmo que usamos para calcular NTT a mano es funcionalmente equivalente a las implementaciones del algoritmo NTT en producción, pero hay algunas variaciones menores. En este capítulo, mostramos implementaciones reales de NTT utilizadas en producción.
Algoritmo DIT Radix-2 en Python. La NTT tiene varias variaciones algorítmicas, dos de las cuales son DIF (Decimation in Frequency) y DIT (Decimation in Time). La primera se explicó en el capítulo anterior; en este capítulo, explicamos la segunda.
NTT, INTT y multiplicación rápida de polinomios en Python. Aquí, implementamos tanto NTT como INTT en Python y usamos estos algoritmos para realizar la multiplicación de polinomios en tiempo O(n log n).
Este artículo es parte de una serie sobre la Number Theoretic Transform en nuestro ZK Book