Cuerpos finitos: sumar y multiplicar con pocos símbolos

En la lección anterior los símbolos eran bits y casi no necesitamos hacer cuentas con ellos. A partir de ahora sí: para construir códigos buenos hay que sumar palabras, multiplicarlas por números y resolver sistemas de ecuaciones, igual que en álgebra lineal. Para eso los símbolos deben comportarse como números normales. Los bits lo hacen (con $1+1=0$), pero un código potente como el de los QR o el de un CD trabaja con bytes, que son 256 símbolos distintos. ¿Cómo se suman y se multiplican bytes de forma que todo siga funcionando? La respuesta son los cuerpos finitos.

La idea

En álgebra lineal usas los números reales: puedes sumar, restar, multiplicar y, lo importante, dividir entre cualquier número distinto de cero. Eso es lo que permite despejar una incógnita o aplicar Gauss sin que nada se rompa. Un conjunto con esas cuatro operaciones y las propiedades de siempre se llama cuerpo.

Los reales son infinitos, y en un código necesitamos un alfabeto finito. ¿Existen cuerpos con un número finito de elementos? Sí, y se llaman cuerpos finitos. Los bits $\{0,1\}$ con la aritmética módulo 2 son el más pequeño. Hay cuerpos de 3, 4, 5, 7, 8, 9, 11… elementos, y uno de 256 elementos, que es el que usan los QR y la demo del curso.

Repaso Qué es un cuerpo

Un cuerpo es un conjunto con una suma y una multiplicación que cumplen: son conmutativas y asociativas, la multiplicación se reparte sobre la suma, existen el 0 (neutro de la suma) y el 1 (neutro de la multiplicación, con $1\neq 0$), todo elemento tiene opuesto y, además, todo elemento distinto de 0 tiene inverso multiplicativo. Esa última condición es la que permite dividir. Los racionales, los reales y los complejos son cuerpos; los enteros no lo son, porque el 2 no tiene inverso entero.

Los enteros módulo p

La construcción más sencilla es la «aritmética del reloj». Fijado un entero $n\ge 2$, $\mathbb{Z}_n=\{0,1,\dots,n-1\}$ con la suma y el producto usuales, tomando siempre el resto de dividir entre $n$. Por ejemplo, en $\mathbb{Z}_7$: $5+4=9=2$ y $3\cdot 5=15=1$.

Si $p$ es primo, $\mathbb{Z}_p$ es un cuerpo, que se escribe también $\mathbb{F}_p$. La razón es que todo elemento no nulo tiene inverso. En $\mathbb{Z}_7$, los inversos son:

$a$	1	2	3	4	5	6
$a^{-1}$	1	4	5	2	3	6

(por ejemplo $2\cdot 4=8=1$). Con inversos, se puede dividir: $a/b=a\cdot b^{-1}$.

Si $n$ no es primo, $\mathbb{Z}_n$ no es un cuerpo. Mira $\mathbb{Z}_4$: $2\cdot 2=4=0$. Dos números no nulos que al multiplicarse dan 0. Entonces el 2 no puede tener inverso (si lo tuviera, multiplicando $2\cdot 2=0$ por él saldría $2=0$) y ecuaciones tan simples como $2x=1$ no tienen solución, mientras que $2x=0$ tiene dos: $x=0$ y $x=2$. Por eso $\mathbb{Z}_4^n$ no es un espacio vectorial y la teoría de este curso (subespacios, bases, dimensión, Gauss) no se le aplica. Existen códigos sobre el anillo $\mathbb{Z}_4$, como los de Kerdock y Preparata, pero son otra historia. Para tener 4 símbolos usaremos otro conjunto de 4 elementos que sí es un cuerpo, y lo construimos enseguida.

Cuerpos de $p^m$ elementos

¿Qué tamaños admiten un cuerpo? Se sabe que existe un cuerpo finito de $q$ elementos si y solo si $q$ es una potencia de un primo, $q=p^m$, y que, salvo renombrar los elementos, es único. Se escribe $\mathbb{F}_q$. Así que hay un cuerpo de 2, 3, 4, 5, 7, 8, 9… elementos, pero ninguno de 6, 10 ni 12.

