Campo finito - Finite field

En matemáticas , un campo finito o campo de Galois (llamado así en honor a Évariste Galois ) es un campo que contiene un número finito de elementos . Como ocurre con cualquier campo, un campo finito es un conjunto en el que las operaciones de multiplicación, suma, resta y división se definen y satisfacen ciertas reglas básicas. Los ejemplos más comunes de campos finitos los dan los enteros mod p cuando p es un número primo .

Los campos finitos son fundamentales en varias áreas de las matemáticas y la informática , incluida la teoría de números , la geometría algebraica , la teoría de Galois , la geometría finita , la criptografía y la teoría de la codificación .

Propiedades

Un campo finito es un conjunto finito que es un campo ; esto significa que la multiplicación, la suma, la resta y la división (excluyendo la división por cero) están definidas y satisfacen las reglas de la aritmética conocidas como axiomas de campo .

El número de elementos de un campo finito se denomina orden o, a veces, tamaño . Un campo finito de orden q existe si y solo si q es una potencia prima p ^k (donde p es un número primo y k es un número entero positivo). En un campo de orden p ^k , la adición de p copias de cualquier elemento siempre da como resultado cero; es decir, la característica del campo es p .

Si q = p ^k , todos los campos de orden q son isomorfos (ver § Existencia y unicidad a continuación). Además, un campo no puede contener dos subcampos finitos diferentes con el mismo orden. Por lo tanto, se pueden identificar todos los campos finitos con el mismo orden, y se denotan sin ambigüedades , F _q o GF ( q ) , donde las letras GF significan "campo de Galois". ${\ Displaystyle \ mathbb {F} _ {q}}$

En un campo finito de orden q , el polinomio X ^q - X tiene todos los elementos q del campo finito como raíces . Los elementos distintos de cero de un campo finito forman un grupo multiplicativo . Este grupo es cíclico , por lo que todos los elementos distintos de cero se pueden expresar como potencias de un solo elemento llamado elemento primitivo del campo. (En general, habrá varios elementos primitivos para un campo determinado).

Los ejemplos más simples de campos finitos son los campos de orden primo: para cada número primo p , el campo prime de orden p , , puede construirse como los enteros módulo p , Z / p Z . ${\ Displaystyle \ mathbb {F} _ {p}}$

Los elementos del campo primo de orden p pueden representarse mediante números enteros en el rango 0, ..., p - 1 . La suma, la diferencia y el producto son el resto de la división por p del resultado de la operación entera correspondiente. El inverso multiplicativo de un elemento se puede calcular usando el algoritmo euclidiano extendido (ver algoritmo euclidiano extendido § Enteros modulares ).

Sea F un campo finito. Para cualquier elemento x en F y cualquier número entero n , denote por n ⋅ x la suma de n copias de x . El n menos positivo tal que n ⋅ 1 = 0 es la característica p del campo. Esto permite definir una multiplicación de un elemento k de GF ( p ) por un elemento x de F eligiendo un número entero representativo de k . Esta multiplicación hace F en un GF ( p ) - espacio vectorial . De ello se deduce que el número de elementos de F es p ⁿ para algún número entero n . ${\ Displaystyle (k, x) \ mapsto k \ cdot x}$

La identidad

${\ Displaystyle (x + y) ^ {p} = x ^ {p} + y ^ {p}}$

(a veces llamado el sueño del estudiante de primer año ) es cierto en un campo de característica p . Esto se sigue del teorema del binomio , ya que cada coeficiente binomial de la expansión de ( x + y ) ^p , excepto el primero y el último, es un múltiplo de p .

Según el pequeño teorema de Fermat , si p es un número primo y x está en el campo GF ( p ), entonces x ^p = x . Esto implica la igualdad

${\ Displaystyle X ^ {p} -X = \ prod _ {a \ in {\ rm {GF}} (p)} (Xa)}$

para polinomios sobre GF ( p ) . De manera más general, cada elemento en GF ( p ⁿ ) satisface la ecuación polinomial x ^{p n} - x = 0 .

Cualquier extensión de campo finito de un campo finito es separable y simple. Es decir, si E es un campo finito y F es un subcampo de E , entonces E se obtiene de F al unir un solo elemento cuyo polinomio mínimo es separable. Para usar una jerga, los campos finitos son perfectos .

Una estructura algebraica más general que satisface todos los demás axiomas de un campo, pero cuya multiplicación no requiere ser conmutativa, se llama anillo de división (o, a veces, campo sesgado ). Según el pequeño teorema de Wedderburn , cualquier anillo de división finita es conmutativo y, por tanto, es un campo finito.

Existencia y singularidad

