Campo finito

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

El orden de un cuerpo finito es su número de elementos, que es un número primo o una potencia de un número primo . Para cada número primo $p$ y cada entero positivo $k$ Hay campos de orden $p^{k}$ Todos los campos finitos de un orden dado son isomorfos .

Los campos finitos son fundamentales en varias áreas de las matemáticas y la informática , incluyendo 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 cuerpo finito es un cuerpo que es un conjunto finito ; esto significa que tiene un número finito de elementos sobre los cuales se definen la multiplicación, la suma, la resta y la división (excluyendo la división por cero) y satisfacen los axiomas del cuerpo . ^{[ 1 ]}

El número de elementos de un cuerpo finito se llama su orden o, a veces, su tamaño . Un cuerpo finito de orden $q$ existe si y solo si $q$ es un poder primordial $p^{k}$ (dónde $p$ es un número primo y $k$ es un entero positivo). En un campo de orden $p^{k}$ , sumando $p$ Las copias de cualquier elemento siempre dan como resultado cero; es decir, la característica del campo es $p$ . ^{[ 1 ]}

Para $q=p^{k}$ , todos los campos del orden $q$ son isomorfos (véase § Existencia y unicidad más adelante). ^{[ 2 ]} Además, un cuerpo no puede contener dos subcuerpos finitos diferentes con el mismo orden. Por lo tanto, se pueden identificar todos los cuerpos finitos con el mismo orden, y se denotan inequívocamente $\mathbb {F} _{q}$ , $\mathbf {F} _ {q}$ o $\mathrm {GF} (q)$ , donde las letras GF significan "campo Galois". ^{[ 3 ]}

En un campo finito de orden $q$ , el polinomio $X^{q}-X$ tiene todo $q$ elementos del cuerpo finito como raíces . Los elementos no nulos de un cuerpo finito forman un grupo multiplicativo . Este grupo es cíclico , por lo que todos los elementos no nulos pueden expresarse como potencias de un único elemento llamado elemento primitivo del cuerpo. (En general, habrá varios elementos primitivos para un cuerpo dado). ^{[ 1 ]}

Los ejemplos más sencillos de campos finitos son los campos de orden primo: para cada número primo $p$ , el campo principal del orden $p$ puede construirse como los enteros módulo $p$ , $\mathbb {Z} /p\mathbb {Z}$ . ^{[ 1 ]}

Los elementos del campo primo del orden $p$ puede representarse mediante números enteros en el rango $0,\ldots ,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 (véase Inverso multiplicativo modular § Algoritmo euclidiano extendido ). ^{[ 1 ]}

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

La identidad $(x+y)^{p}=x^{p}+y^{p}$ (a veces llamado el sueño del estudiante de primer año ^{[ 4 ]} ) es cierto en un campo de características $p$ Esto se deduce 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$ . ^{[ 1 ]}^{: 548}

Según el pequeño teorema de Fermat , si $p$ es un número primo y $x$ está en el campo $\mathrm {GF} (p)$ entonces $x^{p}=x$ Esto implica la igualdad $X^{p}-X=\prod _{a\in \mathrm {GF} (p)}(X-a)$ para polinomios sobre $\mathrm {GF} (p)$ . De manera más general, cada elemento en $\mathrm {GF} (p^{n})$ satisface la ecuación polinómica $x^{p^{n}}-x=0$ . ^{[ 5 ]}

Cualquier extensión de cuerpo finito de un cuerpo 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$ mediante la conjunción de un único elemento cuyo polinomio mínimo es separable . Para usar un término técnico, los cuerpos finitos son perfectos . ^{[ 1 ]}

Los cuerpos finitos son cuasi-algebraicamente cerrados : cada grado $d es$ un polinomio homogéneo en $n$ variables sobre un cuerpo finito con $n>d>0$ tiene un cero no trivial. Esta fue una conjetura de Artin y Dickson , y fue demostrada por Chevalley ; véase el teorema de Chevalley-Warning .

Existencia y singularidad

Dejar $q=p^{n}$ ser una potencia principal y $F$ sea el campo de descomposición del polinomio $P=X^{q}-X$ sobre el campo principal $\mathrm {GF} (p)$ Esto significa que $F$ es un campo finito de orden más bajo, en el que $P$ tiene $q$ raíces distintas (el derivado formal de $P$ es $P'=-1$ , lo que implica que $\mathrm {gcd} (P,P')=1$ , lo que en general implica que el campo de descomposición es una extensión separable del original). La identidad anterior 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$ formar un campo de orden $q$ , que es igual a $F$ por la minimalidad del campo divisor.

