En matemáticas , la aritmética de cuerpos finitos es la aritmética en un cuerpo finito (un cuerpo que contiene un número finito de elementos ), al contrario de la aritmética en un cuerpo con un número infinito de elementos, como el cuerpo de los números racionales .
Existen infinitos cuerpos finitos diferentes. Su número de elementos es necesariamente de la forma p n donde p es un número primo y n es un entero positivo , y dos cuerpos finitos del mismo tamaño son isomorfos . El primo p se denomina característica del cuerpo y el entero positivo n se denomina dimensión del cuerpo sobre su cuerpo primo .
Los campos finitos se utilizan en una variedad de aplicaciones, incluida la teoría de codificación clásica en códigos de bloques lineales como los códigos BCH y la corrección de errores Reed-Solomon , en algoritmos de criptografía como el algoritmo de cifrado Rijndael ( AES ), en la programación de torneos y en el diseño de experimentos .
El cuerpo finito con p n elementos se denota GF( p n ) y también se llama cuerpo de Galois de orden p n , en honor al fundador de la teoría de cuerpos finitos, Évariste Galois . GF( p ), donde p es un número primo, es simplemente el anillo de números enteros módulo p . Es decir, se pueden realizar operaciones (suma, resta, multiplicación) utilizando la operación habitual con números enteros, seguida de una reducción módulo p . Por ejemplo, en GF(5), 4 + 3 = 7 se reduce a 2 módulo 5. La división es la multiplicación por el inverso módulo p , que se puede calcular utilizando el algoritmo euclidiano extendido .
Un caso particular es GF(2) , donde la adición es OR exclusivo (XOR) y la multiplicación es AND . Como el único elemento invertible es 1, la división es la función identidad .
Los elementos de GF( p n ) pueden representarse como polinomios de grado estrictamente menor que n sobre GF( p ). Luego se realizan operaciones módulo m(x) donde m(x) es un polinomio irreducible de grado n sobre GF( p ), por ejemplo usando la división larga de polinomios . La adición es la adición habitual de polinomios, pero los coeficientes se reducen módulo p . La multiplicación también es la multiplicación habitual de polinomios, pero con coeficientes multiplicados módulo p y polinomios multiplicados módulo el polinomio m(x) . [1] Esta representación en términos de coeficientes polinómicos se llama base monomial (también conocida como 'base polinomial').
Existen otras representaciones de los elementos de GF( p n ); algunas son isomorfas a la representación polinómica anterior y otras son bastante diferentes (por ejemplo, utilizando matrices). El uso de una base normal puede tener ventajas en algunos contextos.
Cuando el primo es 2, es convencional expresar los elementos de GF( p n ) como números binarios , con el coeficiente de cada término en un polinomio representado por un bit en la expresión binaria del elemento correspondiente. Las llaves ("{" y "}" ) o delimitadores similares se agregan comúnmente a los números binarios, o a sus equivalentes hexadecimales, para indicar que el valor proporciona los coeficientes de una base de un campo, representando así un elemento del campo. Por ejemplo, las siguientes son representaciones equivalentes del mismo valor en un campo finito característico 2:
Hay muchos polinomios irreducibles (a veces llamados polinomios reductores ) que pueden usarse para generar un campo finito, pero no todos dan lugar a la misma representación del campo.
Un polinomio irreducible mónico de grado n que tiene coeficientes en el cuerpo finito GF( q ), donde q = p t para algún primo p y entero positivo t , se llama polinomio primitivo si todas sus raíces son elementos primitivos de GF( q n ). [2] [3] En la representación polinómica del cuerpo finito, esto implica que x es un elemento primitivo. Hay al menos un polinomio irreducible para el cual x es un elemento primitivo. [4] En otras palabras, para un polinomio primitivo, las potencias de x generan cada valor distinto de cero en el cuerpo.
En los siguientes ejemplos es mejor no usar la representación polinomial, ya que el significado de x cambia entre los ejemplos. El polinomio irreducible mónico x 8 + x 4 + x 3 + x + 1 sobre GF(2) no es primitivo. Sea λ una raíz de este polinomio (en la representación polinomial sería x ), es decir, λ 8 + λ 4 + λ 3 + λ + 1 = 0 . Ahora λ 51 = 1 , por lo que λ no es un elemento primitivo de GF(2 8 ) y genera un subgrupo multiplicativo de orden 51. [5] El polinomio irreducible mónico x 8 + x 4 + x 3 + x 2 + 1 sobre GF(2) es primitivo, y las 8 raíces son generadores de GF(2 8 ) .
Todos los GF(2 8 ) tienen un total de 128 generadores (véase Número de elementos primitivos ) y, para un polinomio primitivo, 8 de ellos son raíces del polinomio reductor. Tener x como generador para un cuerpo finito es beneficioso para muchas operaciones matemáticas computacionales.
La suma y la resta se realizan sumando o restando dos de estos polinomios entre sí y reduciendo el resultado módulo la característica.
En un cuerpo finito con característica 2, la adición módulo 2, la resta módulo 2 y la operación XOR son idénticas. Por lo tanto,
En la suma regular de polinomios, la suma contendría un término 2 x 6. Este término se convierte en 0 x 6 y se omite cuando la respuesta se reduce módulo 2.
A continuación se muestra una tabla con la suma algebraica normal y la suma característica de 2 campos finitos de algunos polinomios:
En aplicaciones de informática, las operaciones se simplifican para campos finitos de característica 2, también llamados campos de Galois GF(2 n ) , lo que hace que estos campos sean opciones especialmente populares para las aplicaciones.
La multiplicación en un cuerpo finito es una multiplicación módulo de un polinomio reductor irreducible que se utiliza para definir el cuerpo finito (es decir, es una multiplicación seguida de una división que utiliza el polinomio reductor como divisor; el resto es el producto). El símbolo "•" puede utilizarse para indicar la multiplicación en un cuerpo finito.
Rijndael (estandarizado como AES) utiliza el cuerpo finito característico 2 con 256 elementos, que también puede denominarse cuerpo de Galois GF(2 8 ). Emplea el siguiente polinomio reductor para la multiplicación:
Por ejemplo, {53} • {CA} = {01} en el campo de Rijndael porque
y
Esto último se puede demostrar mediante una división larga (que se muestra utilizando notación binaria, ya que se presta bien a la tarea. Observe que en el ejemplo se aplica OR exclusivo y no resta aritmética, como se podría usar en una división larga de escuela primaria):
11111101111110 (mod) 100011011 ^100011011 01110000011110 ^ 100011011 0110110101110 ^100011011 010101110110 ^100011011 00100011010 ^100011011 000000001
(Los elementos {53} y {CA} son inversos multiplicativos entre sí ya que su producto es 1. )
La multiplicación en este campo finito particular también se puede realizar utilizando una versión modificada del " algoritmo del campesino ". Cada polinomio se representa utilizando la misma notación binaria que la anterior. Ocho bits son suficientes porque solo son posibles los grados 0 a 7 en los términos de cada polinomio (reducido).
Este algoritmo utiliza tres variables (en el sentido de programación informática), cada una con una representación de ocho bits. a y b se inicializan con los multiplicandos; p acumula el producto y debe inicializarse a 0.
Al principio y al final del algoritmo, y al principio y al final de cada iteración, esta invariante es verdadera: a b + p es el producto. Esto es obviamente cierto cuando el algoritmo comienza. Cuando el algoritmo termina, a o b serán cero, por lo que p contendrá el producto.
0x1b(00011011 en binario). 0x1bcorresponde al polinomio irreducible con el término alto eliminado. Conceptualmente, el término alto del polinomio irreducible y el acarreo suman módulo 2 a 0.Este algoritmo se generaliza fácilmente a la multiplicación sobre otros campos de característica 2, cambiando las longitudes de a , b y p y el valor 0x1bapropiadamente.
El inverso multiplicativo de un elemento a de un campo finito se puede calcular de diferentes maneras:
Al desarrollar algoritmos para el cálculo del campo de Galois en campos de Galois pequeños, un enfoque común de optimización del rendimiento es encontrar un generador g y utilizar la identidad:
implementar la multiplicación como una secuencia de consultas de tabla para las funciones log g ( a ) y g y y una operación de suma de enteros. Esto explota la propiedad de que cada cuerpo finito contiene generadores. En el ejemplo del cuerpo de Rijndael, el polinomio x + 1 (o {03}) es uno de esos generadores. Una condición necesaria pero no suficiente para que un polinomio sea un generador es que sea irreducible .
Una implementación debe probar el caso especial de que a o b sean cero, ya que el producto también será cero.
Esta misma estrategia se puede utilizar para determinar el inverso multiplicativo con la identidad:
Aquí, el orden del generador, | g |, es el número de elementos distintos de cero del campo. En el caso de GF(2 8 ) esto es 2 8 − 1 = 255 . Es decir, para el ejemplo de Rijndael: ( x + 1) 255 = 1 . Por lo tanto, esto se puede realizar con dos tablas de consulta y una resta de números enteros. El uso de esta idea para la exponenciación también tiene sus ventajas:
Esto requiere dos búsquedas en la tabla, una multiplicación de números enteros y una operación de módulo de números enteros. Nuevamente, se debe realizar una prueba para el caso especial a = 0 .
Sin embargo, en las implementaciones criptográficas, hay que tener cuidado con ellas, ya que la arquitectura de caché de muchos microprocesadores genera tiempos variables para el acceso a la memoria, lo que puede dar lugar a implementaciones vulnerables a ataques de tiempo .
Para los campos binarios GF(2 n ), la multiplicación de campos se puede implementar utilizando una multiplicación sin acarreo como el conjunto de instrucciones CLMUL , que es bueno para n ≤ 64. Una multiplicación utiliza una multiplicación sin acarreo para producir un producto (hasta 2 n − 1 bits), otra multiplicación sin acarreo de un inverso precalculado del polinomio de campo para producir un cociente = ⌊producto / (polinomio de campo)⌋, una multiplicación del cociente por el polinomio de campo, luego un xor: resultado = producto ⊕ ((polinomio de campo) ⌊producto / (polinomio de campo)⌋). Los últimos 3 pasos (pclmulqdq, pclmulqdq, xor) se utilizan en el paso de reducción de Barrett para el cálculo rápido de CRC utilizando la instrucción pclmulqdq x86 . [7]
Cuando k es un número compuesto , existirán isomorfismos de un cuerpo binario GF(2 k ) a un cuerpo de extensión de uno de sus subcuerpos, es decir, GF((2 m ) n ) donde k = m n . La utilización de uno de estos isomorfismos puede simplificar las consideraciones matemáticas, ya que el grado de extensión es menor con la desventaja de que los elementos ahora están representados en un subcuerpo más grande. [8] Para reducir el número de puertas para las implementaciones de hardware, el proceso puede implicar anidamiento múltiple, como el mapeo de GF(2 8 ) a GF(((2 2 ) 2 ) 2 ). [9]
A continuación se muestra un código C que sumará y multiplicará números en el campo finito característico 2 de orden 2 8 , utilizado por ejemplo por el algoritmo de Rijndael o Reed–Solomon, utilizando el algoritmo de multiplicación campesina rusa :
/* Suma dos números en el campo finito GF(2^8) */ uint8_t gadd ( uint8_t a , uint8_t b ) { return a ^ b ; } /* Multiplicar dos números en el cuerpo finito GF(2^8) definido * por la relación polinomial módulo x^8 + x^4 + x^3 + x + 1 = 0 * (la otra forma es hacer una multiplicación sin acarreo seguida de una reducción modular) */ uint8_t gmul ( uint8_t a , uint8_t b ) { uint8_t p = 0 ; /* acumulador para el producto de la multiplicación */ while ( a != 0 && b != 0 ) { if ( b & 1 ) /* si el polinomio para b tiene un término constante, sumar el a correspondiente a p */ p ^= a ; /* la suma en GF(2^m) es un XOR de los coeficientes del polinomio */ if ( a & 0x80 ) /* GF módulo: si a tiene un término distinto de cero x^7, entonces debe reducirse cuando se convierte en x^8 */ a = ( a << 1 ) ^ 0x11b ; /* resta (XOR) el polinomio primitivo x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – puedes cambiarlo pero debe ser irreducible */ else a <<= 1 ; /* equivalente a a*x */ b >>= 1 ; } return p ; } Este ejemplo tiene fugas de canales laterales de caché, sincronización y predicción de ramas , y no es adecuado para su uso en criptografía.
Este programa D multiplicará números en el campo finito de Rijndael y generará una imagen PGM :
/** Multiplica dos números en el campo finito GF(2^8) definido por el polinomio x^8 + x^4 + x^3 + x + 1. */ ubyte gMul ( ubyte a , ubyte b ) pure nothrow { ubyte p = 0 ; foreach ( contador ubyte inmutable ; 0 .. 8 ) { p ^= -( b & 1 ) &a a ; máscara automática = -(( a >> 7 ) & 1 ); // 0b1_0001_1011 es x^8 + x^4 + x^3 + x + 1. a = cast ( ubyte )(( a << 1 ) ^ ( 0b1_0001_1011 & mask )); b >>= 1 ; } devolver p ; } void main ( ) { importar std.stdio , std.conv ; enumeración ancho = ubyte.max + 1 , alto = ancho ; auto f = File ( "multiplicacion_campos_finitos_rijndael.pgm" , "wb" ); f . writefln ( "P5\n%d %d\n255" , ancho , alto ); foreach ( inmutable y ; 0 .. alto ) foreach ( inmutable x ; 0 .. ancho ) { inmutable char c = gMul ( x . to ! ubyte , y . to ! ubyte ); f . write ( c ); } } Este ejemplo no utiliza ramas ni búsquedas de tablas para evitar canales secundarios y, por lo tanto, es adecuado para su uso en criptografía.