campo finito

estructura algebraica

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 cuerpo, un cuerpo finito es un conjunto sobre el cual las operaciones de multiplicación, suma, resta y división están definidas y cumplen ciertas reglas básicas. Los ejemplos más comunes de campos finitos vienen dados por los números enteros mod p cuando p es un número primo .

El orden de un campo finito es su número de elementos, que es un número primo o una potencia prima . Para cada número primo p y cada entero positivo k existen campos de orden p ^k , todos los cuales son isomorfos .

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 cuerpo finito se llama orden o, en ocasiones, tamaño . Un campo finito de orden q existe si y sólo si q es una potencia prima p ^k (donde p es un número primo y k es un entero positivo). En un campo de orden p ^k , sumar 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 isomórficos (ver § Existencia y unicidad a continuación). ^[1] 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". ^[2] ${\displaystyle \mathbb {F} _{q}}$

En un campo finito de orden q , el polinomio X ^q − X tiene todos los q elementos del campo finito como raíces . Los elementos distintos de cero de un cuerpo finito forman un grupo multiplicativo . Este grupo es cíclico , por lo que todos los elementos distintos de cero pueden expresarse 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 primo de orden p puede construirse como los números enteros módulo p ,. ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

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 entre p del resultado de la operación entera correspondiente. El inverso multiplicativo de un elemento se puede calcular utilizando el algoritmo euclidiano extendido (consulte Algoritmo euclidiano extendido § Enteros modulares ).

Sea F un cuerpo finito. Para cualquier elemento x en F y cualquier número entero n , denota 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 ( k , x ) ↦ k ⋅ x de un elemento k de GF( p ) por un elemento x de F eligiendo un número entero representativo de k . Esta multiplicación convierte a F en un espacio vectorial GF ( p ) . Se deduce que el número de elementos de F es p ⁿ para algún número entero n .

La identidad

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

sueño del estudiante de primer añopteorema del binomiocoeficiente binomial( x + y ) ^pp

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 \mathrm {GF} (p)}(X-a)}$$

GF( p )GF( p ⁿ )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 cuerpo finito y F es un subcampo de E , entonces E se obtiene de F uniendo 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 necesita 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 finito es conmutativo y, por tanto, es un campo finito.

Existencia y unicidad

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

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

GF( p )FPqderivada formalPP ′ = −1mcd( P , P ′ ) = 1extensión separablePPP. PqF

La unicidad hasta el isomorfismo de la división de campos 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 q raíces de X ^q − X , y F no puede contener otro subcampo de orden q .

En resumen, tenemos el siguiente teorema de clasificación demostrado por primera vez en 1893 por EH Moore : ^[1]

El orden de un campo finito es una potencia prima. 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 se factoriza como

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

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

Construcción explícita

Campos no principales

Dada una potencia prima q = p ⁿ con p prima y n > 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 cociente

$${\displaystyle \mathrm {GF} (q)=\mathrm {GF} (p)[X]/(P)}$$

GF( p )[ X ]Pq

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 se puede calcular con el algoritmo euclidiano extendido; ver Algoritmo euclidiano extendido § Extensiones de campos algebraicos simples .

Sin embargo, con esta representación, los elementos de GF( q ) pueden resultar difíciles de distinguir de los polinomios correspondientes. Por tanto, es común darle un nombre, comúnmente α al elemento de GF( q ) que corresponde al polinomio X . Entonces, los elementos de GF( q ) se convierten en polinomios en α , donde P ( α ) = 0 , y, cuando se encuentra un polinomio en α de grado mayor o igual a n (por ejemplo después de una multiplicación), se sabe que tiene que usar la relación P ( α ) = 0 para reducir su grado (es lo que está haciendo la división euclidiana).

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, comúnmente se elige para P un polinomio de la forma

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

2X ⁿ + aX + b . 2X ⁿ + X + 1X ⁿ + X ^k + 1ktrinomiosX ⁿ + X ^a + X ^b + X ^c + 1121^[3]