Sea q = p ⁿ una potencia prima y F el campo de división del polinomio

${\ Displaystyle P = X ^ {q} -X}$

sobre el campo principal GF ( p ) . Esto significa que F es un campo finito de orden más bajo, en el que P tiene q raíces distintas (la derivada formal de P es P ′ = −1 , lo que implica que mcd ( P , P ′ ) = 1 , lo que en general implica que el el campo de división es una extensión separable del original). Los anteriores de identidad muestra que la suma y el producto de dos raíces de P son raíces de P , así como el inverso multiplicativo de una raíz de P . En otras palabras, las raíces de P forman un campo de orden q , que es igual a F por la minimidad del campo de división.

La unicidad hasta el isomorfismo de los campos divididos implica, por tanto, que todos los campos de orden q son isomorfos. Además, si un campo F tiene un campo de orden q = p ^k como subcampo, sus elementos son las raíces q de X ^q - X , y F no puede contener otro subcampo de orden q .

En resumen, tenemos el siguiente teorema de clasificación probado por primera vez en 1893 por EH Moore :

El orden de un campo finito es un poder primordial. Para cada potencia prima q hay campos de orden q , y todos son isomorfos. En estos campos, cada elemento satisface

${\ Displaystyle x ^ {q} = x,}$

y el polinomio X ^q - X factores como

${\ Displaystyle X ^ {q} -X = \ prod _ {a \ in F} (Xa).}$

De ello se deduce que GF ( p ⁿ ) contiene un subcampo isomorfo a GF ( p ^m ) si y solo si m es un divisor de n ; en ese caso, este subcampo es único. De hecho, el polinomio X ^{p m} - X divide X ^{p n} - X si y solo si m es un divisor de n .

Construcción explícita

Campos no principales

Dada una potencia prima q = p ⁿ con p prima yn > 1 , el campo GF ( q ) puede construirse explícitamente de la siguiente manera. Primero se elige un polinomio irreducible P en GF ( p ) [ X ] de grado n (tal polinomio irreducible siempre existe). Entonces el anillo del cociente

${\ Displaystyle {\ rm {GF}} (q) = {\ rm {GF}} (p) [X] / (P)}$

del anillo polinomial GF ( p ) [ X ] por el ideal generado por P es un campo de orden q .

Más explícitamente, los elementos de GF ( q ) son los polinomios sobre GF ( p ) cuyo grado es estrictamente menor que n . La suma y la resta son las de polinomios sobre GF ( p ) . El producto de dos elementos es el resto de la división euclidiana por P del producto en GF ( p ) [ X ] . El inverso multiplicativo de un elemento distinto de cero puede calcularse con el algoritmo euclidiano extendido; ver algoritmo euclidiano extendido § Extensiones de campo algebraico simple .

Excepto en la construcción de GF (4) , hay varias opciones posibles para P , que producen resultados isomórficos. Para simplificar la división euclidiana, para P uno suele elegir polinomios de la forma

${\ Displaystyle X ^ {n} + aX + b,}$

lo que hace que las divisiones euclidianas necesarias sean muy eficientes. Sin embargo, para algunos campos, típicamente en la característica 2 , los polinomios irreducibles de la forma X ⁿ + aX + b pueden no existir. En la característica 2 , si el polinomio X ⁿ + X + 1 es reducible, se recomienda elegir X ⁿ + X ^k + 1 con la menor k posible que haga que el polinomio sea irreducible. Si todos estos trinomios son reducibles, se elige "pentanomios" X ⁿ + X ^a + X ^b + X ^c + 1 , ya que los polinomios de grado mayor que 1 , con un número par de términos, nunca son irreducibles en la característica 2 , teniendo 1 como raíz.

Los polinomios de Conway ofrecen una posible elección para dicho polinomio . Aseguran una cierta compatibilidad entre la representación de un campo y las representaciones de sus subcampos.

En las siguientes secciones, mostraremos cómo funciona el método de construcción general descrito anteriormente para campos finitos pequeños.

Campo con cuatro elementos

El campo no primo más pequeño es el campo con cuatro elementos, que comúnmente se denota GF (4) o Consiste en los cuatro elementos de manera que y para cada otra operación los resultados se deducen fácilmente de la ley distributiva . Consulte a continuación las tablas de funcionamiento completas. ${\ Displaystyle \ mathbb {F} _ {4}.}$${\ Displaystyle 0,1, \ alpha, 1 + \ alpha}$${\ Displaystyle \ alpha ^ {2} = 1 + \ alpha,}$ ${\ Displaystyle 1 \ cdot \ alpha = \ alpha \ cdot 1 = \ alpha,}$ ${\ Displaystyle x + x = 0,}$${\ Displaystyle x \ cdot 0 = 0 \ cdot x = 0,}$${\ Displaystyle x \ in \ operatorname {GF} (4),}$