Para construir $\mathbb{F}_{p^m}$ se usa una idea que ya conoces de $\mathbb{Z}_p$, pero con polinomios: se trabaja con polinomios en $x$ con coeficientes en $\mathbb{F}_p$ y se toma el resto al dividir entre un polinomio irreducible de grado $m$ (que no se pueda factorizar), igual que antes se tomaba el resto al dividir entre un primo.

Repaso Restos de polinomios

Dividir polinomios es como dividir enteros: el resto tiene grado menor que el divisor. Trabajar «módulo $x^2+x+1$» significa sustituir cada polinomio por su resto. Basta con recordar la regla $x^2=x+1$ (en coeficientes módulo 2, $-1=1$, así que $x^2+x+1=0$ equivale a $x^2=x+1$) y aplicarla cada vez que aparece $x^2$. Con coeficientes binarios todo polinomio de grado menor que 2 es $0$, $1$, $x$ o $x+1$: cuatro posibilidades.

El cuerpo $\mathbb{F}_4$

El polinomio $x^2+x+1$ es irreducible sobre $\mathbb{F}_2$: no vale 0 ni en $x=0$ ni en $x=1$, así que no tiene raíces, y un polinomio de grado 2 sin raíces no se factoriza (si se factorizara, tendría un factor de grado 1, es decir, una raíz). Así que nos inventamos una.

Repaso Inventar una raíz

La ecuación $x^2+1=0$ no tiene solución real, así que se inventa un número $i$ con $i^2=-1$ y se trabaja con $a+bi$; cada vez que sale $i^2$, se cambia por $-1$. Aquí hacemos lo mismo: $x^2+x+1$ no tiene raíces en $\{0,1\}$, así que inventamos un símbolo $\alpha$ con $\alpha^2+\alpha+1=0$ y trabajamos con $a+b\alpha$, con $a,b\in\{0,1\}$. Cada vez que sale $\alpha^2$, se cambia por $\alpha+1$. Por ejemplo, $\alpha^3=\alpha\cdot\alpha^2=\alpha^2+\alpha=(\alpha+1)+\alpha=1$. No hace falta saber «qué es» $\alpha$: basta con la regla.

Sea, pues, $\alpha$ una raíz de $x^2+x+1$, es decir, $\alpha^2=\alpha+1$. Entonces

$$\mathbb{F}_4=\{0,\ 1,\ \alpha,\ \alpha+1\}.$$

La suma es la de polinomios con coeficientes módulo 2. La multiplicación usa la regla $\alpha^2=\alpha+1$. Las tablas son:

$+$	0	1	$\alpha$	$\alpha+1$
0	0	1	$\alpha$	$\alpha+1$
1	1	0	$\alpha+1$	$\alpha$
$\alpha$	$\alpha$	$\alpha+1$	0	1
$\alpha+1$	$\alpha+1$	$\alpha$	1	0

$\cdot$	0	1	$\alpha$	$\alpha+1$
0	0	0	0	0
1	0	1	$\alpha$	$\alpha+1$
$\alpha$	0	$\alpha$	$\alpha+1$	1
$\alpha+1$	0	$\alpha+1$	1	$\alpha$

Por ejemplo, $\alpha\cdot\alpha=\alpha^2=\alpha+1$ y $\alpha\cdot(\alpha+1)=\alpha^2+\alpha=(\alpha+1)+\alpha=1$. Ahora sí: en cada fila de la tabla del producto, salvo la del 0, aparece un 1, es decir, todo elemento no nulo tiene inverso. Nótese que $\mathbb{F}_4$ no es $\mathbb{Z}_4$: aquí $1+1=0$ (todos los elementos son su propio opuesto), mientras que en $\mathbb{Z}_4$ $1+1=2$.

El cuerpo $\mathbb{F}_8$

