Cuatro operaciones y finito

La unidad arranca de una observación de ingeniería, no de álgebra: «El codificador combina símbolos de información mediante sumas y productos… El decodificador debe deshacer esas combinaciones, y para eso necesita también las operaciones inversas: la resta y la división. Por lo tanto, el alfabeto de símbolos no puede ser un conjunto cualquiera: debe estar dotado de las cuatro operaciones de la aritmética elemental… Y hay una restricción adicional que es específica de esta disciplina: el alfabeto debe ser finito.»

Cuatro operaciones y finito. Eso es un cuerpo de Galois, y de ahí sale el resto del curso. El candidato que se le ocurre a cualquiera es la aritmética que ya conocés de toda la vida: los enteros módulo m, con la suma y el producto dando la vuelta al llegar a m. La pregunta que importa es si alcanza.

def tabla_producto(m):
    """El producto módulo m, como tabla."""
    return [[(a * b) % m for b in range(m)] for a in range(m)]

def sin_inverso(m):
    """Los elementos no nulos de Z_m que no tienen inverso multiplicativo."""
    return [a for a in range(1, m) if all((a * b) % m != 1 for b in range(1, m))]

sin_inverso(4)   # [2]: 2 no tiene inverso, porque 2 * 2 = 0
sin_inverso(5)   # []: Z_5 es cuerpo entero, todo no nulo tiene inverso

No alcanza siempre. Con m = 4, 2 ⊙ 2 = 0: dos elementos que no son cero, multiplicados entre sí, dan cero. Y un elemento con esa propiedad no puede tener inverso —si 2 tuviera un inverso 2⁻¹, multiplicar los dos lados de 2 ⊙ 2 = 0 por 2⁻¹ daría 2 = 0, que es falso—. El 2 se queda afuera del grupo multiplicativo, y con él afuera, ℤ₄ no es un cuerpo.

01 · Con m compuesto, el producto tiene agujeros

Elegí un m abajo y mirá las dos tablas. La de la suma no tiene nunca ningún problema, para ningún m: sumar y restar no le exige nada al alfabeto. La del producto sí, y sólo cuando m no es primo. El agujero es siempre el mismo: un par de elementos no nulos cuyo producto cae en 0, marcado en la tabla; los elementos que participan de algún agujero se quedan sin inverso, marcados en el encabezado.

El patrón no cambia con m más grande, ni desaparece si lo buscás con más paciencia: aparece exactamente cuando m no es primo, y siempre por la misma razón. «Este detalle, que parece menor, es la razón profunda por la cual los cuerpos finitos sólo existen cuando la cantidad de elementos es una potencia de un primo.»

Y ahí aparece la razón exacta de que GF(2ᵐ) —el cuerpo binario que a este curso le interesa, porque los símbolos son bytes o palabras de bits— no se construya con aritmética modular directa: su tamaño es siempre una potencia de 2 mayor que 2 misma —4, 8, 16, 256…— y todas esas potencias son compuestas. Las primeras tres ya las mediste arriba, con la misma falla exacta que cualquier otro compuesto. La salida es otra estructura —polinomios sobre GF(2), no enteros módulo 2ᵐ— y de eso se ocupa la nota que sigue.

02 · La ley de cancelación fuerza la tabla

Con m primo, ℤ_m es un cuerpo entero, y eso trae una consecuencia práctica. Si a no es cero y a ⊙ b = a ⊙ c, entonces b = c —es la ley de cancelación, y sale directo de que a tiene inverso: multiplicá los dos lados por a⁻¹—. Aplicada a una fila de la tabla de producto, dice que dos casilleros de la misma fila no pueden repetir valor; aplicada a una columna, lo mismo. Cada fila y cada columna —descontando las del cero— tiene que traer los m − 1 elementos no nulos, cada uno una sola vez.

Esa restricción alcanza para completar una tabla a mano, sin multiplicar nada: si en una fila ya aparecieron todos los valores menos uno, el casillero que falta no tiene otra opción. La unidad usa la palabra exacta: «casi como un sudoku». Abajo hay una tabla de ℤ₅* —los cuatro elementos no nulos de ℤ₅— con la mitad de los casilleros dados. Completá el resto usando sólo la regla de que ningún valor se repite en su fila ni en su columna.