LA EVOLUCI ´ON DE LA TRANSFORMADA DE FOURIER HACIA EL

´ALGEBRA ABSTRACTA

Wilmar R, Bola˜nos Chavez * wilmarr.bolanosc@konradlorenz.edu.co Resumen La Transformada R´apida de Fourier, FFT por sus siglas en ingles, revolucion´o el an´alisis arm´onico y el procesamiento de se˜nales al reducir dr´asticamente la complejidad de la convoluci´on discreta mediante el uso de ra´ıces primitivas de la unidad y sus conjugados en el cuerpo de los n´umeros complejos, C. Sin embargo, su dependencia anal´ıtica de la aritm´etica de coma flotante introduce errores de truncamiento que resultan intolerables en entornos que exigen exactitud criptogr´afica. En este art´ıculo se expone la transici´on hacia la Transformada Num´erica Te´orica (NTT), una variante discreta que traslada el algoritmo a la rigidez de los anillos finitos (Zq). Al redefinir la evaluaci´on polinomial sobre ra´ıces primitivas de la unidad modulares, la NTT garantiza un c´omputo exacto libre de redondeos. Asimismo, ante la amenaza del algoritmo cu´antico de Shor sobre los criptosistemas cl´asicos, en este articulo introducimos la Criptograf´ıa Basada en Ret´ıculos (LBC) como una posible soluci´on a la amanaza cu´antica. Se muestra c´omo la NTT se erige como el n´ucleo algor´ıtmico indispensable para el problema Ring-LWE en el anillo cociente Rq = Zq[x]/⟨xn +1⟩, facilitando la convoluci´on negac´ıclica en tiempo asint´otico O(nlogn) para la estandarizaci´on de esquemas post-cu´anticos modernos como CRYSTALS-Kyber.

1.

Introducci´on:

La Complejidad Computacional A mediados del siglo XX, en los inicios de la era de la informaci´on, los matem´aticos e ingenieros se enfrentaron a un muro invisible pero infranqueable: la complejidad algoritmica. Procesar se˜nales digitales o multiplicar n´umeros astron´omicamente grandes requer´ıa una cantidad de operaciones que crec´ıa de manera prohibitiva con el tama˜no de los datos. En este escenario fue donde el redescubrimiento de un ingenioso atajo matem´atico, que hab´ıa permanecido oculto en los manuscritos de Carl Friedrich Gauss desde 1805, cambi´o para siempre la trayectoria de la computaci´on. Este algoritmo no solo resolvi´o el cuello de botella de la ´epoca, sino que sent´o las bases algebraicas para la criptograf´ıa que hoy nos protege de la inminente amenaza cu´antica.

Desde una perspectiva formal, el problema central radica en el c´alculo de la convoluci´on discreta. Sean dos se- *Departamento de matem´aticas, Fundaci´on universitaria Konrad Lorenz cuencias, los cuales pueden ser considerados como vectores de coeficientes de dos polinomios, a = (a0,a1,...,aN−1) y b = (b0,b1,...,bN−1). Su convoluci´on circular c = a ⊛b se define t´ermino a t´ermino mediante la suma: ck = N−1 ∑ j=0 ajb(k−j) (m´od N) para k = 0,1,...,N −1

(1)

Evaluada de manera ingenua, esta operaci´on requiere calcular N multiplicaciones para cada uno de los N elementos resultantes, lo que arroja una complejidad computacional asint´otica de O(N2). En aplicaciones algebraicas o criptogr´aficas del mundo real, donde el grado N de los polinomios es enorme, este crecimiento cuadr´atico resulta computacionalmente intratable.

El gran salto evolutivo ocurri´o al trasladar este problema al dominio de la frecuencia mediante la Transformada Discreta de Fourier (DFT). Por el Teorema de Convoluci´on, sabemos que la convoluci´on circular en el dominio original es isomorfa a una multiplicaci´on escalar punto a punto en el dominio transformado:

DFT(a⊛b) = DFT(a)⊙DFT(b)

(2)

