Cos finit

Els defectes de cremat, el desgast i la pols que s'observen en la superfície d'un disc compacte requerixen una codificació redundante de l'informació que permet corregir els errors de llectura. Este còdic de correcció d'errors utilisa còdics de Reed-Solomon sobre el cos finito de ___*$256=2^8$ elementos.

En matemáticas y, más precisamente, en álgebra abstracta, un cuerpo finito, campo finito o campo de Galois (llamado así por Évariste Galois) es un cuerpo con un número finito d'elementos. Salvo isomorfisme, un cuerpo finito está unívocamente determinado por su cardinal, que siempre es una potencia d'un número primo. d'hecho, este misme número primo es su característica. per a todo número primo $p$ y todo entero positiu no nulo $n$ existe un cuerpo de cardinal $p^n$, que se presenta como la única extensión de grado $n$ del cuerpo $\mathbb{Z}/p\mathbb{Z}$. els cuerpos finitos són importantes en teoría de números, geometría algebraica, teoría de Galois, y criptografía. En teoría de números algebraicos aparecen como una estructura esencial en la geometría aritmética. Esta rama ha permitido, entre atres cosas, demostrar l'último teorema de Fermat. els cuerpos finitos han encontrado nuevas aplicaciones con el desarrollo de l'informática. En teoría de códigos, permiten, por ejemplo, determinar códigos correctores eficaces. Aparecen también en criptografía, dentro de la creación de cifrados de clave secreta como el estándar AES, así como en la de cifrados de clave pública, a través de, entre atres, el problema del logaritme discreto. els cuerpos finitos se llaman también en ocasiones cuerpos de Galois o más raramente campos de Galois. Esto se debe a que fueron estudiados por Évariste Galois en un artículo publicado en 1830, que es cuando se originó la teoría. d'hecho, Carl Friedrich Gauss ya había descubierto els resultados de Galois a finals del XVIII, pero no els publicó; sus trabajos no fueron conocidos fins despuix de su muerte y tuvieron la influencia dels de Galois. El cuerpo finito de cardinal $q$ (necesariamente una potencia d'un número primo) se denota como ${𝔽}_q$ (del inglés field, que significa cuerpo conmutatiu) o $\mathrm{GF}(q)$ (de l'anglés Galois field).

Construcció cossos finitos

La ferramenta que permet la construcció de cossos finitos és la relació de congruència, congruència de número entero en el cas de cossos finitos de cardinal primer, o congruència de polinomis en coeficients sobre un cos finito cosí en el cas general (potències de número primo).

El cos més chicotet

El cos finito més chicotet es denota per ___*${𝔽}_2$. Consta de dos elementos distintos: $0$, que es l'elemento neutro de la adición, y $1$, que es el elemento neutro de la multiplicación. Esto determina les tablas de les dos operaciones excepto $1+1$, que tiene que ser $0$, pues $1$ debe tener un elemento opuesto (en este caso será el misme $1$). Verificamos que definen bien un cuerpo que es, d'hecho, conmutatiu.

+ 0 1 0 0 1 1 1 0

· 0 1 0 0 0 1 0 1

El cuerpo ${𝔽}_2$ se puede interpretar de diversas maneras. Es l'anillo $\mathbb{Z}/2\mathbb{Z}$, els enteros tomados módulo 2; es decir, que 0 representa els enteros pares, 1 els enteros impares y les operaciones se deducen de les de $\mathbb{Z}$. Es también el conjunto de valores de verdad clásicos: 0 per a falso y 1 per a verdadero. La adición es el "o exclusivo" y la multiplicación, el "y". les apliaciones de ${\left({𝔽}_2\right)}^n$ en ${𝔽}_2$ se llaman funciones booleanas en honor a George Boole. La disjunción (inclusiva) y la negación se definen respectivamente como:

$\vee :{\left({𝔽}_2\right)}^2⟶{𝔽}_2;(x,y)⟼x\vee y:=x+y+xy$

