Aritmética de cuerpos finitos

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 ), a diferencia 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 diversas aplicaciones, incluyendo la teoría clásica de codificación en códigos de bloques lineales como los códigos BCH y la corrección de errores de Reed-Solomon , en algoritmos criptográficos como el algoritmo de cifrado Rijndael ( AES ), en la programación de torneos y en el diseño de experimentos .

Representación polinómica efectiva

El cuerpo finito con p ⁿ elementos se denota GF( p ⁿ ) y también se llama cuerpo de Galois de orden p ⁿ , 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 enteros módulo p . Es decir, se pueden realizar operaciones (suma, resta, multiplicación) usando la operación usual sobre enteros, seguida de la 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 usando el algoritmo euclidiano extendido .

Un caso particular es GF(2) , donde la suma es la OR exclusiva (XOR) y la multiplicación es la AND . Dado que el único elemento invertible es 1, la división es la función identidad .

Los elementos de GF( p ⁿ ) pueden representarse como polinomios de grado estrictamente menor que n sobre GF( p ). Las operaciones se realizan entonces 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 suma es la suma usual de polinomios, pero los coeficientes se reducen módulo p . La multiplicación también es la multiplicación usual 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 llama base monomial (también conocida como 'base polinomial').

Existen otras representaciones de los elementos de GF( p ⁿ ); algunas son isomorfas a la representación polinómica anterior y otras son bastante diferentes (por ejemplo, mediante matrices). El uso de una base normal puede tener ventajas en algunos contextos.

Cuando el número primo es 2, es convencional expresar los elementos de GF( p ⁿ ) como números binarios , donde el coeficiente de cada término de un polinomio se representa mediante un bit en la expresión binaria del elemento correspondiente. Comúnmente se añaden llaves ("{" y "}") o delimitadores similares a los números binarios, o a sus equivalentes hexadecimales , para indicar que el valor proporciona los coeficientes de una base de un cuerpo, representando así un elemento de dicho cuerpo. Por ejemplo, las siguientes son representaciones equivalentes del mismo valor en un cuerpo finito de característica 2:

Polinomios primitivos

Existen muchos polinomios irreducibles (a veces llamados polinomios reductores ) que pueden utilizarse para generar un cuerpo finito, pero no todos dan lugar a la misma representación del cuerpo.

Un polinomio irreducible mónico de grado $n$ con 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$ ). ^[²^]^[³^] 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. ^[⁴^] En otras palabras, para un polinomio primitivo, las potencias de $x$ generan todo valor no nulo en el cuerpo.

En los siguientes ejemplos es mejor no usar la representación polinómica, 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 polinómica esto sería $x$ ), es decir, $λ 8 + λ 4 + λ 3 + λ + 1 = 0$ . Ahora $λ 51 = 1$ , por lo que $λ$ no es un elemento primitivo de GF(2 ⁸ ) 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 todas las 8 raíces son generadores de $GF(2 8)$ .

Todos los GF(2 ⁸ ) 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.

Suma y resta

La suma y la resta se realizan sumando o restando dos de estos polinomios y reduciendo el resultado módulo la característica.

En un campo finito con característica 2, la suma módulo 2, la resta módulo 2 y la 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 ⁶ y se elimina cuando la respuesta se reduce módulo 2.

Aquí hay una tabla con la suma algebraica normal y la suma de cuerpo finito característica 2 de algunos polinomios:

En las aplicaciones de informática, las operaciones se simplifican para campos finitos de característica 2, también llamados campos de Galois GF(2 ⁿ ) , lo que hace que estos campos sean opciones especialmente populares para las aplicaciones.

Multiplicación

La multiplicación en un cuerpo finito es la multiplicación módulo un polinomio reductor irreducible que define dicho cuerpo. (Es decir, se trata de una multiplicación seguida de una división utilizando el polinomio reductor como divisor ; el resto es el producto). El símbolo "•" puede utilizarse para indicar la multiplicación en un cuerpo finito.

Campo finito de Rijndael (AES)

Rijndael (estandarizado como AES) utiliza el cuerpo finito de característica 2 con 256 elementos, que también puede denominarse cuerpo de Galois GF(2 ⁸ ). Emplea el siguiente polinomio reductor para la multiplicación:

x ⁸ + x ⁴ + x ³ + x + 1.