El ´exito de la Transformada R´apida de Fourier (FFT), popularizada por Cooley y Tukey en 1965 [CT65], radic´o en explotar las propiedades de simetr´ıa y ortogonalidad de las ra´ıces primitivas de la unidad en el cuerpo de los n´umeros complejos C. Mediante un enfoque recursivo de “divide y vencer´as”, la FFT redujo el costo de evaluar la transformada de O(N2) a O(N logN), haciendo viable la ecuaci´on 2. Sin embargo, como exploraremos en las siguientes secciones, operar sobre el cuerpo continuo de los complejos C trae consigo un defecto fatal para la teor´ıa de n´umeros y la criptograf´ıa moderna: la p´erdida de precisi´on por el truncamiento en coma flotante. Para superar este obst´aculo, los matem´aticos tuvieron que abandonar el an´alisis arm´onico cl´asico y sumergirse en la rigidez de las estructuras algebraicas abstractas, sustituyendo C por campos finitos y anillos modulares.

2.

La Transformada R´apida de Fourier (FFT) En plena Guerra Fr´ıa, El matem´atico John W. Tukey, asesor del gobierno estadounidense, necesitaba procesar mon-

La Evoluci´on de la Transformada de Fourier hacia el ´Algebra Abstracta ta˜nas de datos sismol´ogicos para detectar ensayos nucleares sovi´eticos subterr´aneos. El problema radicaba en que los computadores de la ´epoca tardaban d´ıas en calcular las transformadas necesarias mediante los m´etodos tradicionales de complejidad O(N2). En 1965, en colaboraci´on con James W. Cooley [CT65], Tukey redescubri´o y sistematiz´o un brillante atajo algebraico. Curiosamente, este mismo m´etodo ya hab´ıa sido intuido por Carl Friedrich Gauss en 1805 para calcular las ´orbitas de los asteroides, mucho antes del nacimiento de la computaci´on. Al reducir el tiempo de c´alculo astron´omicamente, la Transformada R´apida de Fourier (FFT) no solo vigil´o tratados nucleares, sino que posibilit´o la existencia del Wi-Fi, la resonancia magn´etica y el procesamiento de audio moderno [Mat08].

2.1.

Fundamentos Algebraicos:

El Cuerpo Complejo y las Ra´ıces de la Unidad Para entender la genialidad de la FFT, debemos formalizar la Transformada Discreta de Fourier (DFT) como un isomorfismo de evaluaci´on polinomial sobre el cuerpo de los n´umeros complejos, C.

Sea A(x) ∈C[x] un polinomio de grado estrictamente menor que N (donde asumimos, por conveniencia algor´ıtmica, que N es una potencia de 2, N = 2m):

A(x) = N−1 ∑ j=0 ajx j = a0 +a1x+a2x2 +···+aN−1xN−1

(3)

El c´alculo de la DFT del vector de coeficientes a = (a0,...,aN−1) equivale exactamente a evaluar el polinomio A(x) en las N ra´ıces complejas de la ecuaci´on xN −1 = 0. Estas ra´ıces forman un grupo c´ıclico multiplicativo generado por la ra´ız N-´esima primitiva de la unidad, denotada como ωN: ωN = exp  −i2π N  = cos 2π N  −isin 2π N 

(4)

Por lo tanto, el k-´esimo componente del vector transformado X = DFT(a) viene dado por la evaluaci´on puntual: Xk = A(ωk N) = N−1 ∑ j=0 ajω jk N , para k = 0,1,...,N −1

(5)

El ´exito algor´ıtmico de la FFT de Cooley-Tukey, espec´ıficamente la variante de decimaci´on en el tiempo, radica en explotar dos propiedades fundamentales de la ra´ız primitiva de la unidad en el plano de Argand:

1. Simetr´ıa (Anti-periodicidad): ωk+N/2

N = −ωk N

2. Reducci´on del exponente: ω2k