$\mathrm{\neg }:{𝔽}_2⟶{𝔽}_2;x⟼\mathrm{\neg }x:=1+x$

Més generalment es deduïx del teorema d'interpolació de Lagrange que totes les funcions booleanas són polinòmiques (és de fet una propietat que s'hereta a qualsevol cos finito).

Artícul principal → Funció booleana.

Cossos finitos cosins

Una generalisació natural de ___*${𝔽}_2=\mathbb{Z}/2\mathbb{Z}$ es, per a $p$ primo, el cuerpo $\mathbb{Z}/p\mathbb{Z}$, que se denota igualmente ${𝔽}_p$.

Proposición: l'anillo $\mathbb{Z}/p\mathbb{Z}$ es un cuerpo si y sólo si $p$ es un número primo.

En efecto, que $p$ sea primo equivale a que 0 no sea producto de dos enteros no nulos módulo $p$, por el lema d'Euclides. Es necesario pues que $p$ sea primo per a que $\mathbb{Z}/p\mathbb{Z}$ sea un cuerpo, porque si no habría divisores de cero. Además, si $p$ es primo, $\mathbb{Z}/p\mathbb{Z}$ es un anillo íntegro y por tanto, como es finito, es un cuerpo. l'identidad de Bézout asegura directamente la existencia d'un inverso $s$ per a todos els elementos, y un cálculo eficaz del misme mediante l'algoritmo d'Euclides extendido: $\mathrm{mcd}(a,p)\stackrel{p\text{ primo}}{=}1\stackrel{\text{Bézout}}{\Rightarrow }\mathrm{\exists }s,t\in \mathbb{Z}:as+pt=1\Rightarrow as=1modp\Rightarrow s=a^{-1}\text{ en }\mathbb{Z}/p\mathbb{Z}$

Por tanto, también es suficiente. $◻$

Así podemos construir cuerpos finitos con cardinalidad cualquier número primo. El grupo multiplicatiu de $\mathbb{Z}/p\mathbb{Z}$ (con $p$ primo) es d'orden $p-1$, lo que conduïx al chicoteta teorema de Fermat per mig del teorema de Lagrange. Ademés, este grup és cíclico, com es demostra més alvance en un cas més general.

Cocient per un polinomi irreducible

Per a construir nous cossos finitos, utilisem l'estructura d'anell euclideo de ___*${𝔽}_p[x]$ (por ser ${𝔽}_p$ un cuerpo, como hemos visto en el párrafo anterior) de la misma forma que hemos utilizado la de $\mathbb{Z}$ per a construir els cuerpos finitos primos. els polinomios irreducibles juegan aquí el papel dels números primos allí. Dos polinomios són equivalentes módulo un polinomio $P$ si se obté el misme resto per a al hacer la división por $P$. El cociente por esta relació d'equivalencia se denota ${𝔽}_p[x]/(P)$ y la estructura inducida por el cociente es también la d'anillo. De manera totalmente anàloga al caso anterior tenemos que:

Proposición: El anillo ${𝔽}_p[x]/(P)$ es un cuerpo si y sólo si $P$ es un polinomio irreducible.$◻$

Sea $n$ el grado de $P$. Tomando un polinomio cualquiera de ${𝔽}_p[x]$, al dividirlo por $P$, obtenemos un único resto de grado $<n$. Por tanto, per a cada clase d'equivalencia por la relació antes descrita se puede tomar un único representante de grado $<n$ y, así, cada elemento de ${𝔽}_p[x]/(P)$ puede ser representado por un único polinomio de grado $<n$. El cardinal de ${𝔽}_p[x]/(P)$ es por tanto el número de polinomios de ${𝔽}_p[x]$ de grado $<n$. Como hay $n$ coeficientes que determinar, cada uno en ${𝔽}_p$, y ${𝔽}_p$ tiene $p$ elementos, el cardinal de ${𝔽}_p[x]/(P)$ es $p^n$. per a construir un cuerpo finito de cardinal $p^n$ es suficiente, por tanto, encontrar un polinomio irreducible de grado $n$ en ${𝔽}_p[x]$.