Una posible elección para dicho polinomio viene dada por los polinomios de Conway . 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 como GF(4) o Consta de los cuatro elementos 0, 1, α , 1 + α tal que α ² = 1 + α , 1 ⋅ α = α ⋅ 1 = α , x + x = 0 , y x ⋅ 0 = 0 ⋅ x = 0 , para cada x ∈ GF(4) , la otra operación resulta deduciéndose fácilmente de la ley distributiva . Consulte a continuación las tablas de operación completas. ${\displaystyle \mathbb {F} _{4}.}$

Esto se puede deducir de lo siguiente de los resultados del apartado anterior.

Sobre GF(2) , sólo hay un polinomio irreducible de grado 2 :

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

GF(4)

$${\displaystyle \mathrm {GF} (4)=\mathrm {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) . De ello resultan las tablas de operaciones del GF(4) , que son las siguientes:

No se proporciona una tabla para la resta, porque la resta es idéntica a la suma, como es el caso para cada campo de la característica 2. En la tercera tabla, para la división de x entre y , los valores de x deben leerse en la columna de la izquierda. y los valores de y en la fila superior. (Debido a que 0 ⋅ z = 0 para cada z en cada anillo , la división por 0 debe permanecer indefinida). De las tablas, se puede ver que la estructura aditiva de GF(4) es isomorfa al grupo de cuatro de Klein , mientras que la estructura multiplicativa distinta de cero es isomorfa al grupo Z ₃ .

El mapa

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

α1 + αX ² + X + 1

GF( p 2 ) para un primo impar p

Para aplicar la construcción general anterior de campos finitos en el caso de GF( p ² ) , es necesario encontrar un polinomio irreducible de grado 2. Para p = 2 , esto se hizo 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 sólo si r es un módulo cuadrático sin residuo p (esta es casi la definición de un polinomio cuadrático sin residuo). Haypag -1/2Módulo cuadrático sin residuos 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 r cuadrático sin residuo , sea α una raíz cuadrada simbólica de r , es decir, 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 ,}$$

abGF( p )GF( p ² )GF( p )GF( p )

$${\displaystyle {\begin{aligned}-(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{aligned}}}$$

GF(8) y GF(27)

El polinomio

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

GF(2)GF(3)23GF(2)GF(3)GF(8)GF(27)expresiones

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

a , b , cGF(2)GF(3)α

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

La suma, el inverso aditivo y la multiplicación de 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) , representados por letras latinas, son las operaciones en GF(2) o GF(3) , respectivamente:

$${\displaystyle {\begin{aligned}-(a+b\alpha +c\alpha ^{2})&=-a+(-b)\alpha +(-c)\alpha ^{2}\qquad {\text{(for }}\mathrm {GF} (8),{\text{this operation is the identity)}}\\(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{aligned}}}$$

novia(16)

El polinomio

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

GF(2)2GF(16)expresiones

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

a , b , c , d01GF(2)α

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

αGF(2)2GF(16)GF(16)GF(2)GF(2)

$${\displaystyle {\begin{aligned}(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{aligned}}}$$

El campo GF(16) tiene ocho elementos primitivos (los elementos que tienen todos los elementos distintos de cero de GF(16) como potencias enteras). Estos elementos son las cuatro raíces de X ⁴ + X + 1 y sus inversos multiplicativos . En particular, α es un elemento primitivo, y los elementos primitivos son α ^m con m menor que y coprimo con 15 (es decir, 1, 2, 4, 7, 8, 11, 13, 14).

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 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, es decir, existe un elemento a , tal que los q – 1 elementos distintos de cero de GF( q ) son a , a ² , ..., un ^{q −2} , un ^{q −1} = 1 .

Tal elemento a se llama elemento primitivo de GF( q ) . 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 , existe un entero único n con 0 ≤ n ≤ q − 2 tal que

x = un ^norte .

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

Si bien an ^se puede calcular muy rápidamente, por ejemplo usando la exponenciación elevando al cuadrado , no se conoce ningún 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

un ^metro + un ^norte = un ^norte ( un ^{metro - norte} + 1)

permite resolver este problema construyendo la tabla de logaritmos discretos de an ⁺ 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 como para hacer que los algoritmos naturales sean ineficientes, pero no demasiado grandes, ya que hay que calcular previamente una tabla del mismo tamaño. como el orden del campo.

Raíces de unidad

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

Si n es un entero positivo, una n -ésima 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 entero positivo m < n . Si a es una n- ésima raíz primitiva de la unidad en un campo F , entonces F contiene todas las n raíces de la unidad, que son 1, a , a ² , ..., a ^{n −1} .

El campo GF( q ) contiene una n- ésima 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 totiente de Euler ). El número de n -ésimas raíces de la unidad en GF( q ) es mcd( n , q − 1 ) .

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

Por otro lado, si n es coprimo de p , las raíces del n -ésimo polinomio ciclotómico son distintas en cada campo de característica p , ya que este polinomio es un divisor de X ⁿ − 1 , cuyo discriminante n ⁿ es módulo p distinto de cero . De ello se deduce que el n -ésimo polinomio ciclotómico factoriza sobre GF( p ) en distintos polinomios irreducibles que tienen todos el mismo grado, digamos ^d , y que GF( pd ) es el campo más pequeño de la característica p que contiene las n -ésimas raíces primitivas de unidad.

Ejemplo: GF(64)

El campo GF(64) tiene varias propiedades interesantes que los campos más pequeños no comparten: tiene dos subcampos tales 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 no todos los elementos primitivos son 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 GF(64) en sí. Como 2 y 3 son coprimos , la intersección de GF(4) y GF(8) en GF(64) es el campo primo 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 dividiendo 63 . Como las raíces tercera y séptima de la unidad pertenecen a GF(4) y GF(8) , respectivamente, los 54 generadores son raíces nésimas primitivas de la unidad para algún n en { 9, 21, 63} . La función totiente de Euler muestra que hay 6 raíces primitivas de la unidad 9 , 12 raíces primitivas de la unidad 21 y 36 raíces primitivas de la unidad 63 . Sumando estos números, se encuentran nuevamente 54 elementos.

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

• Las seis novenas raíces primitivas de la unidad son raíces de
  $${\displaystyle X^{6}+X^{3}+1,}$$
  y todos están conjugados bajo la acción del grupo de Galois.
• Las doce raíces primitivas 21 de la unidad 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 de 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 seis órbitas de seis elementos cada una 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 sencilla.

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}}$$

endomorfismo lineal( p )automorfismo de campoGF( q )GF( p )automorfismo de Frobeniusa Ferdinand Georg Frobenius

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

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

φ ⁿ0 < k < nφ ^k

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

p ^k

No existen otros automorfismos GF( p ) 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 polinomial

Si F es un cuerpo finito, un polinomio mónico no constante con coeficientes en F es irreducible sobre F , si no es el producto de dos polinomios mónicos 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 irreducibilidad de polinomios y factorizar polinomios en un campo finito. Son un paso clave para factorizar polinomios sobre números enteros o racionales . Al menos por esta razón, todo sistema de álgebra informática tiene funciones para factorizar polinomios en cuerpos finitos o, al menos, en cuerpos primos finitos.

Polinomios irreducibles de un grado dado

El polinomio

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

qq

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 a n . De hecho, si P es un factor irreducible sobre GF( p ) de X ^q − X , su grado divide a 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 a 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 ^{n )} ) , 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últiplo, es el producto de todos los polinomios mónicos irreducibles que lo dividen.

Esta propiedad se utiliza 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 ^[4]

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

μfunción de MöbiusX ^q − Xfórmula de inversión de Möbius

Según la fórmula anterior, el número de polinomios irreducibles (no necesariamente mónicos) de grado n sobre GF( q ) es ( q − 1) N ( q , n ) .

