Una explicación más detallada (en inglés) puede encontrar en este video sobre el que se basa este texto.

Un campo de Galois es una estructura algebráica utilizada entre otras muchas cosas en algoritmos como el AES, o el Reed-Solomon. La intención de este artículo es dotar al lector de unos conocimientos mínimos que le permitan comprenderlos e implementarlos en algún lenguaje de programación.

Estructuras algebraicas

Una estructura algebraica viene dada por una tupla de elementos y un conjunto de operaciones aplicables a estos elementos. Un ejemplo de estructura () podría ser la tupla formada por los números enteros () y el conjunto de operaciones formado por la suma () y la resta ().

Cuerpos

Son un tipo de estructura algebráica más estricta:

Las operaciones adición sustracción multiplicación y división se pueden realizar siempre que se cumplan las siguientes propiedades:

  • Existe un elemento neutro para la adición y la multiplicación.
  • El orden en que se ejecuten las operaciones no altera el resultado. (Propiedad Asociativa)
  • El orden de los sumandos no altera la suma, o el orden de los factores no altera el producto. (Propiedad Conmutativa)
  • El resultado de un número multiplicado por la suma de dos o más sumandos, es igual a la suma de los productos de cada sumando por ese número. (Propiedad Distributiva)

Cuerpos finitos

También llamados campos de Galois son un cuerpo definido sobre un conjunto finito de elementos donde el número de elementos () debe ser primo o una potencia de un número primo.

Si estaremos ante un caso particular llamado campo primo.

Campos primos

Conocidos como (del ingles Galois Field) están formado por un conjunto de elementos y las operaciones de los cuerpos definidas como:

  • Suma: Relizar la suma normalmente módulo p
  • Resta: Realizar la resta normalmente módulo p
  • Multiplicación: Realizar la multiplicación normalmente módulo p.
  • División: Realizar la división normalmente módulo p.

Ejemplo

GF(7)
Elementos: {0,1,2,3,4,5,6}
Operaciones: {+, -, *, /}

Suma:

1 + 1 = 2 mod 7 = 2
1 + 6 = 7 mod 7 = 0
2 + 6 = 8 mod 7 = 1

Multiplicación:

2 * 3 = 6 mod 7 = 6
3 * 3 = 9 mod 7 = 2

Hasta aquí todo es bastante simple, pero ¿Qué pasa cuando ?

Extension fields

Llamaremos extension field a un cuerpo finito donde el número de elementos es una potencia de un número primo y los elementos del conjunto son polinómios de la forma:

Donde

Pongamos como ejemplo el caso donde y 

p = 2
m = 3
GF(p) = GF(2) = {0,1}

Sabemos que todos polinomios tendrán la forma:

y que a solamente puede tener dos posibles valores , por lo que la lista completa de polinomios que pertenecen al será:

Esta naturaleza permite representar los polinomios utilizando solamente el valor de sus coeficientes.

Sumas y restas

Para sumar o restar polinomios en un sólo hay que sumar/restar cada coeficiente módulo . En los campos de Galois donde ambas operaciones son equivalentes a un xor binario.

Ejemplos de suma de polinomios en GF(8)

000 + 000 = 000
111 + 001 = 110
101 + 101 = 010

Multiplicación

La multiplicación se vuelve más compleja ya que si se hace de forma habitual, obtendremos polinomios que están fuera del campo

por lo que se hace necesario reducir el resultado módulo un polinomio que actuará como elemento neutro.

La principal caracteristica de estos polinomios es que son irreducibles (no se pueden factorizar). También son conocidos como primitivas y se puede demostrar que para todo existen múltiples primitivas.