La unicidad salvo isomorfismo de los campos de descomposición implica, por lo 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 los $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 E. H. Moore : ^{[ 2 ]}

El orden de un cuerpo 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 $x^{q}=x,$ y el polinomio $X^{q}-X$ factores como $X^{q}-X=\prod _{a\in F}(X-a).$

Resulta que $\mathrm {GF} (p^{n})$ contiene un subcampo isomorfo a $\mathrm {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 primos

Dado un poder primordial $q=p^{n}$ con $p$ principal y $n>1$ , el campo $\mathrm {GF} (q)$ puede construirse explícitamente de la siguiente manera. Primero se elige un polinomio irreducible. $P$ en $\mathrm {GF} (p)[X]$ de grado $n$ (tal polinomio irreducible siempre existe). Entonces el anillo cociente $\mathrm {GF} (q)=\mathrm {GF} (p)[X]/(P)$ del anillo de polinomios $\mathrm {GF} (p)[X]$ por el ideal principal generado por $P$ es un campo de orden $q$ .

Más explícitamente, los elementos de $\mathrm {GF} (q)$ son los polinomios sobre $\mathrm {GF} (p)$ cuyo grado es estrictamente menor que $n$ La suma y la resta son las de polinomios sobre $\mathrm {GF} (p)$ El producto de dos elementos es el resto de la división euclidiana por $P$ del producto en $\mathrm {GF} (p)[X]$ . El inverso multiplicativo de un elemento distinto de cero se puede calcular con el algoritmo euclidiano extendido; véase Algoritmo euclidiano extendido § Extensiones de campos algebraicos simples .

Sin embargo, con esta representación, elementos de $\mathrm {GF} (q)$ puede ser difícil distinguirlo de los polinomios correspondientes. Por lo tanto, es común darle un nombre, comúnmente $\alpha$ al elemento de $\mathrm {GF} (q)$ que corresponde al polinomio $X$ . Entonces, los elementos de $\mathrm {GF} (q)$ se convierten en polinomios en $\alpha$ , dónde $P(\alpha )=0$ y, cuando uno se encuentra con un polinomio en $\alpha$ de grado mayor o igual a $n$ (por ejemplo, después de una multiplicación), uno sabe que tiene que usar la relación $P(\alpha )=0$ para reducir su grado (es lo que hace la división euclidiana).

Excepto en la construcción de $\mathrm {GF} (4)$ , existen 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 $X^{n}+aX+b,$ lo que hace que las divisiones euclidianas necesarias sean muy eficientes. Sin embargo, para algunos campos, típicamente en características $2$ , polinomios irreducibles de la forma $X^{n}+aX+b$ Puede que no exista. En característica $2$ , si el polinomio $X^{n}+X+1$ es reducible, se recomienda elegir $X^{n}+X^{k}+1$ con el menor posible $k$ Eso hace que el polinomio sea irreducible. Si todos estos trinomios son reducibles, se eligen "pentanomios". $X^{n}+X^{a}+X^{b}+X^{c}+1$ , como polinomios de grado mayor que $1$ , con un número par de términos, nunca son irreductibles en característica $2$ , teniendo $1$ como raíz. ^{[ 6 ]}

Una posible opción para este tipo de polinomio son los polinomios de Conway . Estos garantizan cierta compatibilidad entre la representación de un cuerpo y las representaciones de sus subcuerpos.

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 cuerpo no primo más pequeño es el cuerpo con cuatro elementos, que comúnmente se denota $\mathrm {GF} (4)$ o $\mathbb {F} _{4}.$ Consta de cuatro elementos. $0,1,\alpha ,1+\alpha$ de tal manera que $\alpha ^{2}=1+\alpha$ , $1\cdot \alpha =\alpha \cdot 1=\alpha$ , $x+x=0$ , y $x\cdot 0=0\cdot x=0$ , por cada $x\in \mathrm {GF} (4)$ Los demás resultados de las operaciones se deducen fácilmente de la ley distributiva . Consulte a continuación las tablas de operaciones completas.

Esto puede deducirse de la siguiente manera a partir de los resultados de la sección anterior.

Encima $\mathrm {GF} (2)$ , solo hay un polinomio irreducible de grado $2$ : $X^{2}+X+1$ Por lo tanto, para $\mathrm {GF} (4)$ La construcción de la sección anterior debe involucrar este polinomio, y $\mathrm {GF} (4)=\mathrm {GF} (2)[X]/(X^{2}+X+1).$ Dejar $\alpha$ denota una raíz de este polinomio en $\mathrm {GF} (4)$ Esto implica que $\alpha ^{2}=1+\alpha ,$ y eso $\alpha$ y $1+\alpha$ son los elementos de $\mathrm {GF} (4)$ que no están en $\mathrm {GF} (2)$ . Las tablas de las operaciones en $\mathrm {GF} (4)$ El resultado de esto es el siguiente:

No se proporciona una tabla para la resta, porque la resta es idéntica a la suma, como ocurre en todo campo de característica 2. Para dividir, se multiplica por el recíproco : $x/y=x\cdot (1/y)$ ⁠ . Como en cualquier campo, la división por cero no está definida. De las tablas se puede ver que la estructura aditiva de $\mathrm {GF} (4)$ es isomorfo al grupo de Klein de cuatro elementos , mientras que la estructura multiplicativa no nula es isomorfa al grupo $Z_{3}$ .

El mapa $\varphi :x\mapsto x^{2}$ es el automorfismo de cuerpo no trivial, llamado automorfismo de Frobenius , que envía $\alpha$ en la segunda raíz $1+\alpha$ del polinomio irreducible mencionado anteriormente $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 $\mathrm {GF} (p^{2})$ , hay 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^{2}-r$ , con $r$ en $\mathrm {GF} (p)$ .

Más precisamente, el polinomio $X^{2}-r$ es irreductible sobre $\mathrm {GF} (p)$ si y solo si $r$ es un módulo cuadrático no residual $p$ (esta es casi la definición de un no residuo cuadrático). Hay ${\frac {p-1}{2}}$ no residuos cuadráticos módulo $p$ . Por ejemplo, $2$ es un no residuo cuadrático para $p=3,5,11,13,\ldots$ , y $3$ es un no residuo cuadrático para $p=5,7,17,\ldots$ . Si $p\equiv 3\mod 4$ , eso es $p=3,7,11,19,\ldots$ , uno puede elegir $-1\equiv p-1$ como un no residuo cuadrático, lo que nos permite tener un polinomio irreducible muy simple. $X^{2}+1$ .

Habiendo elegido un no residuo cuadrático $r$ , dejar $\alpha$ ser una raíz cuadrada simbólica de $r$ , es decir, un símbolo que tiene la propiedad $\alpha ^{2}=r$ , de la misma manera que el número complejo $i$ es una raíz cuadrada simbólica de $-1$ . Luego, los elementos de $\mathrm {GF} (p^{2})$ son todas expresiones lineales $a+b\alpha ,$ con $a$ y $b$ en $\mathrm {GF} (p)$ Las operaciones en $\mathrm {GF} (p^{2})$ se definen de la siguiente manera (las operaciones entre elementos de $\mathrm {GF} (p)$ representadas por letras latinas son las operaciones en $\mathrm {GF} (p)$ ): ${\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 $X^{3}-X-1$ es irreductible sobre $\mathrm {GF} (2)$ y $\mathrm {GF} (3)$ , es decir, es irreducible módulo $2$ y $3$ (para demostrar esto, basta con demostrar que no tiene raíz en $\mathrm {GF} (2)$ ni en $\mathrm {GF} (3)$ , como si un factor cúbico entonces debe contener un factor lineal). De ello se deduce que los elementos de $\mathrm {GF} (8)$ y $\mathrm {GF} (27)$ pueden representarse mediante expresiones $a+b\alpha +c\alpha ^{2},$ dónde $a,b,c$ son elementos de $\mathrm {GF} (2)$ o $\mathrm {GF} (3)$ (respectivamente), y $\alpha$ es un símbolo tal que $\alpha ^{3}=\alpha +1.$

La suma, el inverso aditivo y la multiplicación en $\mathrm {GF} (8)$ y $\mathrm {GF} (27)$ puede definirse así de la siguiente manera; en las siguientes fórmulas, las operaciones entre elementos de $\mathrm {GF} (2)$ o $\mathrm {GF} (3)$ , representadas por letras latinas, son las operaciones en $\mathrm {GF} (2)$ o $\mathrm {GF} (3)$ , respectivamente: ${\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}}$

GF(16)

El polinomio $X^{4}+X+1$ es irreductible sobre $\mathrm {GF} (2)$ , es decir, es irreducible módulo $2$ . De ello se deduce que los elementos de $\mathrm {GF} (16)$ pueden representarse mediante expresiones $a+b\alpha +c\alpha ^{2}+d\alpha ^{3},$ dónde $a,b,c,d$ son o $0$ o $1$ (elementos de $\mathrm {GF} (2)$ ), y $\alpha$ es un símbolo tal que $\alpha ^{4}=\alpha +1$ (eso es, $\alpha$ se define como una raíz del polinomio irreducible dado). Como característica de $\mathrm {GF} (2)$ es $2$ , cada elemento es su inverso aditivo en $\mathrm {GF} (16)$ La suma y la multiplicación en $\mathrm {GF} (16)$ puede definirse de la siguiente manera; en las siguientes fórmulas, las operaciones entre elementos de $\mathrm {GF} (2)$ , representadas por letras latinas son las operaciones en $\mathrm {GF} (2)$ . ${\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 $\mathrm {GF} (16)$ tiene ocho elementos primitivos (los elementos que tienen todos los elementos distintos de cero de $\mathrm {GF} (16)$ como potencias enteras). Estos elementos son las cuatro raíces de $X^{4}+X+1$ y sus inversos multiplicativos . En particular, $\alpha$ es un elemento primitivo, y los elementos primitivos son $\alpha ^{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 $\mathrm {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$ de tal manera que $x^{k}=1$ por cada valor distinto de cero $x$ en $\mathrm {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 no nulos son potencias de un único elemento. En resumen:

El grupo multiplicativo de los elementos no nulos en $\mathrm {GF} (q)$ es cíclico, es decir, existe un elemento $a$ , de tal manera que el $q-1$ elementos distintos de cero de $\mathrm {GF} (q)$ son $a,a^{2},\ldots ,a^{q-2},a^{q-1}=1$ .

tal elemento $a$ se denomina un elemento primitivo de $\mathrm {GF} (q)$ . A menos que $q=2,3$ , el elemento primitivo no es único. El número de elementos primitivos es $\phi (q-1)$ dónde $\phi$ es la función totiente de Euler .

El resultado anterior implica que $x^{q}=x$ por cada $x$ en $\mathrm {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 $\mathrm {GF} (q)$ , entonces para cualquier elemento distinto de cero $x$ en $F$ , hay un número entero único $n$ con $0\leq n\leq q-2$ de tal manera que $x=a^{n}$ Este número entero $n$ se denomina logaritmo discreto de $x$ a la base $a$ .

Mientras $a^{n}$ Aunque se puede calcular muy rápidamente, por ejemplo mediante la exponenciación por elevación al cuadrado , no se conoce ningún algoritmo eficiente para calcular la operación inversa, el logaritmo discreto. Este se ha utilizado en diversos protocolos criptográficos ; consulte Logaritmo discreto para obtener más detalles.

Cuando los elementos distintos de cero de $\mathrm {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^{n}$ La identidad $a^{m}+a^{n}=a^{n}\left(a^{m-n}+1\right)$ permite resolver este problema mediante la construcción de la tabla de los logaritmos discretos de $a^{n}+1$ , llamados logaritmos de Zech , para $n=0,\ldots ,q-2$ (es conveniente definir el logaritmo discreto de cero como $-\infty$ ).

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

Raíces de la unidad

Todo elemento no nulo de un cuerpo finito es una raíz de la unidad , como $x^{q-1}=1$ para cada elemento distinto de cero de $\mathrm {GF} (q)$ .

Si $n$ es un número entero positivo, un $n$ La raíz primitiva de la unidad es una solución de la ecuación. $x^{n}=1$ Esa no es una solución de la ecuación. $x^{m}=1$ para cualquier entero positivo $m<n$ . Si $a$ es un $n$ la raíz primitiva de la unidad en un campo $F$ , entonces $F$ contiene todo el $n$ raíces de unidad, que son $1,a,a^{2},\ldots ,a^{n-1}$ .

El campo $\mathrm {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 primitivos $n$ las raíces de la unidad en $\mathrm {GF} (q)$ es $\phi (n)$ ( Función totiente de Euler ). El número de $n$ las raíces de la unidad en $\mathrm {GF} (q)$ es $\mathrm {gcd} (n,q-1)$ .

En un campo de características $p$ , el endomorfismo de Frobenius $\varphi (x)=x^{p}$ es inyectivo. Si $x^{np}=1$ entonces $\varphi (x^{n})=x^{np}=1=\varphi (1)$ por inyectividad $x^{n}=1$ . Este programa muestra que cada $np$ La raíz de la unidad también es una $n$ raíz de la unidad. De ello se deduce que primitivo $np$ Las raíces de la unidad nunca existen en un campo de características $p$ .

Por otro lado, si $n$ es coprimo con $p$ , las raíces de la $n$ Los polinomios ciclotómicos son distintos en cada campo de características. $p$ , ya que este polinomio es un divisor de $X^{n}-1$ , cuyo discriminante $n^{n}$ es distinto de cero módulo $p$ . De ello se deduce que el $n$ factores polinómicos ciclotómicos sobre $\mathrm {GF} (q)$ en polinomios irreducibles distintos que tengan todos el mismo grado, por ejemplo $d$ y que $\mathrm {GF} (p^{d})$ es el campo más pequeño de características $p$ que contiene el $n$ las raíces primitivas de la unidad.

Al calcular los caracteres de Brauer , se utiliza el mapa $\alpha ^{k}\mapsto \exp(2\pi ik/(q-1))$ para mapear los valores propios de una matriz de representación a los números complejos. Bajo este mapeo, el subcampo base $\mathrm {GF} (p)$ Consiste en puntos espaciados uniformemente alrededor del círculo unitario (omitiendo el cero).

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 los elementos primitivos no son 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)$ mismo. 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 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 polinomios$ mónicos irreducibles de grado $6.$ Esto puede verificarse factorizando $X 64 - X$ sobre $GF(2)$ .

Los elementos de $GF(64)$ son raíces primitivas $n-$ ésimas de la unidad para algún $n que$ divide a $63.$ Como la tercera y la séptima raíz de la unidad pertenecen a $GF(4)$ y $GF(8)$ , respectivamente, los $54$ generadores son raíces primitivas $n$ -ésimas de la unidad para algún $n$ en ${9, 21, 63}$ . La función totiente de Euler muestra que hay $6$ raíces primitivas $9$ -ésimas de la unidad, $12$ raíces primitivas $21$ -ésimas de la unidad y $36$ raíces primitivas $63$ -ésimas de la unidad. Sumando estos números, se obtienen nuevamente $54$ elementos.

Al factorizar los polinomios ciclotómicos sobre $\mathrm {GF} (2)$ Se observa que:

Los seis primitivos $9$ Las raíces de la unidad son raíces de $X^{6}+X^{3}+1,$ y todos son conjugados bajo la acción del grupo de Galois.
Los doce primitivos $21$ Las raíces de la unidad son raíces de $(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.
El $36$ elementos primitivos de $\mathrm {GF} (64)$ son las raíces de ${\begin{aligned}&(X^{6}+X^{4}+X^{3}+X+1)(X^{6}+X+1)(X^{6}+X^{5}+1)\cdot {}\\&\qquad (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).\end{aligned}}$ Bajo la acción del grupo de Galois, se dividen en seis órbitas de seis elementos cada una.

Esto demuestra que la mejor opción para construir $\mathrm {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 sencilla.

Automorfismo de Frobenius y teoría de Galois

En esta sección, $p$ es un número primo y $q=p^{n}$ es un poder de $p$ .

En $\mathrm {GF} (q)$ , la identidad $(x + y) p = x p + y p$ implica que el mapa $\varphi :x\mapsto x^{p}$ es un $\mathrm {GF} (p)$ - endomorfismo lineal y un automorfismo de campo de $\mathrm {GF} (q)$ , que fija cada elemento del subcampo $\mathrm {GF} (p)$ Se denomina automorfismo de Frobenius , en honor a Ferdinand Georg Frobenius .

Denotando por $φ k$ la composición de $φ$ consigo misma $k$ veces, tenemos $\varphi ^{k}:x\mapsto x^{p^{k}}.$ Se ha demostrado en la sección anterior que $φ n$ es la identidad. Para $0 < k < n$ , el automorfismo $φ k$ no es la identidad, ya que, de otro modo, el polinomio $X^{p^{k}}-X$ tendría más que raíces $p k .$

No existen otros automorfismos $GF(p)$ de $GF(q)$ . En otras palabras, $GF(p n)$ tiene exactamente $n$ $automorfismos GF(p)$ , que son: $\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 n)$ es una extensión de Galois de $GF(p)$ , que tiene un grupo de Galois cíclico .

El hecho de que la aplicación de Frobenius sea sobreyectiva implica que todo cuerpo finito es perfecto .

Factorización polinómica

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 todo anillo de polinomios sobre un cuerpo es un dominio de factorización único , todo polinomio mónico sobre un cuerpo finito puede factorizarse de forma única (hasta el orden de los factores) en un producto de polinomios mónicos irreducibles.

Existen algoritmos eficientes para comprobar la irreducibilidad de polinomios y factorizarlos sobre cuerpos finitos. Estos algoritmos son un paso fundamental para factorizar polinomios sobre los números enteros o racionales . Por esta razón, todos los sistemas de álgebra computacional cuentan con funciones para factorizar polinomios sobre cuerpos finitos o, al menos, sobre cuerpos primos finitos.

Polinomios irreducibles de un grado dado

El polinomio $X^{q}-X$ factoriza en factores lineales sobre un cuerpo de orden $q$ . Más precisamente, este polinomio es el producto de todos los polinomios mónicos de grado uno sobre un cuerpo de orden $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 cuerpo de descomposición está contenido en $GF(p n)$ . Recíprocamente, si $P$ es un polinomio mónico irreducible sobre $GF(p)$ de grado $d$ que divide $a n$ , define una extensión de cuerpo de grado $d$ , que está contenida en $GF(p n)$ , 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 a $X q - X$ . Como $X q - X$ no tiene ningún factor múltiple, es por lo tanto 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)$ ; véase Factorización de grado distinto .

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

El número $N (q, n)$ de polinomios irreducibles mónicos de grado $n$ sobre $GF(q)$ viene dado por ^{[ 7 ]} $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 una consecuencia inmediata de la propiedad de $X q - X$ anterior y de la fó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 $N(q,n)\geq {\frac {1}{n}}{\biggl (}q^{n}-\sum _{\ell \mid n,\ \ell {\text{ prime}}}q^{n/\ell }{\biggr )};$ Esto es preciso si y solo si $n$ es una potencia de algún número primo. Para cada $q$ y cada $n$ , el lado derecho es positivo, por lo que hay al menos un polinomio irreducible de grado $n$ sobre $GF(q)$ .

Cierre algebraico

Un campo finito $F$ no es algebraicamente cerrado: el polinomio $f(T)=1+\prod _{\alpha \in F}(T-\alpha ),$ no tiene raíces en $F$ , ya que $f (α) = 1$ para todo $\alpha$ en $F$ .

Dado un número primo $p$ , sea ${\overline {\mathbb {F} }}_{p}$ ser un cierre algebraico de $\mathbb {F} _{p}$ Es único salvo isomorfismo, como ocurre con el cierre algebraico de cualquier cuerpo dado. Los polinomios de Conway se pueden utilizar para construir un cierre algebraico explícito de $\mathbb {F} _{p}$ .

Para $n\geq 1$ , dejar $\mathbb {F} _{p^{n}}$ ser el conjunto de raíces de $x^{p^{n}}-x$ en ${\overline {\mathbb {F} }}_{p}$ ; es la extensión de grado $n$ única de $\mathbb {F} _{p}$ contenido en ${\overline {\mathbb {F} }}_{p}$ Cualquier cuerpo finito de característica $p$ es isomorfo a $\mathbb {F} _{p^{n}}$ para algunos $n\geq 1$ .

Cualquier extensión algebraica es la unión de sus subextensiones finitas, por lo tanto ${\overline {\mathbb {F} }}_{p}=\bigcup _{n\geq 1}\mathbb {F} _{p^{n}}.$ Uno tiene $\mathbb {F} _{p^{m}}\subseteq \mathbb {F} _{p^{n}}$ si y solo si $m|n$ , por lo que esta unión también puede verse como un límite directo de campos indexados por el conjunto de enteros positivos parcialmente ordenados por divisibilidad.

Un cierre algebraico de un cuerpo sirve también como cierre algebraico de cualquier subextensión finita, por lo que ${\overline {\mathbb {F} }}_{p}$ es también un cierre algebraico de $\mathbb {F} _{p^{n}}$ para cada $n\geq 1$ La extensión $\mathbb {F} _{p^{n}}/\mathbb {F} _{p}$ es normal (incluso Galois, incluso cíclico), por lo que se conserva mediante cualquier elemento del grupo de Galois. $\operatorname {Gal} ({\overline {\mathbb {F} }}_{p}/\mathbb {F} _{p})$ .

Aplicaciones

En criptografía , la dificultad del problema del logaritmo discreto en un campo finito o en una curva elíptica sobre un campo finito es la base de varios protocolos ampliamente utilizados, como el protocolo Diffie-Hellman . Por ejemplo, en 2014, una conexión segura a internet con Wikipedia implicó el protocolo Diffie-Hellman de curva elíptica ( ECDHE ) sobre un campo finito grande. ^{[ 8 ]} En teoría de códigos , 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 una característica de $2$ , ya que los datos informáticos se almacenan en binario. Por ejemplo, un byte de datos puede interpretarse como un elemento de $GF(2 8)$ . 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 característica $2$ , generalmente variaciones del producto sin acarreo .

Los cuerpos finitos se utilizan ampliamente en la teoría de números , ya que muchos problemas sobre los 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 cuerpo de los números racionales proceden mediante la reducción módulo 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 algunos o todos los números primos. Véase, por ejemplo, el principio de Hasse . Muchos desarrollos recientes de la geometría algebraica se vieron 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 numerosas herramientas matemáticas, incluyendo cuerpos finitos.

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

Los cuerpos finitos tienen una amplia aplicación en combinatoria , siendo dos ejemplos bien conocidos la definición de grafos de Paley y la construcción relacionada de matrices de Hadamard . En combinatoria aritmética, los cuerpos finitos ^{[ 9 ]} y los modelos de cuerpos finitos ^{[ 10 ]}^{[ 11 ]} se utilizan extensamente, como en el teorema de Szemerédi sobre progresiones aritméticas.

Generalizaciones

Si se debilitan los axiomas de campo eliminando la conmutatividad de la multiplicación, e incluso relajando la asociatividad a la alternancia , no se obtienen nuevas estructuras finitas:

El pequeño teorema de Wedderburn afirma que todos los anillos de división finitos son conmutativos y, por lo tanto, son cuerpos finitos. ^{[ 1 ]}
El teorema de Artin-Zorn establece que todos los anillos de división alternativos son cuerpos finitos. ^{[ 12 ]}

Véase también

Notas

1 2 3 4 5 6 7 8 9 Dummit, David Steven; Foote, Richard M. (2004). Álgebra abstracta (3.ª ed.). Hoboken, NJ: Wiley. ISBN 978-0-471-43334-7.
1 2 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 el marco de la Exposición Mundial Colombina , Macmillan & Co., pp . 208–242
↑ Esta última notación fue introducida por EH Moore en un discurso pronunciado en 1893 en el Congreso Matemático Internacional celebrado en Chicago Mullen & Panario 2013 , p. 10 .
↑ Aluffi, Paolo (2009). Álgebra: Capítulo 0. Sociedad Matemática Americana. pág. 439. ISBN 978-0-8218-4781-7.
↑ Xiang-dong Hou (2018), Lecciones sobre campos finitos , Estudios de posgrado en matemáticas, Providence, Rhode Island: American Mathematical Society , pág. 2
↑ Curvas elípticas recomendadas para uso gubernamental (PDF) , Instituto Nacional de Estándares y Tecnología , julio de 1999, pág. 3, archivado (PDF) del original el 19 de julio de 2008.
↑ Jacobson 2009 , §4.13
↑ En la mayoría de los navegadores, esto se puede verificar consultando la información de seguridad disponible al hacer clic en el icono del candado que aparece junto a la URL. En 2025, el certificado digital de Wikipedia aún menciona que se utilizan "curvas elípticas" para el algoritmo criptográfico.
↑ Shparlinski, Igor E. (2013), "Combinatoria aditiva sobre campos finitos: nuevos resultados y aplicaciones", Campos finitos y sus aplicaciones , DE GRUYTER, pp. 233–272 , doi : 10.1515/9783110283600.233 , ISBN 9783110283600
↑ Green, Ben (2005), "Modelos de campos finitos en combinatoria aditiva", Surveys in Combinatorics 2005 , Cambridge University Press, pp. 1–28 , arXiv : math/0409420 , doi : 10.1017/cbo9780511734885.002 , ISBN 9780511734885, S2CID 28297089
↑ Wolf, J. (marzo de 2015). "Modelos de campos finitos en combinatoria aritmética: diez años después" . Finite Fields and Their Applications . 32 : 233–274 . doi : 10.1016/j.ffa.2014.11.003 . hdl : 1983/d340f853-0584-49c8-a463-ea16ee51ce0f . ISSN 1071-5797 .
↑ Shult, Ernest E. (2011). Puntos y líneas. Caracterización de las geometrías clásicas . Universitext. Berlín: Springer-Verlag . pág. 123. ISBN 978-3-642-15626-7. Zbl 1213.51001 .

Referencias

Bussey, WH (1905), "Tablas de campos de Galois para p ⁿ ≤ 169 ", Bulletin of the American Mathematical Society , 12 (1): 22– 38, doi : 10.1090/S0002-9904-1905-01284-2
Bussey, WH (1910), "Tablas de campos de Galois de orden < 1000", Boletín de la Sociedad Matemática Americana , 16 (4): 188– 206, doi : 10.1090/S0002-9904-1910-01888-7
Jacobson, Nathan (2009) [1985], Álgebra básica I (Segunda edición), Dover Publications, ISBN 978-0-486-47189-1
Mullen, Gary L.; Mummert, Carl (2007), Campos finitos y aplicaciones I , Student Mathematical Library (AMS), ISBN 978-0-8218-4418-2
Mullen, Gary L.; Panario, Daniel (2013), Handbook of Finite Fields , 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 la investigación de Wolfram.
Campos finitos y sus aplicaciones , Science Direct, (Revista de acceso abierto).

[:0-1] 1 2 3 4 5 6 7 8 9 Dummit, David Steven; Foote, Richard M. (2004). Álgebra abstracta (3.ª ed.). Hoboken, NJ: Wiley. ISBN 978-0-471-43334-7.

[moore-2] 1 2 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 el marco de la Exposición Mundial Colombina , Macmillan & Co., pp . 208–242

[3] Esta última notación fue introducida por EH Moore en un discurso pronunciado en 1893 en el Congreso Matemático Internacional celebrado en Chicago Mullen & Panario 2013 , p. 10 .

[4] Aluffi, Paolo (2009). Álgebra: Capítulo 0. Sociedad Matemática Americana. pág. 439. ISBN 978-0-8218-4781-7.

[5] Xiang-dong Hou (2018), Lecciones sobre campos finitos , Estudios de posgrado en matemáticas, Providence, Rhode Island: American Mathematical Society , pág. 2

[6] Curvas elípticas recomendadas para uso gubernamental (PDF) , Instituto Nacional de Estándares y Tecnología , julio de 1999, pág. 3, archivado (PDF) del original el 19 de julio de 2008.

[7] Jacobson 2009 , §4.13

[8] En la mayoría de los navegadores, esto se puede verificar consultando la información de seguridad disponible al hacer clic en el icono del candado que aparece junto a la URL. En 2025, el certificado digital de Wikipedia aún menciona que se utilizan "curvas elípticas" para el algoritmo criptográfico.

[9] Shparlinski, Igor E. (2013), "Combinatoria aditiva sobre campos finitos: nuevos resultados y aplicaciones", Campos finitos y sus aplicaciones , DE GRUYTER, pp. 233–272 , doi : 10.1515/9783110283600.233 , ISBN 9783110283600

[10] Green, Ben (2005), "Modelos de campos finitos en combinatoria aditiva", Surveys in Combinatorics 2005 , Cambridge University Press, pp. 1–28 , arXiv : math/0409420 , doi : 10.1017/cbo9780511734885.002 , ISBN 9780511734885, S2CID 28297089

[11] Wolf, J. (marzo de 2015). "Modelos de campos finitos en combinatoria aritmética: diez años después" . Finite Fields and Their Applications . 32 : 233–274 . doi : 10.1016/j.ffa.2014.11.003 . hdl : 1983/d340f853-0584-49c8-a463-ea16ee51ce0f . ISSN 1071-5797 .

[12] Shult, Ernest E. (2011). Puntos y líneas. Caracterización de las geometrías clásicas . Universitext. Berlín: Springer-Verlag . pág. 123. ISBN 978-3-642-15626-7. Zbl 1213.51001 .

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]