N = ωk N/2 Aplicando estas propiedades, podemos dividir el polinomio original A(x) en dos polinomios de grado (N/2)−1, separando los coeficientes de ´ındice par (Apar) e impar (Aimpar): A(x) = (N/2)−1 ∑ j=0 a2j(x2)j +x (N/2)−1 ∑ j=0 a2j+1(x2)j

(6)

= Apar(x2)+xAimpar(x2)

(7)

El golpe maestro se revela al evaluar A(x) en dos puntos diametralmente opuestos del c´ırculo unitario: x = ωk N y x = ωk+N/2 N = −ωk N. Dado que el cuadrado de ambos puntos es id´entico (±ωk N)2 = ω2k N = ωk N/2, el sistema se colapsa en la estructura conocida como operaci´on mariposa (butterfly):

A(ωk N) = Apar(ωk N/2)+ωk NAimpar(ωk N/2) A(ωk+N/2 N ) = Apar(ωk N/2)−ωk NAimpar(ωk N/2)

(8)

De esta manera, evaluar un polinomio de grado N en N puntos se reduce a evaluar dos polinomios de grado N/2 en N/2 puntos. Al aplicar esta recursi´on logar´ıtmica hasta llegar a polinomios de grado cero, la relaci´on de recurrencia temporal T(N) = 2T(N/2)+O(N) se resuelve en una complejidad de O(N logN). Este avance resolvi´o el problema del procesamiento de se˜nales, pero, como se abordar´a m´as adelante, el uso de n´umeros complejos con precisi´on infinita introduce inevitables errores de truncamiento (coma flotante), un lujo inaceptable en el rigor que exige la criptograf´ıa moderna.

3.

La Transformada Num´erica Te´orica

(NTT)

A pesar del rotundo ´exito de la FFT en el procesamiento de se˜nales digitales, los ingenieros y matem´aticos de la d´ecada de

1970 se toparon con un obst´aculo insalvable al intentar apli-

carla en la teor´ıa de n´umeros exacta. Al operar en el cuerpo continuo de los n´umeros complejos, el c´alculo computacional de senos y cosenos, cuyos valores son irracionales en su mayor´ıa, obligaba a los ordenadores a realizar aproximaciones de coma flotante. En el procesamiento de audio, un error de redondeo en el vig´esimo decimal es inaudible; en criptograf´ıa o multiplicaci´on de enteros gigantes, un solo bit err´oneo corrompe todo el sistema. Buscando una salida a este laberinto de imprecisi´on, investigadores como Agarwal y Burrus (1974) [AB74] propusieron una idea radical: abandonar los n´umeros complejos por completo. Al trasladar la estructura del algoritmo de Cooley-Tukey hacia anillos finitos y la aritm´etica modular, naci´o la Transformada Num´erica Te´orica (NTT), un isomorfismo que preservaba la velocidad O(N logN) pero con una exactitud matem´atica absoluta.

Pask´ın Matem´atico Vol. 8 No 2 (2026) 17-24.

19

3.1.

Del Cuerpo Continuo al Anillo Finito Para erradicar el error de truncamiento num´erico, la Transformada Num´erica Te´orica (NTT) reemplaza el cuerpo de los n´umeros complejos C por un anillo o cuerpo finito, t´ıpicamente denotado como el anillo de enteros m´odulo un primo q, formalizado como el cuerpo de Galois GF(q) o Zq. Bajo esta nueva topolog´ıa algebraica, las operaciones de suma y multiplicaci´on polinomial se ejecutan estrictamente dentro de los l´ımites modulares, garantizando que el espacio de estados sea cerrado y finito. En este espacio, ya no podemos definir la ra´ız de la unidad mediante la exponencial compleja de Euler, e−i2π/N. En su lugar, debemos encontrar un elemento generador dentro del grupo multiplicativo Z∗ q.

3.2.

La Ra´ız Primitiva de la Unidad en Zq Se define una ra´ız N-´esima primitiva de la unidad, denotada como ω ∈Zq, como un entero que satisface estrictamente las siguientes dos condiciones de congruencia:

1. ωN ≡1 (m´od q)

2. ωk̸ ≡1 (m´od q)

