Campo finito

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

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 todo campo, un campo finito es un conjunto sobre el que 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 son 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 ya sea un número primo o un poder primario. Por cada número primo $p$ y cada entero positivo $k$ hay campos de orden $p^k,$ todos son isomorfos.

Los campos finitos son fundamentales en varias áreas de las matemáticas y la informática, incluidas 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 llama su orden o, a veces, su tamaño. Un campo finito de orden $q$ existe si y solo si $q$ es una potencia principal $p k$ (donde $p$ es un número primo y $k$ es un número entero positivo). En un campo de orden $p k$ , agregando $p$ las copias de cualquier elemento siempre dan 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 singularidad debajo). Además, un campo no puede contener dos subcampos finitos diferentes con el mismo orden. Por lo tanto, uno puede identificar todos los campos finitos con el mismo orden, y están denotados inequívocamente ${mathbb {F}}_{{q}}$ , $F q$ o $GF(q)$ , donde las letras GF destacan por "campo de Galois".

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 dado).

Los ejemplos más simples de campos finitos son los campos de orden principal: para cada número primo $p$ , el primer campo de orden $p$ , $mathbb {F} _{p}$ , puede ser construido como los enteros modulo p, $Z / p Z$ .

Los elementos del primer campo de orden $p$ pueden ser representados por 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 utilizando el algoritmo euclidiano extendido (ver Algoritmo euclidiano extendido § Enteros modulares).

Vamos $F$ Sé un campo finito. Para cualquier elemento $x$ dentro $F$ y cualquier entero $n$ , denota $n \cdot x$ la suma de $n$ copias de $x$ . Lo menos positivo $n$ tales que $n \cdot 1 = 0$ es la característica $p$ del campo. Esto permite definir una multiplicación ${displaystyle (k,x)mapsto kcdot x}$ de un elemento $k$ de $GF(p)$ por un elemento $x$ de $F$ por elegir un representante entero para $k$ . Esta multiplicación hace $F$ en una $GF(p)$ -Espacio del vencedor. De ahí que el número de elementos $F$ es $p n$ para algunos enteros $n$ .

La identidad

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

p

() x + Sí.) p

p

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

{displaystyle X^{p}-X=prod _{ain mathrm {GF} (p)}(X-a)}

GF(p)

GF(p n)

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$ 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 requiere que sea conmutativa, se denomina anillo de división (o, a veces, campo sesgado). Por el pequeño teorema de Wedderburn, cualquier anillo de división finito es conmutativo y, por lo tanto, es un campo finito.

Existencia y unicidad

Sea $q = p n$ una potencia principal, y $F$ sea el campo de división del polinomio

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

GF(p)

F

P

q

P

P . = 1 -

gcd(P, P .) = 1

P

P

P

P

q

F

La unicidad hasta el isomorfismo de dividir campos implica 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 el $q$ raíces de $X q - X$ , y $F$ no pueden contener otro subcampo de orden $q$ .

En resumen, tenemos el siguiente teorema de clasificación demostrado por primera vez en 1893 por E. H. Moore:

El orden de un campo finito es un poder primario. Por cada potencia principal $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
${displaystyle X^{q}-X=prod _{ain F}(X-a).}$

Se sigue que $GF(p n)$ 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 principal $q = p n$ con $p$ primo 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 del cociente

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