Eixemple: els cossos en ___*$p^2$ elements

Podem, pel paràgraf anterior, construir cossos en ___*$p^2$ elementos demostrando que existe un polinomio irreducible $P$ de grado $2$ en ${𝔽}_p[x]$. El cuerpo ${𝔽}_p[x]/(P)$ tiene entonces $p^2$ y es una extensión cuadrática de ${𝔽}_p$. Se verá más adelante que el cuerpo con $p^2$ elementos es único salvo isomorfisme y se denotará ${𝔽}_{p^2}$. En particular, el cuerpo que vamos a construir es independiente de la elecció del polinomio irreducible $P$ de grado $2$ per al cociente. Esta extensión cuadrática de ${𝔽}_p$ es la anàloga de la (única) extensión cuadrática del cuerpo dels números reals, que da lugar a els números complejos.

• per a $p=2$, el polinomio $1+x+x^2$ es irreducible en ${𝔽}_2[x]$. La extensión correspondiente es un cuerpo ${𝔽}_4:={𝔽}_2[x]/(1+x+x^2)$ con cuatro elementos: 0, 1 y les dos raíces $\phi$ y ${\phi }^2=\phi +1$ de $1+x+x^2$. Sus tablas són, por tanto:

+ 0 1 φ φ² 0 0 1 φ φ² 1 1 0 φ² φ φ φ φ² 0 1 φ² φ² φ 1 0

• 0 1 φ φ² 0   0   0 0 0 1 0 1 φ φ² φ 0 φ φ² 1 φ² 0 φ² 1 φ

• Cuando $p$ es impar, un polinomio de la forma $x^2-a$ es irreducible si y sólo si $a$ no es un cuadrado. Además, per a $p$ diferente de 2, existen en ${𝔽}_p$ elementos no cuadrados. En efecto, els cuadrados dels $p-1$ elementos no nulos de ${𝔽}_p$ són exactamente $\frac{p-1}{2}$, pues cada cuadrado no nulos es el cuadrado d'exactamente dos elementos, uno el opuesto del atre. Por tanto, quedan atres $\frac{p-1}{2}$ no cuadrados, entre els cuals se puede tomar $a$. Así, siempre se podrá tomar el polinomio irreducible deseado y construir el cuerpo de $p^2$ elements.

Classificació