para todo 0 < k < N La existencia de tal elemento ω no est´a garantizada para cualquier par de valores (N,q). Por el Teorema de Lagrange aplicado a la estructura de grupos finitos, el orden de cualquier subgrupo debe dividir el orden del grupo principal. Dado que el grupo multiplicativo Z∗ q tiene cardinalidad q −1, una ra´ız primitiva de orden N existe si y solo si N divide exactamente a q−1:

N | (q−1) =⇒q ≡1 (m´od N)

(9)

Cuando esta condici´on algebraica se cumple, el isomorfismo de la transformada se conserva de manera intacta [LZ22]. a b a+ωb a−ωb ω + − Figura 1: Unidad b´asica de la operaci´on mariposa de Cooley- Tukey. El factor de torsi´on ω se aplica antes de la adici´on algor´ıtmica.

3.3.

Formulaci´on Anal´ıtica de la NTT Sea un vector a = (a0,a1,...,aN−1) donde cada coeficiente ai ∈Zq. La Transformada Num´erica Te´orica directa, A = NTT(a), se define como la evaluaci´on polinomial homom´orfica:

Ak = N−1 ∑ j=0 ajω jk (m´od q), para k = 0,1,...,N −1

(10)

La genialidad de esta formulaci´on radica en su invertibilidad exacta. A diferencia de la FFT cl´asica que requiere dividir entre la constante real N, la Transformada Inversa (INTT) requiere multiplicar por el inverso multiplicativo modular de N, denotado como N−1 (m´od q), garantizado por el algoritmo de Euclides extendido dado que gcd(N,q) = 1: a j = N−1 N−1 ∑ k=0 Akω−jk (m´od q), para j = 0,1,...,N −1

(11)

Al ejecutar la convoluci´on polinomial en este dominio transformado modular, el resultado retorna al espacio original de coeficientes sin haber generado un solo decimal, asegurando la integridad criptogr´afica requerida para las matem´aticas modernas.

a b a+ωk nb a−ωk nb × ωk n + − Figura 2: Grafo de flujo de se˜nales para la mariposa radix-

2 de Cooley-Tukey (CT). El vector de entrada es modificado

por el factor de torsi´on ωk n en Zq previo a la transformaci´on lineal cruzada.

4.

La Amenaza Cu´antica y Criptograf´ıa basada en ret´ıculos En 1994, el matem´atico Peter Shor lanz´o una bomba te´orica sobre los cimientos de la ciberseguridad mundial. Shor demostr´o que un ordenador cu´antico, utilizando la Transformada de Fourier Cu´antica, podr´ıa factorizar n´umeros enteros y calcular logaritmos discretos en tiempo polinomial (dentro de la clase de complejidad BQP) [Sho94]. Este algoritmo sentenci´o a muerte a los sistemas criptogr´aficos modernos, como RSA y las Curvas El´ıpticas, cuyo blindaje depend´ıa precisamente de la intratabilidad cl´asica de estos problemas. Ante el inminente “ apocalipsis cu´antico”, los cript´ografos tuvieron que buscar refugio en problemas matem´aticos que la mec´anica cu´antica pudieran resolver eficientemente. La soluci´on lleg´o de la geometr´ıa de n´umeros de Minkowski: los ret´ıculos multidimensionales. En 2005, Oded Regev introdujo el problema Learning With Errors (LWE) [Reg05], demostrando que resolver un sistema de ecuaciones lineales con un peque˜no ruido aleatorio era tan dif´ıcil como encontrar el vector m´as corto en un ret´ıculo. Posteriormente, Lyubashevsky, Peikert y Regev (2010) [LPR10] optimizaron este concepto traslad´andolo a anillos de polinomios (Ring-LWE), creando la base de la Criptograf´ıa Post-Cu´antica (LBC) moderna.

La Evoluci´on de la Transformada de Fourier hacia el ´Algebra Abstracta

4.1.