Esto se puede deducir de la siguiente manera de los resultados de la sección anterior.

Sobre GF (2) , solo hay un polinomio irreducible de grado2 :

${\ Displaystyle X ^ {2} + X + 1}$

Por lo tanto, para GF (4) la construcción de la sección anterior debe involucrar este polinomio, y

${\ Displaystyle {\ rm {GF}} (4) = {\ rm {GF}} (2) [X] / (X ^ {2} + X + 1).}$

Sea α una raíz de este polinomio en GF (4) . Esto implica que

α ² = 1 + α ,

y que α y 1 + α son los elementos de GF (4) que no están en GF (2) . Las tablas de las operaciones en GF (4) resultan de esto y son las siguientes:

Suma x + y	Multiplicación x ⋅ y	División x / y
x ╲ y 0 1 α 1 + α 0 0 1 α 1 + α 1 1 0 1 + α α α α 1 + α 0 1 1 + α 1 + α α 1 0	x ╲ y 0 1 α 1 + α 0 0 0 0 0 1 0 1 α 1 + α α 0 α 1 + α 1 1 + α 0 1 + α 1 α	x ╲ y 1 α 1 + α 0 0 0 0 1 1 1 + α α α α 1 1 + α 1 + α 1 + α α 1

No se proporciona una tabla para la resta, porque la resta es idéntica a la suma, como es el caso para todos los campos de la característica 2. En la tercera tabla, para la división de x por y , los valores de x deben leerse en la columna de la izquierda. y los valores de y en la fila superior. (Como 0 ⋅ z = 0 para cada z en cada anillo, la división entre 0 debe permanecer indefinida).

El mapa

${\ Displaystyle \ varphi: x \ mapsto x ^ {2}}$

es el automorfismo de campo no trivial, llamado automorfismo de Frobenius , que envía α a la segunda raíz 1 + α del polinomio irreducible mencionado anteriormente${\ Displaystyle X ^ {2} + X + 1.}$

GF ( p ² ) para un primo impar p

Para aplicar la construcción general anterior de campos finitos en el caso de GF ( p ² ) , uno tiene que encontrar un polinomio irreducible de grado 2. Para p = 2 , esto se ha hecho en la sección anterior. Si p es un primo impar, siempre hay polinomios irreducibles de la forma X ² - r , con r en GF ( p ) .

Más precisamente, el polinomio X ² - r es irreducible sobre GF ( p ) si y solo si r es un módulo p cuadrático sin residuo (esta es casi la definición de un no residuo cuadrático). Existen p - 1/2no residuos cuadráticos módulo p . Por ejemplo, 2 es un no-residuo cuadrático para p = 3, 5, 11, 13, ... , y 3 es un no-residuo cuadrático para p = 5, 7, 17, ... . Si p ≡ 3 mod 4 , es decir p = 3, 7, 11, 19, ... , se puede elegir −1 ≡ p - 1 como un no residuo cuadrático, lo que nos permite tener un polinomio X irreducible muy simple ² + 1 .

Habiendo elegido un no residuo cuadrático r , sea α una raíz cuadrada simbólica de r , que es un símbolo que tiene la propiedad α ² = r , de la misma manera que el número complejo i es una raíz cuadrada simbólica de -1 . Entonces, los elementos de GF ( p ² ) son todas las expresiones lineales

${\ Displaystyle a + b \ alpha,}$

con un y b en GF ( p ) . Las operaciones en GF ( p ² ) se definen de la siguiente manera (las operaciones entre elementos de GF ( p ) representados por letras latinas son las operaciones en GF ( p ) ):

${\ Displaystyle {\ begin {alineado} - (a + b \ alpha) & = - a + (- b) \ alpha \\ (a + b \ alpha) + (c + d \ alpha) & = (a + c ) + (b + d) \ alpha \\ (a + b \ alpha) (c + d \ alpha) & = (ac + rbd) + (ad + bc) \ alpha \\ (a + b \ alpha) ^ {-1} & = a (a ^ {2} -rb ^ {2}) ^ {- 1} + (- b) (a ^ {2} -rb ^ {2}) ^ {- 1} \ alpha \ end {alineado}}}$

GF (8) y GF (27)

El polinomio

${\ Displaystyle X ^ {3} -X-1}$

es irreductible sobre GF (2) y GF (3) , es decir, es irreducible módulo 2 y 3 (para demostrarlo basta con mostrar que no tiene raíz en GF (2) ni en GF (3) ). De ello se deduce que los elementos de GF (8) y GF (27) pueden representarse mediante expresiones