Por ejemplo, {53} • {CA} = {01} en el campo de Rijndael porque

y

Esto último se puede demostrar mediante la división larga (mostrada usando notación binaria, ya que se presta bien a la tarea. Nótese que en el ejemplo se aplica la disyunción exclusiva y no la resta aritmética, como se usaría en la división larga en 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 puede realizarse mediante una versión modificada del " algoritmo del campesino ". Cada polinomio se representa con la misma notación binaria que la descrita anteriormente. Ocho bits son suficientes, ya que solo son posibles los grados del 0 al 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, así como al inicio y al final de cada iteración, se cumple la siguiente invariante : a + b + p es el producto. Esto es evidente cuando el algoritmo comienza. Cuando el algoritmo finaliza, a o b serán cero, por lo que p contendrá el producto.

Ejecuta el siguiente bucle ocho veces (una vez por bit). Puedes detenerte cuando a o b sea cero antes de una iteración:
1. Si el bit más a la derecha de b está activado, se realiza una operación OR exclusiva entre el producto p y el valor de a . Esto es una suma de polinomios.
2. Desplaza b un bit a la derecha, descartando el bit más a la derecha y haciendo que el bit más a la izquierda tenga un valor de cero. Esto divide el polinomio por x , descartando el término x ^{= 0 .}
3. Lleva un registro de si el bit más a la izquierda de a está establecido en uno y llama a este valor carry .
4. Desplazamos un bit a la izquierda, descartando el bit más a la izquierda y haciendo que el nuevo bit más a la derecha sea cero. Esto multiplica el polinomio por x , pero aún necesitamos tener en cuenta el acarreo que representaba el coeficiente de x ⁷ .
5. Si el acarreo tuviera un valor de uno, exclusivo o con el número hexadecimal 0x1b(00011011 en binario). 0x1bcorresponde al polinomio irreducible con el término de orden superior eliminado. Conceptualmente, el término de orden superior del polinomio irreducible y el acarreo suman módulo 2 a 0.
p ahora tiene el producto

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 0x1bde forma apropiada.

inverso multiplicativo

El inverso multiplicativo de un elemento a de un cuerpo finito se puede calcular de varias maneras diferentes:

Multiplicando a por cada número del campo hasta que el producto sea uno. Esto es una búsqueda por fuerza bruta .
Dado que los elementos no nulos de GF( p ⁿ ) forman un grupo finito con respecto a la multiplicación, a ^{p ⁿ −1} = 1 (para a ≠ 0 ), por lo tanto, el inverso de a es a ^{p ⁿ −2} . Este algoritmo es una generalización del inverso multiplicativo modular basado en el pequeño teorema de Fermat .
La inversa multiplicativa basada en el pequeño teorema de Fermat también puede interpretarse utilizando la función de norma multiplicativa en un campo finito . Este nuevo punto de vista conduce a un algoritmo inverso basado en la función de traza aditiva en un campo finito . ^{[ 6 ]}
Mediante el uso del algoritmo euclidiano extendido .
Haciendo tablas de logaritmos y exponenciación para el campo finito, restando el logaritmo de p ⁿ − 1 y exponenciando el resultado.
Creando una tabla de inversos multiplicativos modulares para el campo finito y realizando una búsqueda.
Mediante la transformación a un campo compuesto donde la inversión es más sencilla, y la posterior transformación inversa.
Construyendo un entero especial (en caso de un cuerpo finito de orden primo) o un polinomio especial (en caso de un cuerpo finito de orden no primo) y dividiéndolo por a . ^{[ 7 ]}

Trucos de implementación

Tablas basadas en generadores

Al desarrollar algoritmos para el cálculo de campos de Galois en campos de Galois pequeños, un enfoque común de optimización del rendimiento consiste en encontrar un generador g y utilizar la identidad:

ab=g^{\log _{g}(ab)}=g^{\log _{g}(a)+\log _{g}(b)}

para 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 entera. Esto explota la propiedad de que todo 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 .

La implementación debe comprobar el caso especial en 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:

a^{-1}=g^{\log _{g}\left(a^{-1}\right)}=g^{-\log _{g}(a)}=g^{|g|-\log _{g}(a)}

Aquí, el orden del generador, | g | , es el número de elementos distintos de cero del campo. En el caso de GF(2⁸ ⁾ , esto es 2⁸ − 1 = 255. Es decir, para el ejemplo de Rijndael: ( x + 1) ^²⁵⁵ = 1. Por lo tanto ^, esto se puede realizar con dos tablas de búsqueda y una resta de enteros. El uso de esta idea para la exponenciación también resulta beneficioso:

a^{n}=g^{\log _{g}\left(a^{n}\right)}=g^{n\log _{g}(a)}=g^{n\log _{g}(a){\pmod {|g|}}}

Esto requiere dos búsquedas en tablas, una multiplicación entera y una operación de módulo entero. Nuevamente, debe realizarse una prueba para el caso especial a = 0 .

Sin embargo, en las implementaciones criptográficas, hay que tener cuidado, ya que la arquitectura de caché de muchos microprocesadores genera tiempos de acceso a la memoria variables. Esto puede dar lugar a implementaciones vulnerables a ataques de temporización .

Multiplicación sin acarreo

Para campos binarios GF(2 ⁿ ), 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 una inversa precalculada del polinomio de campo para producir un cociente = ⌊producto / (polinomio de campo)⌋, una multiplicación del cociente por el polinomio de campo, luego una operación 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 de x86 . ^{[ 8 ]}

exponente compuesto

Cuando k es un número compuesto , existirán isomorfismos de un campo binario GF(2 ^k ) a un campo de extensión de uno de sus subcampos, es decir, GF((2 ^m ) ⁿ ) donde k = m n . Utilizar uno de estos isomorfismos puede simplificar las consideraciones matemáticas ya que el grado de la extensión es menor, con la contrapartida de que los elementos ahora se representan sobre un subcampo más grande. ^{[ 9 ]} Para reducir el número de compuertas para implementaciones de hardware, el proceso puede implicar múltiples anidamientos, como mapear de GF(2 ⁸ ) a GF(((2 ² ) ² ) ² ). ^{[ 10 ]}

Ejemplos de programas

Ejemplo de programación en C

Aquí hay un código C que sumará y multiplicará números en el campo finito de característica 2 de orden 2 ⁸ , 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 modular x^8 + x^4 + x^3 + x + 1 = 0 * (la otra forma es realizar 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, suma el correspondiente a a p */ p ^= a ; /* la suma en GF(2^m) es un XOR de los coeficientes del polinomio */if ( a & 0x80 ) /* Módulo GF: si a tiene un término distinto de cero x^7, entonces debe reducirse cuando se convierte en x^8 */ a = ( a << 1 ) ^ 0x11b ; /* restar (XOR) el polinomio primitivo x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – se puede cambiar, pero debe ser irreducible */ else a <<= 1 ; /* equivalente a a*x */ b >>= 1 ; } return p ; }

Este ejemplo presenta fugas de memoria, problemas de temporización y vulnerabilidades en la predicción de bifurcaciones , por lo que no es adecuado para su uso en criptografía.

Ejemplo de programación en D

Este programa en 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 ;para cada ( contador de ubytes inmutable ; 0 .. 8 ) { p ^= -( b & 1 ) &a a ; auto mask = -(( 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 () { import std . stdio , std . conv ; enum width = ubyte . max + 1 , height = width ;auto f = File ( "rijndael_finite_field_multiplication.pgm" , "wb" ); f . writefln ( "P5\n%d %d\n255" , width , height ); foreach ( immutable y ; 0 .. height ) foreach ( immutable x ; 0 .. width ) { immutable char c = gMul ( x . to ! ubyte , y . to ! ubyte ); f . write ( c ); } }

Este ejemplo no utiliza bifurcaciones ni búsquedas en tablas para evitar canales laterales y, por lo tanto, es adecuado para su uso en criptografía.

Véase también

Logaritmo de Zech

Referencias

↑ Hankerson, Vanstone y Menezes 2004 , pág. 28
↑ Las raíces de dicho polinomio deben estar en un campo de extensión de GF( $q$ ) ya que el polinomio es irreducible y, por lo tanto, no tiene raíces en GF( $q$ ).
↑ Mullen y Panario 2013 , pág. 17
↑ Diseño y análisis de experimentos . John Wiley & Sons, Ltd. 8 de agosto de 2005. págs. 716–720 . doi : 10.1002/0471709948.app1 .
↑ Lidl y Niederreiter 1983 , pág. 553
↑ Fan, Haining. "Un algoritmo de inversión $GF(2$ $n$ $)$ basado en trazas " (PDF) . Archivado del original el 21 de abril de 2025. Recuperado el 10 de enero de 2025 .{{cite web}}: CS1 maint: bot: estado de la URL original desconocido ( enlace )
↑ Grošek, O.; Fabšič, T. (2018), "Cálculo de inversos multiplicativos en campos finitos mediante división larga" (PDF) , Journal of Electrical Engineering , 69 (5): 400– 402, Bibcode : 2018JEE....69..400G , doi : 10.2478/jee-2018-0059 , S2CID 115440420
↑ "Cálculo rápido de CRC para polinomios genéricos mediante la instrucción PCLMULQDQ" (PDF) . www.intel.com . 2009. Consultado el 8 de agosto de 2020 .
↑ "Implementaciones de software eficientes de campos finitos grandes GF(2n) para aplicaciones de almacenamiento seguro" (PDF) . www.ccs.neu.edu . Consultado el 8 de agosto de 2020 .
↑ "bpdegnan/aes" . GitHub .

Fuentes

Lidl, Rudolf; Niederreiter, Harald (1983), Campos finitos , Addison-Wesley, ISBN 0-201-13519-1(reeditado en 1984 por Cambridge University Press ISBN 0-521-30240-4).
Mullen, Gary L.; Panario, Daniel (2013), Handbook of Finite Fields , CRC Press, ISBN 978-1-4398-7378-6
Hankerson, Darrel; Vanstone, Scott; Menezes, Alfred (2004), Guía de criptografía de curvas elípticas , Springer, ISBN 978-0-387-21846-5

Enlaces externos

Gordon, G. (1976). "Método muy simple para encontrar el polinomio mínimo de un elemento no nulo arbitrario de un campo finito". Electronics Letters . 12 (25): 663– 664. Bibcode : 1976ElL....12..663G . doi : 10.1049/el:19760508 .
da Rocha, VC; Markarian, G. (2006). "Método simple para encontrar la traza de un elemento arbitrario de un campo finito". Electronics Letters . 42 (7): 423– 325. Bibcode : 2006ElL....42..423D . doi : 10.1049/el:20060473 .
Trenholme, Sam. "Campo Galois de AE" .
Planck, James S. (2007). "Biblioteca rápida de aritmética de campos de Galois en C/C++" .
Wikiversidad: Reed–Solomon para programadores – Aritmética de cuerpos finitos

[1] Hankerson, Vanstone y Menezes 2004 , pág. 28

[2] Las raíces de dicho polinomio deben estar en un campo de extensión de GF( $q$ ) ya que el polinomio es irreducible y, por lo tanto, no tiene raíces en GF( $q$ ).

[3] Mullen y Panario 2013 , pág. 17

[4] Diseño y análisis de experimentos . John Wiley & Sons, Ltd. 8 de agosto de 2005. págs. 716–720 . doi : 10.1002/0471709948.app1 .

[LN-5] Lidl y Niederreiter 1983 , pág. 553

[6] Fan, Haining. "Un algoritmo de inversión $GF(2$ $n$ $)$ basado en trazas " (PDF) . Archivado del original el 21 de abril de 2025. Recuperado el 10 de enero de 2025 .{{cite web}}: CS1 maint: bot: estado de la URL original desconocido ( enlace )

[7] Grošek, O.; Fabšič, T. (2018), "Cálculo de inversos multiplicativos en campos finitos mediante división larga" (PDF) , Journal of Electrical Engineering , 69 (5): 400– 402, Bibcode : 2018JEE....69..400G , doi : 10.2478/jee-2018-0059 , S2CID 115440420

[8] "Cálculo rápido de CRC para polinomios genéricos mediante la instrucción PCLMULQDQ" (PDF) . www.intel.com . 2009. Consultado el 8 de agosto de 2020 .

[9] "Implementaciones de software eficientes de campos finitos grandes GF(2n) para aplicaciones de almacenamiento seguro" (PDF) . www.ccs.neu.edu . Consultado el 8 de agosto de 2020 .

[10] "bpdegnan/aes" . GitHub .

[ 1 ]

[

[

[

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]