Geometr´ıa de N´umeros Desde una perspectiva topol´ogica, un ret´ıculo, Lattice en ingles, L es un subgrupo discreto aditivo de Rn. Dado un conjunto de n vectores base linealmente independientes B = {b1,b2,...,bn} en Rm (con m ≥n), el ret´ıculo generado por B se define como el conjunto de todas las combinaciones lineales enteras de dichos vectores:

L (B) =

(

n ∑ i=1 zibi

zi ∈Z

)

(12)

El problema intratable subyacente que blinda a esta topolog´ıa es el Problema del Vector M´as Corto (SVP, Shortest Vector Problem): dada una base arbitraria B de un ret´ıculo L , encontrar el vector no nulo v ∈L que minimice la norma euclidiana ||v||. En dimensiones altas (e.g., n ≥512), no existe ning´un algoritmo cl´asico ni cu´antico conocido que resuelva este problema o sus aproximaciones (GapSVP) en tiempo polinomial.

4.2.

El Anillo Cociente y el Problema Ring-

LWE

Aunque el problema LWE original sobre matrices ofrec´ıa seguridad post-cu´antica, resultaba computacionalmente ineficiente debido al tama˜no cuadr´atico O(n2) de las claves p´ublicas. Para reducir esta complejidad computacional y espacial, Lyubashevsky et al. [LPR10] propusieron el problema Ring- LWE, restringiendo la geometr´ıa a “ret´ıculos ideales” generados sobre anillos de polinomios.

Se define el anillo de coeficientes enteros R = Z[x]/⟨Φm(x)⟩, donde Φm(x) es el m-´esimo polinomio ciclot´omico. Para lograr la m´axima eficiencia algor´ıtmica, las implementaciones modernas fijan m como una potencia de 2, de modo que Φm(x) = xn + 1, con n = m/2. Al aplicar aritm´etica modular con un primo q, trabajamos en el anillo cociente finito:

Rq = Zq[x] ⟨xn +1⟩

(13)

El problema de b´usqueda Ring-LWE consiste en lo siguiente: sea un polinomio secreto s(x) ∈Rq muestreado de una distribuci´on de probabilidad espec´ıfica (t´ıpicamente una Gaussiana discreta χ peque˜na). Se proporciona a un adversario un conjunto de pares (ai(x),bi(x)), donde ai(x) se elige uniformemente al azar de Rq y:

bi(x) ≡ai(x)·s(x)+ei(x) (m´od ⟨xn +1,q⟩)

(14)

Aqu´ı, ei(x) ←χ representa un polinomio de .errorc¸on coeficientes peque˜nos. La dificultad de distinguir de manera no trivial las muestras (ai,bi) de pares de polinomios puramente aleatorios (ai,ui) en Rq es computacionalmente equivalente a resolver el SVP en el peor de los casos sobre ret´ıculos ideales en R.

La barrera operativa para que Ring-LWE se convierta en un est´andar global es el costo de la multiplicaci´on polinomial ai(x)·s(x) en el anillo Rq. Como veremos a continuaci´on, es precisamente en este cuello de botella donde la Transformada Num´erica Te´orica (NTT) emerge como la ´unica soluci´on algor´ıtmica viable.

5.

La NTT como el motor de la Criptograf´ıa Post-Cu´antica Con la amenaza de la computaci´on cu´antica acechando, el Instituto Nacional de Est´andares y Tecnolog´ıa (NIST) de los Estados Unidos inici´o en 2016 un proceso global para estandarizar los algoritmos criptogr´aficos del futuro. Tras exhaustivas rondas de escrutinio criptoanal´ıtico, esquemas basados en ret´ıculos ideales como CRYSTALS-Kyber [BDK+18] emergieron como los vencedores. ¿La raz´on principal de su victoria? Su asombrosa eficiencia. Sin embargo, esta velocidad no proviene de la topolog´ıa del ret´ıculo en s´ı, sino de la implementaci´on ingenieril de la Transformada Num´erica Te´orica (NTT). Kyber y sus pares dependen de multiplicar polinomios de grado 255 miles de veces por segundo. Sin la NTT, el coste cuadr´atico habr´ıa hecho que la criptograf´ıa post-cu´antica fuera demasiado lenta para el tr´afico de internet moderno. De esta forma, un algoritmo algebraico dise˜nado en los a˜nos

