GF(2)

$GF(2)$ (también denotado como , $Z$ $/2$ $Z$ o ) es el campo finito con dos elementos. ^[1]^[a] $\mathbb {F}_{2}$ $\mathbb {Z} /2\mathbb {Z}$

$GF(2)$ es el campo con el menor número posible de elementos, y es único si se denotan respectivamente la identidad aditiva y la identidad multiplicativa .0 y1 , como de costumbre.

Los elementos de $GF(2)$ pueden identificarse con los dos valores posibles de un bit y con los valores booleanos true y false . De ello se deduce que $GF(2)$ es fundamental y omnipresente en la ciencia informática y sus fundamentos lógicos .

Definición

GF(2) es el único campo con dos elementos con sus identidades aditivas y multiplicativas respectivamente denotadas0 y1 .

Su adición se define como la adición habitual de números enteros pero módulo 2 y corresponde a la siguiente tabla:

Si los elementos de GF(2) se consideran valores booleanos, entonces la suma es la misma que la operación lógica XOR . Como cada elemento es igual a su opuesto , la resta es la misma operación que la suma.

La multiplicación de GF(2) es nuevamente la multiplicación habitual módulo 2 (ver la tabla a continuación), y en variables booleanas corresponde a la operación lógica AND .

GF(2) se puede identificar con el campo de los enteros módulo2 , es decir, el anillo cociente del anillo de los números enteros Z por el ideal 2 Z de todos los números pares : GF(2) = Z /2 Z.

Se pueden encontrar las notaciones $Z 2$ y aunque pueden confundirse con la notación de $\mathbb {Z} _ {2}$ 2 -enteros ádicos .

Propiedades

Debido a que GF(2) es un campo, se conservan muchas de las propiedades familiares de los sistemas numéricos, como los números racionales y los números reales :

la suma tiene un elemento identidad (0) y un inverso para cada elemento;
la multiplicación tiene un elemento identidad (1) y un inverso para cada elemento excepto 0;
La suma y la multiplicación son conmutativas y asociativas ;
La multiplicación es distributiva sobre la suma.

Las propiedades que no son familiares a partir de los números reales incluyen:

cada elemento x de GF(2) satisface $x + x = 0$ y por lo tanto $- x = x$ ; esto significa que la característica de GF(2) es 2;
cada elemento x de GF(2) satisface $x 2 = x$ (es decir, es idempotente con respecto a la multiplicación); este es un ejemplo del pequeño teorema de Fermat . GF(2) es el único cuerpo con esta propiedad (Prueba: si $x 2 = x$ , entonces $x = 0$ o $x \neq 0$ . En el último caso, x debe tener un inverso multiplicativo, en cuyo caso dividir ambos lados por x da $x = 1$ . Todos los cuerpos más grandes contienen elementos distintos de 0 y 1, y esos elementos no pueden satisfacer esta propiedad).

Aplicaciones

Debido a las propiedades algebraicas anteriores, muchas herramientas matemáticas conocidas y poderosas funcionan en GF(2) tan bien como en otros campos. Por ejemplo, las operaciones matriciales, incluida la inversión de matrices , se pueden aplicar a matrices con elementos en GF(2) ( ver anillo de matrices ).

Cualquier grupo ( V,+ ) con la propiedad v + v = 0 para cada v en V es necesariamente abeliano y puede convertirse en un espacio vectorial sobre GF(2) de manera natural, definiendo 0 v = 0 y 1 v = v para todo v en V . Este espacio vectorial tendrá una base , lo que implica que el número de elementos de V debe ser una potencia de 2 (o infinito).

En las computadoras modernas , los datos se representan con cadenas de bits de una longitud fija, llamadas palabras de máquina . Estas están dotadas de la estructura de un espacio vectorial sobre GF(2). La adición de este espacio vectorial es la operación bit a bit llamada XOR (o exclusivo). El AND bit a bit es otra operación sobre este espacio vectorial, lo que lo convierte en un álgebra de Boole , una estructura que subyace a toda la ciencia de la computación . Estos espacios también se pueden aumentar con una operación de multiplicación que los convierte en un cuerpo GF(2 ⁿ ), pero la operación de multiplicación no puede ser una operación bit a bit. Cuando n es en sí mismo una potencia de dos, la operación de multiplicación puede ser nim-multiplicación ; alternativamente, para cualquier n , se puede usar la multiplicación de polinomios sobre GF(2) módulo un polinomio irreducible (como por ejemplo para el cuerpo GF(2 ⁸ ) en la descripción del cifrado Advanced Encryption Standard ).

Los espacios vectoriales y los anillos polinómicos sobre GF(2) se utilizan ampliamente en la teoría de codificación y, en particular, en los códigos de corrección de errores y la criptografía moderna . Por ejemplo, muchos códigos de corrección de errores comunes (como los códigos BCH ) son códigos lineales sobre GF(2) (códigos definidos a partir de espacios vectoriales sobre GF(2)) o códigos polinómicos (códigos definidos como cocientes de anillos polinómicos sobre GF(2)).

Cierre algebraico

Como cualquier cuerpo, GF(2) tiene un cierre algebraico . Se trata de un cuerpo F que contiene a GF(2) como subcuerpo , que es algebraico sobre GF(2) (es decir, cada elemento de F es una raíz de un polinomio con coeficientes en GF(2)), y que es algebraicamente cerrado (cualquier polinomio no constante con coeficientes en F tiene una raíz en F ). El cuerpo F está determinado de forma única por estas propiedades, hasta un automorfismo de cuerpo (es decir, esencialmente hasta la notación de sus elementos).

F es contable y contiene una única copia de cada uno de los cuerpos finitos GF(2 ⁿ ); la copia de GF(2 ⁿ ) está contenida en la copia de GF(2 ^m ) si y solo si n divide a m. El cuerpo F es contable y es la unión de todos estos cuerpos finitos.

Conway se dio cuenta de que F puede identificarse con el número ordinal , donde las operaciones de adición y multiplicación se definen de manera natural por inducción transfinita (estas operaciones son, sin embargo, diferentes de la adición y multiplicación estándar de números ordinales). ^[2] La adición en este campo es simple de realizar y es similar a la adición Nim ; Lenstra ha demostrado que la multiplicación también se puede realizar de manera eficiente. ^[3] $\omega ^{\omega ^{\omega }}$

Véase también

Campo con un elemento

Referencias

^ GF es la sigla de campo de Galois , otro nombre para los campos finitos.

^ Lidl, Rudolf; Niederreiter, Harald (1997). Campos finitos . Enciclopedia de matemáticas y sus aplicaciones. Vol. 20 (2.ª ed.). Cambridge University Press . ISBN 0-521-39231-4.Zbl 0866.11069 .
^ Conway, John H. (2000). Sobre números y juegos (2.ª ed.). Wellesley, Mass., pág. 61. ISBN 978-1-56881-127-7.{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
^ Lenstra, Hendrik (1977). "Sobre la clausura algebraica de dos" (PDF) . Indagationes Mathematicae (Actas) . 80 (5).