Ya que tot cos de característica 0 conté als racionals i és per lo tant infinit, tots els cossos finitos tenen característica p primera. Per lo tant, el seu tamany (o cardinalidad) és de la forma pⁿ, per a algun sancer positiu n > 0 (puix el cos és un espai vectorial sobre el subcuerpo de cardinalidad p generat per l'element 1). No obstant, no és cert en general que tot cos de característica primera siga finito. Per a tot primer p, els sancers mòdul p formen un cos de p elements, denotat per Z/pZ (puix la seua grup aditiu és isomorfo al grup cíclico de p elements), F_p, o GF(p); en alguns casos s'usa Z_p, encara que esta notació és evitada per teoristas dels números, puix pot crear confusió en l'anell dels números p-ádicos. Tot cos en p elements és isomorfo a est. Si q = pⁿ és una potencia d'un cosí, existix (llevat isomorfisme) exactament un cos en q elements, en concret, el cos de descomposició de ___*$x^{p^n}-x$ sobre $𝐙/p𝐙$. Dit cos es denota per F_q, F[pⁿ] o GF(pⁿ) i es pot construir de la següent manera:

• es pren un polinomi irreducible f(X) de grau n en coeficients en F_p,
• es definix F_q = F_p[X] / <f(X)>, a on
  • F_p[X] denota l'anell de tots els polinomis en coeficients en F_p,
  • <f(X)> denota l'ideal generat per f(X),
  • la barra diagonal indica que es pren l'anelle cocient (definit de forma similar al grup cocient). El polinomi f(X) es pot trobar factorizando X^q-X sobre F_p. El cos F_q conté una còpia de F_p com subcuerpo. No hi ha atres cos finitos.

Eixemples

Cos F[7]

Siga F[7] el conjunt dels sancers mòdul 7 baix l'adició i multiplicació mòdul 7. És dir, els elements de F[7] són les classes d'equivalència representades pels elements [0], [1], [2], [3], [4], [5] i [6] a on:

• [a] + [b] = [j], sent [j] el restant de la divisió de (a + b)/7 ( per eixemple [5] + [6] = [4], ya que 5+6=11, que dividit per 7, dona restant 4).
• [a] x [b] = [k] a on [k] és el restant de la divisió de (a x b)/7 (Per eixemple, [5] x [6] = [2], ya que 5 x 6 = 30 i 30 entre 7, dona com a restant 2). Es verifica que F[7] és un anell conmutatiu en element unitari [1]. Ademés es complix:
• [1] x [1] = [1] = [6] x [6].
• [2] x [4] = [1] = [4] x [2].
• [3] x [5] = [1] = [5] x [3]. Els elements de F[7] distints de zero formen un grup abeliano baix la multiplicació. F[7] és, puix, un camp. ya que té un número finito d'elements és un camp finito.

Aritmètica en F[7]

Cocient

Siguen a i b ≠ 0, elements de F'[7], direm que a÷b = c s. s. s. a = b×c

Com a eixemple 5÷3= 5×3^-1 =4, puix 3×4= 5.

Potència

1. Per a tot a≠0; a⁰ =1
2. a^h+1 = a^ha ; h està en ℤ

Eixemple 2²= 2¹×2 = 2×2 = 4

Raïl quadrada

siga a element de F'[7], direm que b, si existix, és la raïl quadrada de si a = b²

Eixemple ___*$\sqrt{2}=3\vee 4$, puix 3² = 2 o 4² = 2; només tenen sengles raïls 1, 2 i 4

Cos F[2²]

El cos F[2²] es construïx com l'anelle cocient entre l'anell de polinomis en coeficients en F[2] sobre l'ideal generat per un polinomi irreducible, per eixemple, f(x) = x² + x + 1.

$F[4]=F_2[X]/⟨x^2+x+1⟩$

El cuerpo F₄ puede representarse como el conjunto $\{0,1,\alpha ,\alpha +1\}$ donde la suma y la multiplicación quedan definidas considerando que ${\alpha }^2+\alpha +1=0$. Por ejemplo, per a hallar

$(\alpha )(\alpha +1)=({\alpha }^2+\alpha )=({\alpha }^2+\alpha +1)+1=1$ (ya que 1 + 1 = 0 en F₂)

per a encontrar un inverso multiplicatiu de $\alpha$ en este campo, se debe encontrar un polinomio $g(\alpha )$ tal que $\alpha \times g(\alpha )=1mod({\alpha }^2+\alpha +1)$; el polinomio $g(\alpha )=\alpha +1$ cumple esta propiedad, de modo que es el inverso de $\alpha$. Observe's que el camp F₄ no té relació en l'anell Z₄ de sancers mòdul 4.

Atres eixemples

Per a construir el camp F[3³], es comença en el polinomi irreducible (en F₃) x³ + x² + x - 1. Es té llavors

$F[3^3]=F_3[X]/⟨x^3+x^2+x-1⟩$

De modo equivalente, F[3³] = {ax² + bx + c | a, b, c ∈ F₃}, donde la multiplicación se define considerando que x³ + x² + x - 1 = 0. les matrices $A=\left(\begin{array}{cc}{a}_0& b_0\\ -b_0& a_0\end{array}\right)$ en a₀ i b₀ elements de Z₃ formen un camp de 9 elements, i el grup multiplicatiu d'este camp, és cíclico, d'orde 8. És per tant isomorfo a F[3²].

Propietats

• Tots els elements de ___*$F_q$ satisfacen la ecuación polinómica $x^q-x=0$.

Grup multiplicatiu

Donat un cos ___*$F_q$, su grupo multiplicatiu $F_q^{\times }$ es un grupo cíclico d'orden q-1.

Esto significa que si F es un campo finito de q elementos, siempre hay al menos un elemento x ∈ F tal que F = { 0, 1, x, x²,..., x^q-2 }. els elementos x que cumplen esta condició reciben el nombre d'elementos primitius y el número d'ellos viene dado por $\phi (q-1)$, donde $\phi$ és la funció indicatriz d'Euler. Donat un element primitiu x, llavors per a tot a ≠ 0 en F hi ha un únic n ∈ {0,..., q - 2} tal que a = xⁿ. El valor de n per a un dau a es diu logaritme discret de a en base x. En la pràctica, encara que calcular xⁿ és relativament trivial donat n, trobar n per a un a dau és un problema difícil, per lo que resulta d'interés en criptografia.

Subcuerpos

El cos ___*$F_q$ (donde q=p^m) contiene una copia de $F_{q^{\prime }}$ (donde q'=pⁿ) si y solo si n divide a m. En esta situación, $F_{q^{\prime }}$ es un subcuerpo de $F_q$, y $F_q$ es una extensión de $F_{q^{\prime }}$. La raó per a la direcció "si" és que hi ha polinomis irreducibles de qualsevol grau en F_p^m. Si es construïxen els camps finitos de forma tal que F_pⁿ estiga efectivament contingut en F_p^m sempre que n dividixca a m, es pot prendre l'unió de tots eixos camps; esta és també un camp de característica p, encara que infinit. És la clausura algebraica de cada u dels camps F_pⁿ. Encara si no es construïxen d'esta manera els camps, es pot parlar del seu clausura algebraica, encara que la seua construcció és ara més delicada.

Teorema de Wedderburn

La teorema de Wedderburn, en ocasions cridat chicotet teorema de Wedderburn per a distinguir-ho del teorema d'Artin-Wedderburn, establix que tot domini finito és un cos. Per tant, pel que fa als anells finitos, no hi ha distinció entre dominis, anells de divisió i cossos. Esta teorema és equivalent a afirmar que el grup de Brauer de tot cos finito és trivial. La teorema va ser demostrada per Joseph Wedderburn en 1905, lo que va supondre un alvanç en l'àmbit dels anells conmutatius.

Endomorfisme de Frobenius

La funció

$f:F_q\to F_q$

definida por

$f(x):=x^p$, donde $q=p^n$

és biyectiva i un endomorfisme, en lo que és un automorfisme de F. És un cas particular d'un tipo d'homomorfisme cridat endomorfisme de Frobenius, en honor a Ferdinand Georg Frobenius. El fet de que el mapa f siga sobreyectiu implica que tot camp finito és perfecte. L'automorfisme de Frobenius té orde n, i per lo tant el grup cíclico generat per est és el grup complet d'automorfismes del cos.

Els primers cossos finitos

F₂:

+ 0 1 0 0 1 1 1 0

× 0 1 0 0 0 1 0 1

F₃:

+ 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1

× 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1

F₄:

+ 0 1 α α+1 0 0 1 α α+1 1 1 0 α+1 α α α α+1 0 1 α+1 α+1 α 1 0

× 0 1 α α+1 0 0 0 0 0 1 0 1 α α+1 α 0 α α+1 1 α+1 0 α+1 1 α

Nota: ___*$F[4]=F_2[\alpha ]/⟨{\alpha }^2+\alpha +1⟩$

Vore també

• Teoria de cossos.
• Teoria d'anells.
• Anell de divisió.

Enllaços externs

Commons

• Wikimedia Commons alberga contingut multimèdia sobre Cos finit.
• Finite Field en MathWorld.