70 para evitar errores de redondeo num´erico se convirti´o en el

escudo fundamental de la ciberseguridad global del siglo XXI [LZ22].

5.1.

El Cuello de Botella: La Convoluci´on Negac´ıclica Como se estableci´o en la Ecuaci´on 14, el coraz´on del problema Ring-LWE reside en multiplicar elementos dentro del anillo cociente Rq = Zq[x]/⟨xn +1⟩.

Si aplic´aramos la NTT est´andar sobre dos polinomios a(x) y b(x) de grado n −1, el Teorema de Convoluci´on nos devolver´ıa su producto m´odulo (xn −1), lo cual corresponde a una convoluci´on circular regular. Sin embargo, el anillo criptogr´afico impone la reducci´on por el polinomio ciclot´omico (xn+1), lo que algebraicamente impone la condici´on xn ≡−1 (m´od q). Esto da lugar a la convoluci´on negac´ıclica, donde los t´erminos que desbordan el grado posicional n cambian de signo al envolverse:

ck = k ∑ j=0 ajbk−j − n−1 ∑ j=k+1 ajbn+k−j (m´od q)

(15)

Calcular esta sumatoria de convoluci´on directamente mediante el algoritmo cl´asico requiere O(n2) operaciones en Zq. Para evadir este coste asint´otico, la soluci´on radica en modificar el isomorfismo de la transformada utilizando una ra´ız de la unidad de orden superior.

Pask´ın Matem´atico Vol. 8 No 2 (2026) 17-24.

21

Figura 3: ´Arbol de descomposici´on del anillo Zq[x]/⟨xn −1⟩utilizando el Teorema Chino del Resto (CRT). La existencia de una ra´ız en´esima primitiva de la unidad ω ∈Zq garantiza que ωn/2 ≡−1 (m´od q), permitiendo la divisi´on recursiva del m´odulo polinomial en componentes de grado mitad hasta alcanzar los factores lineales isom´orficos. Figura 4:

´Arbol de descomposici´on del anillo Zq[x]/⟨xn −1⟩utilizando el Teorema Chino del Resto (CRT). La existencia de una ra´ız en´esima primitiva de la unidad ω ∈Zq garantiza que ωn/2 ≡−1 (m´od q), permitiendo la divisi´on recursiva del m´odulo polinomial en componentes de grado mitad hasta alcanzar los factores lineales isom´orficos.

5.2.

El Isomorfismo con Factores de Torsi´on Para calcular la convoluci´on negac´ıclica utilizando una transformada de tama˜no n (y retener la complejidad asint´otica O(nlogn)), la teor´ıa de n´umeros exige la introducci´on de una ra´ız 2n-´esima primitiva de la unidad, denotada como ψ ∈Zq, la cual cumple la relaci´on ψ2 ≡ω (m´od q), siendo ω la ra´ız n-´esima primitiva est´andar.

Previo a la transformaci´on en el dominio frecuencial, los coeficientes del vector polinomial a = (a0,a1,...,an−1) se escalan elemento a elemento multiplic´andolos por las potencias crecientes de ψ. Esta operaci´on topol´ogica se conoce como el producto por factores de torsi´on (twiddle factors): ˜a = (a0,a1ψ,a2ψ2,...,an−1ψn−1)

(16)

Sea ˜b el vector hom´ologamente pre-escalado para b(x). Al aplicar la Transformada Num´erica Te´orica directa sobre estos vectores modificados, el Teorema de Convoluci´on modular asume la forma:

˜C = NTT(˜a)⊙NTT(˜b) (m´od q)

(17)

Para proyectar el vector ˜C de regreso al dominio del tiempo y aislar los coeficientes finales del polinomio producto c(x) = a(x) · b(x) (m´od xn + 1), aplicamos la Transformada Inversa (INTT) y post-escalamos el resultado multiplicando por las potencias inversas de ψ:

