En matemáticas , la aritmética de campos finitos es la aritmética en un campo finito (un campo que contiene un número finito de elementos ) contrariamente a la aritmética en un campo con un número infinito de elementos, como el campo de los números racionales .
Hay infinitos campos 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 campos finitos del mismo tamaño son isomorfos . El primo p se llama característica del campo, y el entero positivo n se llama dimensión del campo sobre su campo primo .
Los campos finitos se utilizan en una variedad de aplicaciones, incluso en 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 de Reed-Solomon , en algoritmos de criptografía como el algoritmo de cifrado Rijndael ( AES ), en la programación de torneos y en la diseño de experimentos .
El campo finito con p n elementos se denota GF( p n ) y también se llama campo de Galois de orden p n , en honor al fundador de la teoría de campos 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 la reducción del 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 módulo inverso p , que se puede calcular utilizando el algoritmo euclidiano extendido .
Un caso particular es GF(2) , donde la suma 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 ) se pueden representar como polinomios de grado estrictamente menor que n sobre GF( p ). Luego se realizan operaciones en módulo m(x), donde m(x) es un polinomio irreducible de grado n sobre GF( p ), por ejemplo, usando división larga polinomial . La suma es la suma habitual de polinomios, pero los coeficientes se reducen en 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 polinomiales se denomina base monomial (también conocida como "base polinómica").
Existen otras representaciones de los elementos de GF( p n ); algunos son isomórficos a la representación polinómica anterior y otros se ven bastante diferentes (por ejemplo, usando matrices). Usar una base normal puede tener ventajas en algunos contextos.
Cuando el primo es 2, es convencional expresar elementos de GF( p n ) como números binarios , con el coeficiente de cada término de 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 mónico irreducible de grado n que tiene coeficientes en el cuerpo finito GF( q ) , donde q = pt 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 campo finito, esto implica que x es un elemento primitivo. Existe 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 campo.
En los siguientes ejemplos es mejor no utilizar la representación polinómica, ya que el significado de x cambia entre los ejemplos. El polinomio mónico irreducible 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 polinómica esto sería x ), es decir, λ 8 + λ 4 + λ 3 + λ + 1 = 0 . Ahora λ 51 = 1 , entonces λ no es un elemento primitivo de GF(2 8 ) y genera un subgrupo multiplicativo de orden 51. [5] El polinomio mónico irreducible x 8 + x 4 + x 3 + x 2 + 1 sobre GF (2) es primitivo y las 8 raíces son generadoras de GF(2 8 ) .
Todos los GF(2 8 ) tienen un total de 128 generadores (ver Número de elementos primitivos ), y para un polinomio primitivo, 8 de ellos son raíces del polinomio reductor. Tener x como generador de un campo finito es beneficioso para muchas operaciones matemáticas computacionales.
La suma y la resta se realizan sumando o restando dos de estos polinomios y reduciendo el resultado módulo a la característica.
En un campo finito con característica 2, la suma módulo 2, la resta módulo 2 y XOR son idénticos. De este modo,
Bajo 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 elimina cuando la respuesta se reduce en módulo 2.
Aquí hay 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 campo finito es un módulo de multiplicación, un polinomio reductor irreducible que se utiliza para definir el campo finito. (Es decir, es una multiplicación seguida de una división utilizando el polinomio reductor como divisor; el resto es el producto). El símbolo "•" puede usarse para indicar la multiplicación en un cuerpo finito.
Rijndael (estandarizado como AES) utiliza el característico campo finito 2 con 256 elementos, que también puede denominarse campo 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 división larga (que se muestra usando notación binaria, ya que se adapta bien a la tarea. Tenga en cuenta que en el ejemplo se aplica OR exclusivo y no resta aritmética, como se podría usar en la división larga de la 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 se muestra arriba. Ocho bits son suficientes porque sólo son posibles los grados 0 a 7 en los términos de cada polinomio (reducido).
Este algoritmo utiliza tres variables (en el sentido de la 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 inicio y al final del algoritmo, y al inicio y al final de cada iteración, esta invariante es verdadera: a b + p es el producto. Obviamente, esto es cierto cuando se inicia el algoritmo. Cuando finalice el algoritmo, aob será 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 superior del polinomio irreducible y lleva suman módulo 2 a 0.Este algoritmo se generaliza fácilmente a la multiplicación sobre otros campos de la característica 2, cambiando las longitudes de a , byp y el valor de0x1b manera apropiada.
El inverso multiplicativo de un elemento a de un campo finito se puede calcular de varias maneras diferentes:
Al desarrollar algoritmos para el cálculo de campos de Galois en campos pequeños de Galois, 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 búsquedas en tablas para las funciones log g ( a ) y g y y una operación de suma de enteros. Esto explota la propiedad de que cada campo finito contiene generadores. En el ejemplo del campo 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 generador es ser irreducible .
Una implementación debe probar el caso especial de que aob sea cero , ya que el producto también será cero.
Esta misma estrategia se puede utilizar para determinar el inverso multiplicativo con 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 . Entonces esto se puede realizar con dos tablas de consulta y una resta de números enteros. Usar esta idea para la exponenciación también genera beneficios:
Esto requiere dos búsquedas de tablas, 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 dichas implementaciones, ya que la arquitectura de caché de muchos microprocesadores conduce a tiempos variables para el acceso a la memoria. Esto puede llevar a implementaciones que sean vulnerables a un ataque de sincronización .
Para campos binarios GF(2 n ), la multiplicación de campos se puede implementar usando una multiplicación sin acarreo como el conjunto de instrucciones CLMUL , que es bueno para n ≤ 64. Una multiplicación usa una multiplicación sin acarreo para producir un producto (hasta 2 n − 1 bits ), otra multiplicación inútil 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 ⊕ ((campo polinomio) ⌊producto / (polinomio de campo)⌋). Los últimos 3 pasos (pclmulqdq, pclmulqdq, xor) se utilizan en el paso de reducción de Barrett para un cálculo rápido de CRC utilizando la instrucción x86 pclmulqdq. [7]
Cuando k es un número compuesto , existirán isomorfismos desde un campo binario GF(2 k ) a un campo de extensión de uno de sus subcampos, 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 compensación de que los elementos ahora están representados en un subcampo más grande. [8] Para reducir el número de puertas para implementaciones de hardware, el proceso puede implicar anidamiento múltiple, como el mapeo de GF(2 8 ) a GF(((2 2 ) 2 ) 2 ). [9] Existe una restricción de implementación: las operaciones en las dos representaciones deben ser compatibles, por lo que se necesita el uso explícito del isomorfismo. Más precisamente, el isomorfismo se denotará por map(), es una biyección que mapea un elemento de GF(2 k ) a GF((2 m ) n ), satisfaciendo: map( a + b ) = map( a ) + map( b ) y map( a b ) = map( a ) map( b ) , donde las operaciones en el lado izquierdo ocurren en GF(2 k ) antes del mapeo y las operaciones en el lado derecho ocurren en GF((2 m ) n ) después del mapeo. [10] El isomorfismo generalmente se implementa con una matriz de k filas por k bits, que se utiliza para realizar una multiplicación matricial sobre GF(2) de un elemento de GF(2 k ) tratado como una matriz de k filas por 1 bit. Defina α como un elemento primitivo de GF(2 k ) y β como un elemento primitivo de GF((2 m ) n ). Entonces β j = mapa ( α j ) y α j = mapa −1 ( β j ). Los valores de α y β determinan la matriz de mapeo y su inversa. Dado que las matemáticas reales se realizan en GF((2 m ) n ), el polinomio reductor para GF((2 m ) n ) suele ser primitivo y β = x en GF((2 m ) n). Para cumplir con la restricción de compatibilidad para la suma y la multiplicación, se realiza una búsqueda para elegir cualquier elemento primitivo α de GF(2 k ) que cumpla con la restricción. En el caso en que el polinomio reductor para GF(2 k ) sea primitivo, es posible un método de mapeo alternativo: los coeficientes de 1 bit del polinomio reductor para GF(2 k ) se interpretan como elementos de m bits 0 o 1 de GF(2 m) . ), y habrá m factores primitivos de grado n , cualquiera de los cuales puede usarse como polinomio reductor para GF((2 m ) n ). El mapeo a un campo compuesto se puede generalizar para mapear GF( p k ) a un campo compuesto como GF(( p m ) n ), para p cualquier primo.
Aquí hay 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 campesino ruso :
/* Suma dos números en el campo finito GF(2^8) */ uint8_t gadd ( uint8_t a , uint8_t b ) { return a ^ b ; } /* Multiplica dos números en el campo finito GF(2^8) definido * por la relación polinómica módulo x^8 + x^4 + x^3 + x + 1 = 0 * (la otra forma es hacer una multiplicación sin acarreo seguida por 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 de b tiene un término constante, suma el a correspondiente a p */ pag ^= a ; /* la suma en GF(2^m) es un XOR de los coeficientes polinomiales */ if ( a & 0x80 ) /* Módulo GF: si a tiene un término distinto de cero x^7, entonces debe reducirse cuando se convierta 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 ; } devolver p ; } Este ejemplo tiene fugas de caché, temporización y predicción de bifurcaciones en el canal lateral , 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 { ubytep = 0 ; foreach ( contador de ubytes 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 & máscara )); segundo >>= 1 ; } devolver p ; } void main () { importar estándar . stdio , estándar . conversión ; ancho de enumeración = ubyte . máx + 1 , alto = ancho ; auto f = Archivo ( "rijndael_finite_field_multiplication.pgm" , "wb" ); F. writefln ( "P5\n%d %d\n255" , ancho , alto ); foreach ( inmutable y ; 0 .. altura ) foreach ( inmutable x ; 0 .. ancho ) { inmutable char c = gMul ( x . to ! ubyte , y . to ! ubyte ); F. escribir ( c ); } } Este ejemplo no utiliza ramas ni búsquedas de tablas para evitar canales laterales y, por lo tanto, es adecuado para su uso en criptografía.