GF(p [X]

P

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

Excepto en la construcción de $GF(4)$ , hay varias opciones posibles para $P$ , que producen resultados isomorfos. Para simplificar la división euclidiana, comúnmente se elige para $P$ un polinomio de la forma

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

2

X n + aX + b

2

X n + X + 1

X n + X k + 1

k

X n + X a + X b + X c + 1

1

2

1

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

En las próximas 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 alto más pequeño es el campo con cuatro elementos, que es comúnmente denotado $GF(4)$ o ${displaystyle mathbb {F} _{4}.}$ Se compone de los cuatro elementos ${displaystyle 0,1,alpha1+alpha }$ tales que ${displaystyle alpha ^{2}=1+alpha}$ ${displaystyle 1cdot alpha =alpha cdot 1=alpha}$ ${displaystyle x+x=0,}$ y ${displaystyle xcdot 0=0cdot x=0,}$ para todos ${displaystyle xin operatorname {GF} (4),}$ la otra operación resulta ser fácilmente deducido de la ley distributiva. Vea a continuación las tablas de operaciones completas.

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

Sobre $GF(2)$ , solo 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

α 2 = 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:

Adición

x + Sí.

Multiplicación

x \cdot Sí.

División

x / Sí.

$Sí.$ $x$	$0$	$1$	$α$	$1 + α$
$0$	$0$	$1$	$α$	$1 + α$
$1$	$1$	$0$	$1 + α$	$α$
$α$	$α$	$1 + α$	$0$	$1$
$1 + α$	$1 + α$	$α$	$1$	$0$

$Sí.$ $x$	$0$	$1$	$α$	$1 + α$
$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$α$	$1 + α$
$α$	$0$	$α$	$1 + α$	$1$
$1 + α$	$0$	$1 + α$	$1$	$α$

$Sí.$ $x$	$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 de cada campo 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. (Porque $0 \cdot 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 a los cuatro de Klein -grupo, mientras que la estructura multiplicativa distinta de cero es isomorfa a Z₃.

El mapa

{displaystyle varphi:xmapsto x^{2}}

α

1 + α

{displaystyle X^{2}+X+1.}

GF(p2) para un primo impar p

Para aplicar la construcción general anterior de campos finitos en el caso de $GF(p 2)$ , se tiene para 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 2 - r$ , con $r$ en $GF(p)$ .

Más precisamente, el polinomio $X 2 - r$ es irreducible sobre $GF(p)$ si y solo si $r$ es un no cuadrático residuo módulo $p$ (esta es casi la definición de un no residuo cuadrático). Hay $p - 1 / 2$ mó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 \equiv 3 mod 4$ , eso es $p = 3, 7, 11, 19,...$ , se puede elegir $-1 \equiv p - 1$ como un no residuo cuadrático, lo que nos permite tiene un polinomio irreducible muy simple $X 2 + 1$ .

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

{displaystyle a+balpha}

a

b

GF(p)

GF(p 2)

GF(p)

GF(p)

{displaystyle {begin{aligned}-(a+balpha)&=-a+(-b)alpha \(a+balpha)+(c+dalpha)&=(a+c)+(b+d)alpha \(a+balpha)(c+dalpha)&=(ac+rbd)+(ad+bc)alpha \(a+balpha)^{-1}&=a(a^{2}-rb^{2})^{-1}+(-b)(a^{2}-rb^{2})^{-1}alpha end{aligned}}}

FG(8) y FG(27)

El polinomio

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

GF(2)

GF(3)

2

3

GF(2)

GF(3)

GF(8)

GF(27)

{displaystyle a+balpha +calpha ^{2},}

a, b, c

GF(2)

GF(3)

alpha

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

La suma, el inverso aditivo y la multiplicación en $GF(8)$ y $GF(27)$ pueden definirse de la siguiente manera; 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{aligned}-(a+balpha +calpha ^{2})&=-a+(-b)alpha +(-c)alpha ^{2}qquad {text{(for }}mathrm {GF} (8),{text{this operation is the identity)}}\(a+balpha +calpha ^{2})+(d+ealpha +falpha ^{2})&=(a+d)+(b+e)alpha +(c+f)alpha ^{2}\(a+balpha +calpha ^{2})(d+ealpha +falpha ^{2})&=(ad+bf+ce)+(ae+bd+bf+ce+cf)alpha +(af+be+cd+cf)alpha ^{2}end{aligned}}}

FG(16)

El polinomio

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

GF(2)

2

GF(16)

{displaystyle a+balpha +calpha ^{2}+dalpha ^{3},}

a, b, c, d

0

1

GF(2)

α

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

α

GF(2)

2

GF(16)

GF(16)

GF(2)

GF(2)