ck = ψ−k ·INTT( ˜C)k (m´od q)

(18)

La Evoluci´on de la Transformada de Fourier hacia el ´Algebra Abstracta Figura 5:

´Arbol de descomposici´on del anillo Zq[x]/⟨xn −1⟩utilizando el Teorema Chino del Resto (CRT). La existencia de una ra´ız en´esima primitiva de la unidad ω ∈Zq garantiza que ωn/2 ≡−1 (m´od q), permitiendo la divisi´on recursiva del m´odulo polinomial en componentes de grado mitad hasta alcanzar los factores lineales isom´orficos.

5.3.

Optimizaci´on Algor´ıtmica en la Pr´actica (Ejemplo CRYSTALS-Kyber) En las implementaciones estandarizadas por el NIST [BDK+18], se seleccionan par´ametros criptogr´aficos estrictos para garantizar la existencia de este isomorfismo en GF(q). En el caso espec´ıfico de Kyber, se fija el grado polinomial en n = 256 y el m´odulo en el n´umero primo q = 3329. Dado que requerimos una ra´ız 2n-´esima (es decir, de orden 512), evaluamos la condici´on de existencia de la NTT (Ecuaci´on 9): verificamos que 3329 ≡1 (m´od 512), lo que significa que 512 divide exactamente a 3328 (q −1). Al fusionar matem´aticamente el escalado de ψ dentro de los nodos de la operaci´on mariposa (butterfly network) de Cooley-Tukey, el c´omputo de la convoluci´on negac´ıclica se ejecuta in-place sin asignar memoria vectorial adicional, consolidando a la NTT como el motor geom´etrico indiscutible de la criptograf´ıa moderna.

6.

Conclusi´on y Comparativa Anal´ıtica El viaje desde el c´alculo manual de las ´orbitas de los asteroides por Gauss, pasando por la detecci´on de se˜nales s´ısmicas en la Guerra Fr´ıa, hasta llegar a la protecci´on de los datos globales contra la computaci´on cu´antica, es, en esencia, la historia de un ´unico y elegante isomorfismo. La Transformada R´apida de Fourier demostr´o que los cuellos de botella asint´oticos pueden romperse si entendemos profundamente la simetr´ıa de los espacios en los que operamos. Sin embargo, la verdadera victoria para la ciberseguridad moderna no provino del an´alisis continuo, sino del ´algebra abstracta. Al despojar a la transformada de sus ra´ıces irracionales y confinarla a la exactitud implacable de los anillos finitos, los matem´aticos crearon un puente indestructible entre la eficiencia algor´ıtmica y la teor´ıa de n´umeros.

Para sintetizar las divergencias topol´ogicas y operativas entre el enfoque cl´asico y el modular, la Tabla 6 presenta una disecci´on anal´ıtica de ambos algoritmos.

6.1.

Reflexi´on Final El advenimiento del algoritmo de Shor nos ense˜n´o una lecci´on de humildad: la seguridad basada en la dificultad de factorizar n´umeros en Z (RSA) es topol´ogicamente fr´agil ante la superposici´on cu´antica. La transici´on hacia la Criptograf´ıa Basada en Ret´ıculos (Lattice-Based Cryptography) y el problema Ring-LWE oblig´o a la comunidad cient´ıfica a operar sobre anillos cociente multidimensionales Rq.

Pask´ın Matem´atico Vol. 8 No 2 (2026) 17-24.

23

Algoritmos NTT Complejidad computacional NTT, INTT, NTTψ, INTTψ−1 O(n2)

NTT♮

no→bo, NTT♮ bo→no, NTTCT,ψ no→bo, NTTCT,ψ bo→no

1

2nlogn

INTT‡

no→bo, INTT‡ bo→no, INTTGS,ψ−1 no→bo , INTTGS,ψ−1 bo→no

1

2nlogn+n

NTT♮

no→bo ◦ψ, NTT♮ bo→no ◦ψbo