${\ Displaystyle a + b \ alpha + c \ alpha ^ {2},}$

donde a , b , c son elementos de GF (2) o GF (3) (respectivamente), y es un símbolo tal que ${\ Displaystyle \ alpha}$

${\ Displaystyle \ alpha ^ {3} = \ alpha +1.}$

La suma, el inverso aditivo y la multiplicación en GF (8) y GF (27) pueden definirse así como sigue; en las siguientes fórmulas, las operaciones entre elementos de GF (2) o GF (3) , representadas por letras latinas, son las operaciones en GF (2) o GF (3) , respectivamente:

${\ Displaystyle {\ begin {alineado} - (a + b \ alpha + c \ alpha ^ {2}) & = - a + (- b) \ alpha + (- c) \ alpha ^ {2} \ qquad {\ text {(para}} \ mathrm {GF} (8), {\ text {esta operación es la identidad)}} \\ (a + b \ alpha + c \ alpha ^ {2}) + (d + e \ alpha + f \ alpha ^ {2}) & = (a + d) + (b + e) ​​\ alpha + (c + f) \ alpha ^ {2} \\ (a + b \ alpha + c \ alpha ^ {2}) (d + e \ alpha + f \ alpha ^ {2}) & = (ad + bf + ce) + (ae + bd + bf + ce + cf) \ alpha + (af + be + cd + cf) \ alpha ^ {2} \ end {alineado}}}$

Novia (16)

El polinomio

${\ Displaystyle X ^ {4} + X + 1}$

es irreducible sobre GF (2) , es decir, es irreducible módulo 2 . De ello se deduce que los elementos de GF (16) pueden representarse mediante expresiones

${\ Displaystyle a + b \ alpha + c \ alpha ^ {2} + d \ alpha ^ {3},}$

donde a , b , c , d son 0 o 1 (elementos de GF (2) ), y α es un símbolo tal que

${\ Displaystyle \ alpha ^ {4} = \ alpha +1}$

(es decir, α se define como una raíz del polinomio irreducible dado). Como la característica de GF (2) es 2 , cada elemento es su inverso aditivo en GF (16) . La suma y la multiplicación en GF (16) se pueden definir como sigue; en las siguientes fórmulas, las operaciones entre elementos de GF (2) , representadas por letras latinas, son las operaciones en GF (2) .

${\ Displaystyle {\ begin {alineado} (a + b \ alpha + c \ alpha ^ {2} + d \ alpha ^ {3}) + (e + f \ alpha + g \ alpha ^ {2} + h \ alpha ^ {3}) & = (a + e) ​​+ (b + f) \ alpha + (c + g) \ alpha ^ {2} + (d + h) \ alpha ^ {3} \\ (a + b \ alpha + c \ alpha ^ {2} + d \ alpha ^ {3}) (e + f \ alpha + g \ alpha ^ {2} + h \ alpha ^ {3}) & = (ae + bh + cg + df) + (af + be + bh + cg + df + ch + dg) \ alpha \; + \\ & \ quad \; (ag + bf + ce + ch + dg + dh) \ alpha ^ {2 } + (ah + bg + cf + de + dh) \ alpha ^ {3} \ end {alineado}}}$

Estructura multiplicativa

El conjunto de elementos distintos de cero en GF ( q ) es un grupo abeliano bajo la multiplicación, de orden q - 1 . Según el teorema de Lagrange , existe un divisor k de q - 1 tal que x ^k = 1 para cada x distinto de cero en GF ( q ) . Como la ecuación x ^k = 1 tiene como máximo k soluciones en cualquier campo, q - 1 es el valor más bajo posible para k . El teorema de la estructura de los grupos abelianos finitos implica que este grupo multiplicativo es cíclico , es decir, todos los elementos distintos de cero son potencias de un solo elemento. En resumen:

El grupo multiplicativo de los elementos distintos de cero en GF ( q ) es cíclico, y existe un elemento a , tal que los q - 1 elementos distintos de cero de GF ( q ) son a , a ² , ..., a ^{q −2} , a ^{q −1} = 1 .

Dicho elemento a se denomina elemento primitivo . A menos que q = 2, 3 , el elemento primitivo no es único. El número de elementos primitivos es φ ( q - 1) donde φ es la función totiente de Euler .

El resultado anterior implica que x ^q = x para cada x en GF ( q ) . El caso particular donde q es primo es el pequeño teorema de Fermat .

Logaritmo discreto

Si a es un elemento primitivo en GF ( q ) , entonces para cualquier elemento x distinto de cero en F , hay un único entero n con 0 ≤ n ≤ q - 2 tal que