La fórmula exacta implica la desigualdad.

$${\displaystyle N(q,n)\geq {\frac {1}{n}}\left(q^{n}-\sum _{\ell \mid n,\ \ell {\text{ prime}}}q^{n/\ell }\right);}$$

nqnnGF( q )

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 a Internet a Wikipedia implicaba el protocolo de curva elíptica Diffie-Hellman ( ECDHE ) sobre un gran campo finito. ^[5] En la teoría de la codificación , muchos códigos se construyen como subespacios de espacios vectoriales sobre campos finitos.

Muchos códigos de corrección de errores utilizan campos finitos , 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 puede interpretarse como un elemento de GF(2 ⁸ ) . Una excepción es el código de barras PDF417 , que es GF(929) . Algunas CPU tienen instrucciones especiales que pueden ser útiles para campos finitos de la característica 2 , generalmente variaciones de productos sin acarreo .

Los campos finitos se utilizan ampliamente en teoría de números , ya que muchos problemas sobre números enteros pueden resolverse reduciéndolos en módulo uno o varios números primos . Por ejemplo, los algoritmos más rápidos conocidos para la factorización polinomial y el álgebra lineal sobre el campo de números racionales proceden mediante la reducción en módulo de uno o varios primos, y luego la reconstrucción de la solución utilizando el teorema chino del resto , 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 módulo de 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 demostración de Wiles del último teorema de Fermat es un ejemplo de un resultado profundo que involucra muchas herramientas matemáticas, incluidos 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 amplia aplicación en combinatoria , dos ejemplos bien conocidos son la definición de Paley Graphs y la construcción relacionada de Hadamard Matrices . En combinatoria aritmética, los campos finitos ^[6] y los modelos de campos finitos ^{[7] [8]} se utilizan ampliamente, como en el teorema de Szemerédi sobre progresiones aritméticas.

Extensiones

El pequeño teorema de Wedderburn

Un anillo de división es una generalización del 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 y, por tanto, son campos finitos. Este resultado se mantiene incluso si relajamos el axioma de asociatividad a la alternatividad , es decir, todos los anillos de división alternativos finitos son campos finitos, según el teorema de Artin-Zorn . ^[9]

cierre algebraico

Un cuerpo finito F no es algebraicamente cerrado: el polinomio

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

Ff  ( α ) = 1αF

Dado un número primo p , sea un cierre algebraico de No sólo es único hasta un isomorfismo, como lo son todos los cierres algebraicos, sino que contrariamente al caso general, todos sus subcampos están fijados por todos sus automorfismos, y también es el cierre algebraico de todos los campos finitos de la misma característica p . ${\displaystyle {\overline {\mathbb {F} }}_{p}}$ ${\displaystyle \mathbb {F} _{p}.}$

Esta propiedad resulta principalmente del hecho de que los elementos de son exactamente las raíces de y esto define una inclusión para Estas inclusiones permiten escribir de manera informal ${\displaystyle \mathbb {F} _{p^{n}}}$ ${\displaystyle x^{p^{n}}-x,}$ ${\displaystyle \mathbb {\mathbb {F} } _{p^{n}}\subset \mathbb {F} _{p^{nm}}}$ ${\displaystyle m>1.}$

$${\displaystyle {\overline {\mathbb {F} }}_{p}=\bigcup _{n\geq 1}\mathbb {F} _{p^{n}}.}$$

conjunto dirigidolímite directo ${\displaystyle {\overline {\mathbb {F} }}_{p},}$

Elementos primitivos en la clausura algebraica.

Dado un elemento primitivo de entonces es un elemento primitivo de ${\displaystyle g_{mn}}$ ${\displaystyle \mathbb {F} _{q^{mn}},}$ ${\displaystyle g_{mn}^{m}}$ ${\displaystyle \mathbb {F} _{q^{n}}.}$