1

2nlogn+n ψ−1 bo ◦INTT‡ no→bo, ψ−1 ◦INTT‡ bo→no

1

2nlogn+2n Cuadro 1: Comparaci´on de diferentes algoritmos NTT y su complejidad computacional. Caracter´ıstica Estructural FFT (Cooley-Tukey)

NTT

Espacio Topol´ogico Cuerpo continuo de los Complejos (C) Anillo o Cuerpo Finito (Zq o GF(q)) Ra´ız de la Unidad ωN = e−i2π/N (Exponencial irracional) ω ∈Zq tal que ωN ≡1 (m´od q) (Entero generador exacto) Escalado Inverso

(INTT)

Divisi´on por el escalar real N (1/N) Multiplicaci´on por el inverso modular N−1 (m´od q) Precisi´on Num´erica Susceptible a errores de truncamiento (coma flotante) Exactitud absoluta (Aritm´etica entera, cero errores de redondeo) Complejidad Asint´otica O(N logN) operaciones flotantes O(N logN) operaciones modulares Convoluci´on Nativa Circular en C Circular en Zq (Negac´ıclica con factores de torsi´on ψ) Aplicaci´on Principal Procesamiento de se˜nales, ac´ustica, telecomunicaciones (RF) Criptograf´ıa Post-Cu´antica (LBC), multiplicaci´on de enteros gigantes Cuadro 2: Comparaci´on FFT Cl´asica vs. NTT Modular En este nuevo paradigma, la Transformada Te´orica de N´umeros trasciende su rol original como un simple optimizador de hardware para convertirse en un habilitador existencial. Al fusionar la teor´ıa de grupos, el teorema chino del resto y la geometr´ıa de n´umeros, la NTT nos demuestra que las estructuras algebraicas abstractas son el ´unico refugio verdaderamente seguro en la era de la computaci´on cu´antica. Agradecimientos Agradezco a la Fundaci´on Universitaria Konrad Lorenz el permitirme compartir con todos estos temas tan interesantes y principalmente a la decana del departamento de matem´aticas, Ruth Torres, por todo su apoyo y direcci´on. Finalmente, a todo el equipo de edici´on del Paskin matem´atico encabezado por Nataly Neira Parra.

Referencias.

[AB74] Ramesh Agarwal and Charles Burrus, Fast one-dimensional digital convolution by multidimensional techniques, IEEE Transactions on Acoustics, Speech, and Signal Processing 22 (1974), no. 1, 1–10.

[BDK+18] Joppe Bos, L´eo Ducas, Eike Kiltz, Tancr`ede Lepoint, Vadim Lyubashevsky, John M Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehl´e, Crystals-kyber: a cca-secure module-latticebased kem, Ieee european symposium on security and privacy (euros&p), 2018, pp.–367@.

[CT65] James W Cooley and John W Tukey, An algorithm for the machine calculation of complex fourier series, Mathematics of Computation 19 (1965), no. 90, 297–301.

[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev, On ideal lattices and learning with errors over rings, Advances in cryptology–eurocrypt 2010: 29th annual international conference on the theory and applications of cryptographic techniques, 2010, pp.–23@.

[LZ22] Zhichuang Liang and Yunlei Zhao, Number theoretic transform and its applications in lattice-based cryptosystems: A survey, ar- Xiv preprint arXiv:2211.13546 (2022).

[Mat08] Todd Mateer, Fast fourier transform algorithms with applications, Clemson University, 2008.

[Reg05] Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the thirty-seventh annual acm symposium on theory of computing, 2005, pp.–93@. [Sho94] Peter W Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proceedings 35th annual symposium on foundations of computer science, 1994, pp.–134@.

La Evoluci´on de la Transformada de Fourier hacia el ´Algebra Abstracta Acerca del autor:

Wilmar Bola˜nos es docente investigador en el departamento de matem´aticas de la Fundaci´on Universitaria Konrad Lorenz. Sus intereses principales son el ´algebra, la teor´ıa de n´umeros y la criptograf´ıa.