x = una ⁿ .

Este número entero n se llama logaritmo discreto de x en base a .

Si bien una ⁿ se puede calcular muy rápidamente, por ejemplo, usando exponenciación al elevar al cuadrado , no se conoce un algoritmo eficiente para calcular la operación inversa, el logaritmo discreto. Esto se ha utilizado en varios protocolos criptográficos ; consulte Logaritmo discreto para obtener más detalles.

Cuando los elementos distintos de cero de GF ( q ) están representados por sus logaritmos discretos, la multiplicación y la división son fáciles, ya que se reducen a suma y resta módulo q - 1 . Sin embargo, la suma equivale a calcular el logaritmo discreto de a ^m + a ⁿ . La identidad

una ^m + una ^norte = una ^norte ( una ^{m - norte} + 1)

permite resolver este problema construyendo la tabla de los logaritmos discretos de a ⁿ + 1 , llamados logaritmos de Zech , para n = 0, ..., q - 2 (es conveniente definir el logaritmo discreto de cero como - ∞ ).

Los logaritmos de Zech son útiles para cálculos grandes, como el álgebra lineal sobre campos de tamaño mediano, es decir, campos que son lo suficientemente grandes para hacer que los algoritmos naturales sean ineficientes, pero no demasiado grandes, ya que uno tiene que precalcular una tabla del mismo tamaño. como el orden del campo.

Raíces de unidad

Todo elemento distinto de cero de un campo finito es una raíz de unidad , ya que x ^{q −1} = 1 para cada elemento distinto de cero de GF ( q ) .

Si n es un entero positivo, un n º raíz primitiva de la unidad es una solución de la ecuación x ⁿ = 1 que no es una solución de la ecuación x ^m = 1 para cualquier número entero positivo m < n . Si una es un n º raíz primitiva de la unidad en un campo F , entonces F contiene todos los n raíces de la unidad, que son 1, un , un ² , ..., un ^{n -1} .

El campo GF ( q ) contiene un n º raíz primitiva de la unidad si y sólo si n es un divisor de q - 1 ; si n es un divisor de q - 1 , entonces el número de raíces primitivas n -ésimas de la unidad en GF ( q ) es φ ( n ) ( función totient de Euler ). El número de raíces n -ésimas de la unidad en GF ( q ) es mcd ( n , q - 1) .

En un campo de característica p , cada ( np ) º raíz de la unidad es también un n º raíz de la unidad. De ello se sigue que las raíces primitivas ( np ) de unidad nunca existen en un campo de característica p .

Por otro lado, si n es primos entre sí a p , las raíces de la n º ciclotómico polinómicas son distintos en cada cuerpo de característica p , como este polinomio es un divisor de X ⁿ - 1 , cuyo discriminante es distinto de cero en módulo p . Se deduce que el n - ésimo polinomio ciclotómico se factoriza sobre GF ( p ) en distintos polinomios irreducibles que tienen todos el mismo grado, digamos d , y que GF ( p ^d ) es el campo más pequeño de la característica p que contiene las n- ésimas raíces primitivas de unidad. ${\ Displaystyle n ^ {n}}$

Ejemplo: GF (64)

El campo GF (64) tiene varias propiedades interesantes que los campos más pequeños no comparten: tiene dos subcampos de modo que ninguno está contenido en el otro; no todos los generadores (elementos con polinomio mínimo de grado 6 sobre GF (2) ) son elementos primitivos; y los elementos primitivos no están todos conjugados bajo el grupo de Galois .

El orden de este campo es 2 ⁶ , y los divisores de 6 son 1, 2, 3, 6 , los subcampos de GF (64) son GF (2) , GF (2 ² ) = GF (4) , GF (2 ³ ) = GF (8) y el propio GF (64) . Como 2 y 3 son coprimos , la intersección de GF (4) y GF (8) en GF (64) es el campo primario GF (2) .

La unión de GF (4) y GF (8) tiene por tanto 10 elementos. Los 54 elementos restantes de GF (64) generan GF (64) en el sentido de que ningún otro subcampo contiene ninguno de ellos. De ello se deduce que son raíces de polinomios irreducibles de grado 6 sobre GF (2) . Esto implica que, sobre GF (2) , hay exactamente 9 =54/6polinomios mónicos irreducibles de grado 6 . Esto puede verificarse factorizando X ⁶⁴ - X sobre GF (2) .