Igual, pero con un polinomio irreducible de grado 3: $x^3+x+1$. No tiene raíces en $\mathbb{F}_2$, y un polinomio de grado 3 que se factoriza tiene un factor de grado 1, es decir, una raíz; así que es irreducible. Sea $\alpha$ una raíz: $\alpha^3=\alpha+1$. Los elementos son los polinomios de grado menor que 3 en $\alpha$, es decir, $a_0+a_1\alpha+a_2\alpha^2$ con $a_i\in\{0,1\}$: ocho en total. Y aquí ocurre algo muy útil. Calculando las potencias de $\alpha$ aparecen todos los elementos no nulos:

potencia	polinomio en $\alpha$	vector $(1,\alpha,\alpha^2)$
$\alpha^0$	$1$	$(1,0,0)$
$\alpha^1$	$\alpha$	$(0,1,0)$
$\alpha^2$	$\alpha^2$	$(0,0,1)$
$\alpha^3$	$\alpha+1$	$(1,1,0)$
$\alpha^4$	$\alpha^2+\alpha$	$(0,1,1)$
$\alpha^5$	$\alpha^2+\alpha+1$	$(1,1,1)$
$\alpha^6$	$\alpha^2+1$	$(1,0,1)$

y $\alpha^7=1$. Ojo con el orden: el vector $(a_0,a_1,a_2)$ es $a_0+a_1\alpha+a_2\alpha^2$, con el término constante primero. Cada fila sale de la anterior multiplicando por $\alpha$ y usando $\alpha^3=\alpha+1$: por ejemplo, $\alpha^4=\alpha\cdot\alpha^3=\alpha^2+\alpha$ y $\alpha^5=\alpha^3+\alpha^2=\alpha^2+\alpha+1$.

Esta tabla es una «calculadora» completa de $\mathbb{F}_8$ con dos reglas:

• Sumar es sumar los vectores módulo 2 (columna de la derecha).
• Multiplicar es sumar los exponentes módulo 7: $\alpha^i\cdot\alpha^j=\alpha^{i+j}$, con $\alpha^7=1$.

Todo elemento no nulo es una potencia de $\alpha$; a un elemento con esa propiedad se le llama primitivo. Todo cuerpo finito tiene alguno (es un teorema que aquí aceptamos sin demostrar), y eso es lo que hace tan cómodo calcular con ellos, y lo usaremos para los códigos de Reed-Solomon.

Ejemplo resuelto

Vamos a calcular en $\mathbb{F}_8$ el producto $(\alpha^2+\alpha)(\alpha^2+1)$ de dos maneras y a resolver un sistema.

Producto, a la fuerza bruta. Desarrollamos y reducimos con $\alpha^3=\alpha+1$ y $\alpha^4=\alpha^2+\alpha$:

$$(\alpha^2+\alpha)(\alpha^2+1)=\alpha^4+\alpha^2+\alpha^3+\alpha=(\alpha^2+\alpha)+\alpha^2+(\alpha+1)+\alpha=\alpha+1,$$

porque los dos $\alpha^2$ se anulan y de los tres $\alpha$ queda uno.

Producto, con la tabla. Según la tabla, $\alpha^2+\alpha=\alpha^4$ y $\alpha^2+1=\alpha^6$. Multiplicamos sumando exponentes: $\alpha^{4+6}=\alpha^{10}=\alpha^3=\alpha+1$. Sale lo mismo, y mucho más rápido.

Un sistema. Resolvamos en $\mathbb{F}_8$

$$\begin{cases}x+\alpha y=\alpha^2\\ \alpha x+y=1\end{cases}$$

De la primera, $x=\alpha^2+\alpha y$. Sustituimos en la segunda: $\alpha^3+\alpha^2y+y=1$, es decir, $(\alpha^2+1)y=1+\alpha^3$. Como $1+\alpha^3=1+\alpha+1=\alpha$ y $\alpha^2+1=\alpha^6$:

$$y=\frac{\alpha}{\alpha^6}=\alpha^{1-6}=\alpha^{-5}=\alpha^{2}.$$

(Dividir es restar exponentes, siempre módulo 7: $-5\equiv 2$.) Y entonces $x=\alpha^2+\alpha\cdot\alpha^2=\alpha^2+\alpha^3=(0,0,1)+(1,1,0)=(1,1,1)=\alpha^5$. Comprobamos en la segunda ecuación: $\alpha\cdot\alpha^5+\alpha^2=\alpha^6+\alpha^2=(1,0,1)+(0,0,1)=(1,0,0)=1$. La solución es $x=\alpha^5$, $y=\alpha^2$, única: justo lo que garantiza que estemos en un cuerpo.