Para cálculos explícitos, puede resultar útil tener una elección coherente de los elementos primitivos para todos los campos finitos; es decir, elegir el elemento primitivo de para que, siempre que se tenga dónde esté el elemento primitivo ya elegido para ${\displaystyle g_{n}}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle n=mh,}$ ${\displaystyle g_{m}=g_{n}^{h},}$ ${\displaystyle g_{m}}$ ${\displaystyle \mathbb {F} _{q^{m}}.}$

Esta construcción puede obtenerse mediante polinomios de Conway .

Cierre cuasi algebraico

Aunque los campos finitos no son algebraicamente cerrados, son cuasi-algebraicamente cerrados , lo que significa que todo 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. Esta fue una conjetura de Artin y Dickson demostrada por Chevalley (ver Teorema de Chevalley-Warning ).

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

1. Moore, EH (1896), "Un sistema doblemente infinito de grupos simples", en EH Moore; et al. (eds.), Artículos matemáticos leídos en el Congreso Internacional de Matemáticas celebrado en relación con la Exposición Mundial Colombina , Macmillan & Co., págs.
2. Esta última notación fue introducida por EH Moore en un discurso pronunciado en 1893 en el Congreso Internacional de Matemáticas celebrado en Chicago Mullen & Panario 2013, p. 10.
3. Curvas elípticas recomendadas para uso gubernamental (PDF) , Instituto Nacional de Estándares y Tecnología , julio de 1999, p. 3, archivado (PDF) desde el original el 19 de julio de 2008.
4. Jacobson 2009, §4.13
5. Esto se puede verificar mirando la información en la página proporcionada por el navegador.
6. Shparlinski, Igor E. (2013), "Combinatoria aditiva sobre campos finitos: nuevos resultados y aplicaciones", Campos finitos y sus aplicaciones , DE GRUYTER, págs. 233–272, doi :10.1515/9783110283600.233, ISBN 9783110283600
7. Green, Ben (2005), "Modelos de campos finitos en combinatoria aditiva", Surveys in Combinatorics 2005 , Cambridge University Press, págs. 1-28, arXiv : math/0409420 , doi :10.1017/cbo9780511734885.002, ISBN 9780511734885, S2CID  28297089
8. Wolf, J. (marzo de 2015). "Modelos de campos finitos en combinatoria aritmética: diez años después". Campos finitos y sus aplicaciones . 32 : 233–274. doi : 10.1016/j.ffa.2014.11.003 . hdl : 1983/d340f853-0584-49c8-a463-ea16ee51ce0f . ISSN  1071-5797.
9. Shult, Ernest E. (2011). Puntos y líneas. Caracterizando las geometrías clásicas . Texto universitario. Berlín: Springer-Verlag . pag. 123.ISBN _ 978-3-642-15626-7. Zbl  1213.51001.

Referencias

• WH Bussey (1905) "Tablas de campo de Galois para p ⁿ ≤ 169 ", Boletín de la Sociedad Matemática Estadounidense 12(1): 22–38, doi :10.1090/S0002-9904-1905-01284-2
• WH Bussey (1910) "Tablas de campos de Galois de orden <1000", Boletín de la Sociedad Matemática Estadounidense 16(4): 188–206, doi :10.1090/S0002-9904-1910-01888-7
• Jacobson, Nathan (2009) [1985], Álgebra básica I (Segunda ed.), Publicaciones de Dover, ISBN 978-0-486-47189-1
• Mullen, Gary L.; Mummert, Carl (2007), Campos finitos y aplicaciones I , Biblioteca de matemáticas para estudiantes (AMS), ISBN 978-0-8218-4418-2
• Mullen, Gary L.; Panario, Daniel (2013), Manual de campos finitos , CRC Press, ISBN 978-1-4398-7378-6
• Lidl, Rudolf; Niederreiter, Harald (1997), Campos finitos (2ª ed.), Cambridge University Press , ISBN 0-521-39231-4
• Skopin, AI (2001) [1994], "Campo de Galois", Enciclopedia de Matemáticas , EMS Press

enlaces externos

• Campos finitos en Wolfram Research.