Los elementos de GF (64) son raíces primitivas n -ésimas de la unidad para algunos n que dividen 63 . Como la tercera y la séptima raíces de la unidad pertenecen a GF (4) y GF (8) , respectivamente, los 54 generadores son raíces primitivas n -ésimas de la unidad para algunos n en {9, 21, 63} . La función totient de Euler muestra que hay 6 raíces primitivas novena de unidad, 12 raíces primitivas vigésimo primera de unidad y 36 raíces primitivas 63 o de unidad. Sumando estos números, se encuentran nuevamente 54 elementos.

Al factorizar los polinomios ciclotómicos sobre GF (2) , se encuentra que:

• Las seis raíces primitivas novena de la unidad son raíces de

${\ Displaystyle X ^ {6} + X ^ {3} +1,}$

y todos se conjugan bajo la acción del grupo de Galois.

• Las doce raíces primitivas de la unidad 21 son raíces de

${\ Displaystyle (X ^ {6} + X ^ {4} + X ^ {2} + X + 1) (X ^ {6} + X ^ {5} + X ^ {4} + X ^ {2} +1).}$

Forman dos órbitas bajo la acción del grupo Galois. Como los dos factores son recíprocos entre sí, una raíz y su inverso (multiplicativo) no pertenecen a la misma órbita.

• Los 36 elementos primitivos de GF (64) son las raíces de

${\ Displaystyle (X ^ {6} + X ^ {4} + X ^ {3} + X + 1) (X ^ {6} + X + 1) (X ^ {6} + X ^ {5} + 1) (X ^ {6} + X ^ {5} + X ^ {3} + X ^ {2} +1) (X ^ {6} + X ^ {5} + X ^ {2} + X + 1) (X ^ {6} + X ^ {5} + X ^ {4} + X + 1),}$

Se dividieron en 6 órbitas de 6 elementos bajo la acción del grupo Galois.

Esto muestra que la mejor opción para construir GF (64) es definirlo como GF (2) [ X ] / ( X ⁶ + X + 1) . De hecho, este generador es un elemento primitivo, y este polinomio es el polinomio irreducible que produce la división euclidiana más fácil.

Automorfismo de Frobenius y teoría de Galois

En esta sección, p es un número primo y q = p ⁿ es una potencia de p .

En GF ( q ) , la identidad ( x + y ) ^p = x ^p + y ^p implica que el mapa

${\ Displaystyle \ varphi: x \ mapsto x ^ {p}}$

es un GF ( p ) - endomorfismo lineal y un automorfismo de campo de GF ( q ) , que fija todos los elementos del subcampo GF ( p ) . Se llama automorfismo de Frobenius , en honor a Ferdinand Georg Frobenius .

Denotando por φ ^k la composición de φ consigo mismo k veces, tenemos

${\ Displaystyle \ varphi ^ {k}: x \ mapsto x ^ {p ^ {k}}.}$

En la sección anterior se ha demostrado que φ ⁿ es la identidad. Para 0 < k < n , el automorfismo φ ^k no es la identidad, ya que, en caso contrario, el polinomio

${\ Displaystyle X ^ {p ^ {k}} - X}$

tendría más de p ^k raíces.

No hay otros GF ( p ) -automorfismos de GF ( q ) . En otras palabras, GF ( p ⁿ ) tiene exactamente n GF ( p ) -automorfismos, que son

${\ Displaystyle \ mathrm {Id} = \ varphi ^ {0}, \ varphi, \ varphi ^ {2}, \ ldots, \ varphi ^ {n-1}.}$

En términos de la teoría de Galois , esto significa que GF ( p ⁿ ) es una extensión de Galois de GF ( p ) , que tiene un grupo de Galois cíclico .

El hecho de que el mapa de Frobenius sea sobreyectivo implica que todo campo finito es perfecto .

Factorización de polinomios

Si F es un campo finito, un no constante polinomio mónico con coeficientes en F es irreducible sobre F , si no es el producto de dos polinomios monic no constantes, con coeficientes en F .

Como cada anillo polinomial sobre un campo es un dominio de factorización único , cada polinomio mónico sobre un campo finito puede factorizarse de una manera única (hasta el orden de los factores) en un producto de polinomios mónicos irreducibles.

Existen algoritmos eficientes para probar la irreductibilidad de polinomios y factorizar polinomios sobre un campo finito. Son un paso clave para factorizar polinomios sobre los números enteros o racionales . Al menos por esta razón, todo sistema de álgebra computacional tiene funciones para factorizar polinomios sobre campos finitos o, al menos, sobre campos primos finitos.

Polinomios irreducibles de un grado dado

El polinomio

${\ Displaystyle X ^ {q} -X}$

factores en factores lineales sobre un campo de orden q . Más precisamente, este polinomio es el producto de todos los polinomios mónicos de grado uno sobre un campo de orden q .