Para qué sirve esto

Cuando en las próximas lecciones el alfabeto sea $\mathbb{F}_q$, los códigos lineales serán subespacios de $\mathbb{F}_q^n$ y todo el álgebra lineal funcionará como la conoces. En los códigos binarios, $q=2$. En los de Reed-Solomon de las lecciones 9 a 11 usaremos $\mathbb{F}_8$ para el ejemplo. En la práctica, los QR, los CD y la demo usan $\mathbb{F}_{256}$ (llamado a veces GF(256), de $256=2^8$): cada símbolo es un byte, sumar bytes es hacer el «o exclusivo» bit a bit y multiplicarlos sigue la misma idea que en $\mathbb{F}_8$, con un polinomio irreducible de grado 8.

Ejercicios

Ejercicio 1

En $\mathbb{Z}_7$, calcula $3^{-1}$ y resuelve $3x=4$.

Ver la solución

Buscamos $b$ con $3b\equiv 1 \pmod 7$. Probando, $3\cdot 5=15=2\cdot 7+1$, así que $3^{-1}=5$. Entonces $x=4\cdot 3^{-1}=4\cdot 5=20=2\cdot7+6$, es decir, $x=6$. Comprobación: $3\cdot 6=18=2\cdot7+4$, que da 4.

Ejercicio 2

Con la tabla de $\mathbb{F}_8$, calcula: a) $\alpha^3\cdot\alpha^5$; b) $\alpha^4+\alpha^5$; c) $\alpha^3+\alpha^6$; d) el inverso de $\alpha^5$.

Ver la solución

a) Sumamos exponentes: $\alpha^{3+5}=\alpha^8=\alpha^7\cdot\alpha=\alpha$.

b) $\alpha^4=(0,1,1)$ y $\alpha^5=(1,1,1)$. Su suma es $(1,0,0)=1=\alpha^0$.

c) $\alpha^3=(1,1,0)$ y $\alpha^6=(1,0,1)$. Su suma es $(0,1,1)=\alpha^4$.

d) Buscamos $j$ con $5+j\equiv 0 \pmod 7$: $j=2$. El inverso de $\alpha^5$ es $\alpha^2$, porque $\alpha^5\cdot\alpha^2=\alpha^7=1$.

Ejercicio 3

Explica por qué $\mathbb{Z}_6$ no es un cuerpo. Después resuelve en $\mathbb{F}_8$ la ecuación $\alpha^2x=\alpha^5+1$.

Ver la solución

En $\mathbb{Z}_6$, $2\cdot 3=6=0$ con $2$ y $3$ no nulos, así que ni el 2 ni el 3 tienen inverso (como en $\mathbb{Z}_4$ con el 2). Tampoco existe ningún cuerpo de 6 elementos, porque 6 no es potencia de un primo.

Para la ecuación en $\mathbb{F}_8$: $\alpha^5+1=(1,1,1)+(1,0,0)=(0,1,1)=\alpha^4$. Entonces $x=\alpha^4/\alpha^2=\alpha^2$. Comprobación: $\alpha^2\cdot\alpha^2=\alpha^4$.

En resumen

• Para hacer álgebra lineal con los símbolos de un código necesitamos un cuerpo: sumar, restar, multiplicar y dividir entre lo no nulo.
• $\mathbb{Z}_p$ con $p$ primo es un cuerpo; $\mathbb{Z}_4$ o $\mathbb{Z}_6$ no lo son, porque tienen divisores de cero.
• Existe un cuerpo de $q$ elementos si y solo si $q$ es potencia de un primo, y se construye con polinomios módulo uno irreducible.
• En $\mathbb{F}_8$, sumar es sumar vectores módulo 2 y multiplicar es sumar exponentes de $\alpha$ módulo 7.
• Los QR, los CD y la demo trabajan con $\mathbb{F}_{256}$: cada símbolo es un byte.

Siguiente lección: Códigos lineales: un código que es un subespacio