{displaystyle {begin{aligned}(a+balpha +calpha ^{2}+dalpha ^{3})+(e+falpha +galpha ^{2}+halpha ^{3})&=(a+e)+(b+f)alpha +(c+g)alpha ^{2}+(d+h)alpha ^{3}\(a+balpha +calpha ^{2}+dalpha ^{3})(e+falpha +galpha ^{2}+halpha ^{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 no cero de $GF(16)$ como poderes enteros). Estos elementos son las cuatro raíces de $X^{4}+X+1$ y sus inversos multiplicadores. En particular, $α$ es un elemento primitivo, y los elementos primitivos son $alpha ^{m}$ con $m$ menos que y coprime 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$ . Por el teorema de Lagrange, existe un divisor $k$ de $q - 1$ tal que $x k = 1$ para cada $distinto de cero x$ 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 alto posible para $k$ . El teorema de estructura de 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 multiplicador de los elementos no cero en

GF(q)

es cíclico, y existe un elemento

a

, tal que

q - 1

no cero elementos de

GF(q)

son

a, a 2,... a q -2, a q -1 = 1

Tal 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 totient 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)$ , luego para cualquier elemento distinto de cero $x$ en $F$ , hay un entero único $n$ con $0 \leq n \leq q - 2$ tal que

x = a n

Este número entero $n$ se denomina logaritmo discreto de $x$ a la base $a$ .

Mientras que $a n$ se puede calcular muy rápidamente, por ejemplo usando la exponenciación al cuadrado, no existe una eficiencia conocida algoritmo 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 información.

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 módulo de resta $q - 1$ . Sin embargo, la suma equivale a calcular el logaritmo discreto de $a m + a n$ . La identidad

a m + a n = a n () a m - n + 1)

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

Los logaritmos de Zech son útiles para cálculos grandes, como á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 pre- calcular una tabla del mismo tamaño que el orden del campo.

Raíces de unidad

Todo elemento distinto de cero de un campo finito es una raíz de la unidad, como $x q -1 = 1$ para cada elemento distinto de cero de $GF(q)$ .

Si $n$ es un número entero positivo, un $n$ -th raíz primitiva de la unidad es una solución de la ecuación $x n = 1$ que no es una solución de la ecuación $x m = 1$ para cualquier número entero positivo $m < n$ . Si $a$ es una $n$ ésima raíz primitiva de la unidad en un campo $F$ , entonces $F$ contiene todos los $n$ raíces de unidad, que son $1, a, a 2,..., a n -1$ .

El campo $GF(q)$ contiene un $n$ la raíz primitiva de la unidad si y solo 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 $n$ ésimas raíces de la unidad en $GF(q)$ es $gcd(n, q - 1)$ .

En un campo de característica $p$ , cada $(np)$ th raíz de la unidad es también una $n$ th 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 coprime $p$ , las raíces de las $n$ polinomio ciclotómico son distintos en cada campo de características $p$ , como este polinomio es un divisor de $X n - 1$ , cuya discriminación $n^n$ no cero modulo $p$ . De ahí que $n$ ciclotómicos factores polinomios $GF(p)$ en polinomios irreducibles distintos que tienen todo el mismo grado, dicen $d$ , y eso $GF(p d)$ es el campo más pequeño de la característica $p$ que contiene $n$ las raíces primitivas de la unidad.

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 $26$ , y los divisores de $6$ son $1, 2, 3, 6$ , los subcampos de $GF(64)$ son $GF(2)$ , $GF(2 2) = GF(4)$ , $GF(2 3) = GF(8)$ , y $GF(64)$ en sí mismo. Como $2$ y $3$ son coprimos, la intersección de $GF(4)$ y $GF(8)$ en $GF(64)$ es el campo principal $GF(2)$ .

La unión de $GF(4)$ y $GF(8)$ tiene por lo 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 / 6$ monic irreducible polinomios de grado $6$ . Esto se puede verificar factorizando $X 64 - X$ sobre $GF(2)$ .

Los elementos de $GF(64)$ son raíces primitivas $n$ ésimas de unidad para algunos $n$ dividiendo $63$ . Como las raíces 3 y 7 de la unidad pertenecen a $GF(4)$ y $GF(8)$ , respectivamente, el $54$ son $n$ th raíces primitivas de unidad para algunos $n$ en ${9, 21, 63}$ . La función totient de Euler muestra que hay $6$ $9$ raíces primitivas de la unidad, $12$ primitivas $21$ raíces de unidad, y $36$ primitivas $63$ rd raíces de unidad. Sumando estos números, uno encuentra de nuevo $54$ elementos.

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

Los seis primitivos $9$ las raíces de la unidad son raíces de ${displaystyle X^{6}+X^{3}+1,}$ y están todos conjugados bajo la acción del grupo Galois.
Los doce primitivos $21$ raíces 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 Galois. Como los dos factores son recíprocos entre sí, una raíz y su inverso (multiplicativo) no pertenecen a la misma órbita.
El $36$ elementos primitivos $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 uno 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 6 + 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 n$ es una potencia de $p$ .

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

{displaystyle varphi:xmapsto x^{p}}

GF(p)

GF(q)

GF(p)

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

{displaystyle varphi ^{k}:xmapsto x^{p^{k}}.}

φ n

0 k . n

φ k

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

p k

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

{displaystyle mathrm {Id} =varphi ^{0},varphivarphi ^{2},ldotsvarphi ^{n-1}.}

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

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 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 de polinomio sobre un campo es un dominio de factorización único, cada polinomio mónico sobre un campo finito se puede factorizar 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 en campos finitos. Son un paso clave para factorizar polinomios sobre los números enteros o los números racionales. Al menos por esta razón, cada 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}

