Unidad 2 · La construcción de GF(2ᵐ)
GF(2ᵐ) se construye con un polinomio P(x) de grado m sobre GF(2). Elegido el polinomio, α = x genera una sucesión de potencias —α⁰, α¹, α²…—, reduciendo cada vez que el grado se pasa de m − 1. La promesa es que esa sucesión recorra los 2ᵐ − 1 elementos no nulos del cuerpo antes de volver al 1. Es una promesa, no una garantía: depende de qué P(x) se haya elegido.
Cuando la promesa se cumple, P(x) se llama primitivo. Y «primitivo» no es un adjetivo que se memoriza junto con una lista de polinomios: dice, literalmente, que el ciclo de α dé la vuelta entera. Nada más y nada menos que eso.
Las dos mitades de esa frase son la misma afirmación. P(x) es primitivo exactamente cuando α recorre los 2ᵐ − 1 no nulos: no existe un polinomio primitivo cuyo α no genere, porque generarlo todo es lo que la palabra significa. (Sí pueden existir otros elementos que generan el cuerpo entero sin que P(x) sea primitivo —eso es distinto, y vuelve más abajo con el caso de AES.) Y hay una segunda confusión, todavía más común: ser irreducible no es lo mismo que ser primitivo. Irreducible es que GF(2ᵐ) sea un cuerpo de verdad —que todo elemento no nulo tenga inverso—; primitivo es que, además, α lo recorra entero. Un polinomio puede tener la primera propiedad y no la segunda, y eso es exactamente lo que sigue.
from fec_algebra import GF
def orden_de_alfa(m, polinomio):
"""El menor n >= 1 tal que α^n = 1: el largo del ciclo de las potencias."""
campo = GF(m, polinomio)
alfa = campo(2) # α = x: el bit b_1 prendido y nada más
v, n = campo(1), 0
while True:
v *= alfa
n += 1
if v == campo(1):
return n
orden_de_alfa(4, 0b0011) # 15: x⁴ = x + 1 es primitivo
orden_de_alfa(4, 0b1111) # 5: x⁴ = x³+x²+x+1 no lo es -- y sin embargo es un cuerpo
Esos dos números —y los otros dos de más abajo— salen de correr fec_algebra, la librería de Python del propio curso. El widget de abajo no inventa nada: calcula con las mismas reglas, y da los mismos números.
Movete entre los cuatro polinomios del selector y mirá qué cambia. Con x⁴ = x + 1 y con x⁴ = x³ + 1, arrastrando el deslizador hasta el final, el ciclo llega a los quince elementos no nulos de GF(2⁴): los dos son primitivos. Con x⁴ = x³ + x² + x + 1, el ciclo se cierra en el paso cinco, sobre {1, 2, 4, 8, 15}, y los otros diez elementos quedan en rojo para siempre —α nunca los alcanza, sin importar cuánto sigas arrastrando.
Y acá está el punto que más fácil se pasa por alto: los cuatro polinomios de la tabla son irreducibles. GF(2⁴) con x⁴ = x³ + x² + x + 1 es un cuerpo de verdad —todo elemento no nulo tiene inverso multiplicativo—, y sin embargo α no lo recorre. Lo único que cambia entre los cuatro es si el ciclo de α da la vuelta entera. Eso es, literalmente, toda la diferencia entre «cuerpo» y «primitivo».
Con GF(2⁸) —el de AES, x⁸ = x⁴ + x³ + x + 1— pasa lo mismo a otra escala: α tiene orden 51, no 255. Pero el cuerpo sí tiene generadores: x + 1 tiene orden 255 y recorre el cuerpo entero. Hay generadores; α = x simplemente no es uno de ellos. Ésa es la distinción que separó la primera mitad de esta nota a propósito: primitivo describe a P(x), generador describe a un elemento, y en AES las dos cosas se despegan.
Un elemento de GF(2ᵐ) se puede escribir de tres formas —como potencia de α, como polinomio, como m-tupla de bits— y las tres coexisten porque cada una hace fácil una operación distinta. En potencias, multiplicar es sumar exponentes. En tuplas, sumar es XOR bit a bit, sin ningún paso más. Ninguna de las dos hace fácil a la otra operación, y por eso el hardware de un decodificador guarda tablas de las tres en vez de convertir sobre la marcha cada vez.
Elegí abajo un elemento y mirá sus tres caras. Probá esto con el polinomio no primitivo de recién: elegí el 3 —no está en {1, 2, 4, 8, 15}— y mirá la fila de «potencia». Es la misma marca roja del widget de arriba, ahora escrita como el valor de una función: comoPotencia(3) da null porque α nunca llega al 3 con ese polinomio.
Hay una trampa ahí, y ya mató una página de este proyecto. comoPotencia(1) da 0 —porque 1 = α⁰— y 0 es un valor falsy en JavaScript. comoPotencia(0) da null —porque el cero no es ninguna potencia—. Comparar con if (!exp) confundiría los dos casos y diría que el 1 está afuera del ciclo, que es exactamente al revés: hay que comparar con === null. Movete al elemento 1 y al elemento 0 abajo y mirá la diferencia: uno dice «α⁰», el otro dice que el cero no es ninguna potencia; ninguno de los dos es un error.
Todo lo de esta nota es una sola idea vista desde dos lados: el ciclo de α puede cerrarse antes de tiempo, y cuando se cierra, hay elementos que ninguna de las tres representaciones te va a dar como potencia —aunque sí como polinomio y como tupla, porque esas dos no dependen de que nada genere nada. Elegir un polinomio primitivo no es un detalle de implementación: es lo que hace que la tabla de logaritmos discretos —la que el widget de arriba fue completando paso a paso— cubra el cuerpo entero, en vez de dejar agujeros que ninguna potencia rellena.