Esto implica que, si q = p ⁿ entonces X ^q - X es el producto de todos los polinomios mónicos irreducibles sobre GF ( p ) , cuyo grado divide n . De hecho, si P es un factor irreductible sobre GF ( p ) de X ^q - X , su grado divide n , ya que su campo de división está contenido en GF ( p ⁿ ) . Por el contrario, si P es un polinomio mónico irreducible sobre GF ( p ) de grado d que divide n , define una extensión de campo de grado d , que está contenida en GF ( p ⁿ ) , y todas las raíces de P pertenecen a GF ( p ⁿ ) , y son raíces de X ^q - X ; por lo tanto P divide X ^q - X . Como X ^q - X no tiene ningún factor múltiple, es el producto de todos los polinomios mónicos irreductibles que lo dividen.

Esta propiedad se usa para calcular el producto de los factores irreducibles de cada grado de polinomios sobre GF ( p ) ; ver factorización de grados distintos .

Número de polinomios mónicos irreducibles de un grado dado sobre un campo finito

El número N ( q , n ) de polinomios mónicos irreducibles de grado n sobre GF ( q ) viene dado por

${\ Displaystyle N (q, n) = {\ frac {1} {n}} \ sum _ {d \ mid n} \ mu (d) q ^ {n / d},}$

donde μ es la función de Möbius . Esta fórmula es casi una consecuencia directa de la propiedad anterior de X ^q - X .

Por la fórmula anterior, el número de polinomios irreducibles (no necesariamente monicos) de grado n sobre GF ( q ) es ( q - 1) N ( q , n ) .

Un límite inferior (ligeramente más simple) para N ( q , n ) es

${\ Displaystyle N (q, n) \ geq {\ frac {1} {n}} \ left (q ^ {n} - \ sum _ {p \ mid n, \ p {\ text {prime}}} q ^ {n / p} \ derecha).}$

Se puede deducir fácilmente que, para cada qy cada n , hay al menos un polinomio irreducible de grado n sobre GF ( q ) . Este límite inferior es agudo para q = n = 2 .

Aplicaciones

En criptografía , la dificultad del problema del logaritmo discreto en campos finitos o en curvas elípticas es la base de varios protocolos ampliamente utilizados, como el protocolo Diffie-Hellman . Por ejemplo, en 2014, una conexión segura de Internet a Wikipedia implicó el protocolo de curva elíptica Diffie-Hellman ( ECDHE ) sobre un gran campo finito. En la teoría de la codificación , muchos códigos se construyen como subespacios de espacios vectoriales sobre campos finitos.

Los campos finitos son utilizados por muchos códigos de corrección de errores , como el código de corrección de errores Reed-Solomon o el código BCH . El campo finito casi siempre tiene la característica de 2, ya que los datos de la computadora se almacenan en binario. Por ejemplo, un byte de datos se puede interpretar como un elemento de . Una excepción es el código de barras PDF417 , que es . Algunas CPU tienen instrucciones especiales que pueden ser útiles para campos finitos de la característica 2, generalmente variaciones de productos sin acarreo . ${\ displaystyle GF (2 ^ {8})}$${\ displaystyle GF (929)}$

Los campos finitos se utilizan ampliamente en la teoría de números , ya que muchos problemas relacionados con los números enteros pueden resolverse reduciéndolos módulo uno o varios números primos . Por ejemplo, los algoritmos más rápidos conocidos para la factorización de polinomios y el álgebra lineal sobre el campo de los números racionales proceden mediante la reducción del módulo uno o varios números primos, y luego la reconstrucción de la solución utilizando el teorema del resto chino , el levantamiento de Hensel o el algoritmo LLL .

De manera similar, muchos problemas teóricos en teoría de números pueden resolverse considerando sus reducciones en módulo algunos o todos los números primos. Véase, por ejemplo, el principio de Hasse . Muchos desarrollos recientes de la geometría algebraica fueron motivados por la necesidad de ampliar el poder de estos métodos modulares. La prueba de Wiles del último teorema de Fermat es un ejemplo de un resultado profundo que involucra muchas herramientas matemáticas, incluidos los campos finitos.

Las conjeturas de Weil se refieren al número de puntos en variedades algebraicas sobre campos finitos y la teoría tiene muchas aplicaciones, incluidas estimaciones exponenciales y de suma de caracteres .

Los campos finitos tienen una aplicación generalizada en combinatoria , dos ejemplos bien conocidos son la definición de Paley Graphs y la construcción relacionada de Hadamard Matrices . En la combinatoria aritmética, los campos finitos y los modelos de campo finito se utilizan ampliamente, como en el teorema de Szemerédi sobre progresiones aritméticas.