q

q

Esto implica que, si $q = p n$ entonces $X q - X$ es el producto de todos los polinomios irreducibles mónicos 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 n)$ . Por el contrario, si $P$ es un polinomio mónico irreducible sobre $GF(p)$ de grado $d$ dividiendo $n$ , define un campo extensión del grado $d$ , que está contenido en $GF(p n)$ , y todas las raíces de $P$ pertenecen a $GF(p n)$ , y son raíces de $X q - X$ ; así $P$ divide $X q - X$ . Como $X q - X$ no tiene ningún factor múltiple, entonces es el producto de todos los polinomios mónicos irreducibles que la 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 grado distinto.

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)$ está dada por

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

μ

X q - X

Con 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);}

n

q

n

n

GF(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 de Internet a Wikipedia involucró 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 características 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 ${displaystyle GF(2^{8})}$ . Una excepción es el código de barras PDF417, que es ${displaystyle GF(929)}$ . Algunos Las CPU tienen instrucciones especiales que pueden ser útiles para campos finitos de características 2, generalmente variaciones de producto sin carga.

Los campos finitos se utilizan ampliamente en la teoría de números, ya que muchos problemas sobre 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 mediante el uso del teorema del resto chino, el levantamiento de Hensel o el algoritmo LLL.

Del mismo modo, muchos problemas teóricos en la teoría de números pueden resolverse considerando sus reducciones 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. Artimañas' La prueba 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 amplia aplicación en combinatoria, dos ejemplos bien conocidos son la definición de Paley Graphs y la construcción relacionada para Hadamard Matrices. En la combinatoria aritmética, los campos finitos y los modelos de campos finitos 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),}

F

f () α) = 1

α

F

Arreglar un cierre algebraico ${displaystyle {overline {mathbb {F} }}_{q}}$ de $mathbb {F} _{q}$ . El mapa ${displaystyle varphi _{q}colon {overline {mathbb {F} }}_{q}to {overline {mathbb {F} }}_{q}}$ enviando cada uno $x$ a $x q$ se llama $q$ potencia automorfismo Frobenius. El subcampo ${displaystyle {overline {mathbb {F} }}_{q}}$ fijado por el $n$ t iterate of ${displaystyle varphi _{q}}$ es el conjunto de ceros del polinomio $x q n - x$ , que tiene raíces distintas desde su derivación en ${displaystyle mathbb {F} _{q}[x]}$ es $-1$ , que nunca es cero. Por lo tanto, el subcampo tiene $q n$ elementos, por lo que es la copia única ${displaystyle mathbb {F} _{q^{n}}}$ dentro ${displaystyle {overline {mathbb {F} }}_{q}}$ . Cada extensión finita de $mathbb {F} _{q}$ dentro ${displaystyle {overline {mathbb {F} }}_{q}}$ Es esto ${displaystyle mathbb {F} _{q^{n}}}$ para algunos $n$ Así que

{displaystyle {overline {mathbb {F} }}_{q}=bigcup _{ngeq 1}mathbb {F} _{q^{n}}.}

mathbb {F} _{q}

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

{displaystyle operatorname {Gal} ({overline {mathbb {F} }}_{q}/mathbb {F} _{q})}

{displaystyle varphi _{q}}

{displaystyle operatorname {Gal} (mathbb {F} _{q^{n}}/mathbb {F} _{q})simeq mathbf {Z} /nmathbf {Z} }

1

{displaystyle varphi _{q}}

{displaystyle 1in {widehat {mathbf {Z} }}}

{displaystyle varphi _{q}}

{displaystyle operatorname {Gal} ({overline {mathbb {F} }}_{q}/mathbb {F} _{q})}

{displaystyle 1in {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 todo polinomio homogéneo sobre un campo finito tiene un cero no trivial cuyas 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 probada por Chevalley (ver el teorema de Chevalley-Warning).

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 lo 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.

Contenido relacionado

Más resultados...