Extensiones

Cierre algebraico

Un campo finito F no es algebraicamente cerrado: el polinomio

${\ Displaystyle f (T) = 1 + \ prod _ {\ alpha \ in F} (T- \ alpha),}$

no tiene raíces en F , ya que f  ( α ) = 1 para todos α en F .

Corrija un cierre algebraico de . El mapa que envía cada x de x ^q se llama la q ésima potencia de Frobenius automorfismo . El subcampo de fijado por el n º iterate de es el conjunto de ceros del polinomio x ^{q n} - x , que tiene raíces distintas desde su en derivado es -1 , que nunca es cero. Por lo tanto, ese subcampo tiene q ⁿ elementos, por lo que es la única copia de in . Cada extensión finita de in es esto para algunos n , por lo que ${\ Displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ Displaystyle \ mathbb {F} _ {q}}$${\ Displaystyle \ varphi _ {q} \ colon {\ overline {\ mathbb {F}}} _ {q} \ to {\ overline {\ mathbb {F}}} _ {q}}$${\ Displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ Displaystyle \ varphi _ {q}}$${\ Displaystyle \ mathbb {F} _ {q} [x]}$${\ Displaystyle \ mathbb {F} _ {q ^ {n}}}$${\ Displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ Displaystyle \ mathbb {F} _ {q}}$${\ Displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ Displaystyle \ mathbb {F} _ {q ^ {n}}}$

${\ Displaystyle {\ overline {\ mathbb {F}}} _ {q} = \ bigcup _ {n \ geq 1} \ mathbb {F} _ {q ^ {n}}.}$

El grupo de Galois absoluto de es el grupo profinito${\ Displaystyle \ mathbb {F} _ {q}}$

${\ Displaystyle \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q} / \ mathbb {F} _ {q}) \ simeq \ varprojlim _ {n} \ operatorname {Gal} ({ \ overline {\ mathbb {F}}} _ {q ^ {n}} / \ mathbb {F} _ {q}) \ simeq \ varprojlim _ {n} (\ mathbf {Z} / n \ mathbf {Z} ) = {\ widehat {\ mathbf {Z}}}.}$

Como cualquier grupo infinito de Galois, puede estar equipado con la topología de Krull , y luego los isomorfismos que acabamos de dar son isomorfismos de grupos topológicos . La imagen de en el grupo es el generador 1 , por lo que corresponde a . De ello se deduce que tiene un orden infinito y genera un subgrupo denso de , no todo el grupo, porque el elemento tiene un orden infinito y genera el subgrupo denso. Uno dice que es un generador topológico de . ${\ Displaystyle \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q} / \ mathbb {F} _ {q})}$${\ Displaystyle \ varphi _ {q}}$${\ Displaystyle \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q ^ {n}} / \ mathbb {F} _ {q}) \ simeq \ mathbf {Z} / n \ mathbf {Z}}$${\ Displaystyle \ varphi _ {q}}$${\ Displaystyle 1 \ in {\ widehat {\ mathbf {Z}}}}$${\ Displaystyle \ varphi _ {q}}$${\ Displaystyle \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q} / \ mathbb {F} _ {q})}$${\ Displaystyle 1 \ in {\ widehat {\ mathbf {Z}}}}$${\ Displaystyle \ mathbf {Z} \ subsetneqq {\ widehat {\ mathbf {Z}}}.}$${\ Displaystyle \ varphi _ {q}}$${\ Displaystyle \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q} / \ mathbb {F} _ {q})}$

Cierre cuasi-algebraico

Aunque los campos finitos no son algebraicamente cerrados, son casi algebraicamente cerrados , lo que significa que cada polinomio homogéneo sobre un campo finito tiene un cero no trivial cuyos componentes están en el campo si el número de sus variables es mayor que su grado. Ésta fue una conjetura de Artin y Dickson probada por Chevalley (véase el teorema de Chevalley-Warning ).

El pequeño teorema de Wedderburn

Un anillo de división es una generalización de campo. No se supone que los anillos de división sean conmutativos. No hay anillos de división finitos no conmutativos: el pequeño teorema de Wedderburn establece que todos los anillos de división finitos son conmutativos, por lo tanto, campos finitos. El resultado se mantiene incluso si relajamos la asociatividad y consideramos anillos alternativos , según el teorema de Artin-Zorn .

Ver también

• Campo cuasi-finito
• Campo con un elemento
• Aritmética de campos finitos
• Anillo finito
• Grupo finito
• Grupo abeliano elemental
• Espacio Hamming

Notas

Referencias

enlaces externos

• Campos finitos en Wolfram research.