Cos finito

Archiu:Caps block 0 autolev crop new.jpg

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$ elements.

En matemàtiques i, més precisament, en àlgebra abstracta, un cos finito, camp finito o camp de Galois (cridat aixina per Évariste Galois) és un cos en un número finito d'elements. Llevat isomorfisme, un cos finito està unívocamente determinat pel seu cardinal, que sempre és una potència d'un número primo. De fet, este mateix número primo és el seu característica. Per a tot número primo $p$ i tot sancer positiu no nul $n$ existix un cos de cardinal $p^n$, que es presenta com l'única extensió de grau $n$ del cos $\mathbb{Z}/p\mathbb{Z}$.

Els cossos finitos són importants en teoria de números, geometria algebraica, teoria de Galois, i criptografia.

En teoria d'número algebraico apareixen com una estructura essencial en la geometria aritmètica. Esta branca ha permés, entre atres coses, demostrar l'última teorema de Fermat.

Els cossos finitos han trobat noves aplicacions en el desenroll de l'informàtica. En teoria de còdics, permeten, per eixemple, determinar còdics correctors eficaços. Apareixen també en criptografia, dins de la creació de sifrats de clau secreta com l'estàndart AES, aixina com en la de sifrats de clau pública, a través de, entre uns atres, el problema del logaritmo discret.

Els cossos finitos es diuen també en ocasions cossos de Galois o més rarament camps de Galois. Açò es deu a que varen ser estudiats per Évariste Galois en un artícul publicat en 1830, que és quan es va originar la teoria. De fet, Carl Friedrich Gauss ya havia descobert els resultats de Galois a finals de el XVIII, pero no els va publicar; els seus treballs no varen ser coneguts fins al cap de la seua mort i varen tindre l'influència dels de Galois.

El cos finito de cardinal $q$ (necessàriament una potència d'un número primo) es denota com ${𝔽}_q$ (de l'anglés field, que significa cos conmutativo) 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 d'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 d'número primo).

El cos més chicotet

El cos finito més chicotet es denota per ${𝔽}_2$. Consta de dos elements distints: $0$, que és l'element neutre de l'adició, i $1$, que és l'element neutre de la multiplicació. Açò determina les taules de les dos operacions llevat $1+1$, que té que ser $0$, puix $1$ deu tindre un element opost (en este cas serà el mateix $1$). Verifiquem que definixen be un cos que és, de fet, conmutativo.

+ 0 1 0 0 1 1 1 0

· 0 1 0 0 0 1 0 1

El cos ${𝔽}_2$ es pot interpretar de diverses maneres. És l'anell $\mathbb{Z}/2\mathbb{Z}$, els sancers presos mòdul 2; és dir, que 0 representa els sancers parells, 1 els sancers impars i les operacions es deduïxen de les de $\mathbb{Z}$.

És també el conjunt de valors de veres clàssics: 0 per a fals i 1 per a verdader. L'adició és el "o exclusiu" i la multiplicació, el "i".

Les apliaciones de ${\left({𝔽}_2\right)}^n$ en ${𝔽}_2$ es diuen funcions booleanas en honor a George Boole. La disjunción (inclusiva) i la negació es definixen respectivament com:

$\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}$ és, per a $p$ cosí, el cos $\mathbb{Z}/p\mathbb{Z}$, que es denota igualment ${𝔽}_p$.

Proposició: l'anell $\mathbb{Z}/p\mathbb{Z}$ és un cos si i només si $p$ és un número primo.

En efecte, que $p$ siga primer equival a que 0 no siga producte de dos sancers no nuls mòdul $p$, pel lema de Euclides. És necessari puix que $p$ siga primer per a que $\mathbb{Z}/p\mathbb{Z}$ siga un cos, perque si no hi hauria divisores de zero. Ademés, si $p$ és primer, $\mathbb{Z}/p\mathbb{Z}$ és un anelle íntegre i per tant, com és finito, és un cos. l'identitat de Bézout assegura directament l'existència d'un invers $s$ per a tots els elements, i un càlcul eficaç del mateix per mig del algoritme de Euclides estés: $\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}$

Per tant, també és suficient. $◻$

Aixina podem construir cossos finitos en cardinalidad qualsevol número primo.

El grup multiplicativo de $\mathbb{Z}/p\mathbb{Z}$ (en $p$ cosí) és d'orde $p-1$, lo que conduïx al menuda 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]$ (per ser ${𝔽}_p$ un cos, com hem vist en el paràgraf anterior) de la mateixa forma que hem utilisat la de $\mathbb{Z}$ per a construir els cossos finitos cosins. Els polinomis irreducibles juguen ací el paper dels número primo allí. Dos polinomis són equivalents mòdul un polinomi $P$ si s'obté el mateix restant para en fer la divisió per $P$. El cocient per esta relació d'equivalència es denota ${𝔽}_p[x]/(P)$ i l'estructura induïda pel cocient és també la d'anell.

De manera totalment anàloga al cas anterior tenim que:

Proposició: L'anell ${𝔽}_p[x]/(P)$ és un cos si i només si $P$ és un polinomi irreducible.$◻$

Siga $n$ el grau de $P$. Prenent un polinomi qualsevol de ${𝔽}_p[x]$, en dividir-ho per $P$, obtenim un únic restant de grau $<n$. Per tant, per a cada classe d'equivalència per la relació abans descrita es pot prendre un únic representant de grau $<n$ i, aixina, cada element de ${𝔽}_p[x]/(P)$ pot ser representat per un únic polinomi de grau $<n$. El cardinal de ${𝔽}_p[x]/(P)$ és per tant el número de polinomis de ${𝔽}_p[x]$ de grau $<n$. Com hi ha $n$ coeficients que determinar, cada u en ${𝔽}_p$, i ${𝔽}_p$ té $p$ elements, el cardinal de ${𝔽}_p[x]/(P)$ és $p^n$.

Per a construir un cos finito de cardinal $p^n$ és suficient, per tant, trobar un polinomi irreducible de grau $n$ en ${𝔽}_p[x]$.

Eixemple: els cossos en $p^2$ elements

Podem, pel paràgraf anterior, construir cossos en $p^2$ elements demostrant que existix un polinomi irreducible $P$ de grau $2$ en ${𝔽}_p[x]$. El cos ${𝔽}_p[x]/(P)$ té llavors $p^2$ i és una extensió quadràtica de ${𝔽}_p$. Es vorà més alvance que el cos en $p^2$ elements és únic llevat isomorfisme i es denotarà ${𝔽}_{p^2}$. En particular, el cos que anem a construir és independent de l'elecció del polinomi irreducible $P$ de grau $2$ per al cocient. Esta extensió quadràtica de ${𝔽}_p$ és l'anàloga de la (única) extensió quadràtica del cos dels número real, que dona lloc als número complejo.

• Per a $p=2$, el polinomi $1+x+x^2$ és irreducible en ${𝔽}_2[x]$. L'extensió corresponent és un cos ${𝔽}_4:={𝔽}_2[x]/(1+x+x^2)$ en quatre elements: 0, 1 i les dos raïls $\phi$ i ${\phi }^2=\phi +1$ de $1+x+x^2$. Les seues taules són, per tant:

+ 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 φ

• Quan $p$ és impar, un polinomi de la forma $x^2-a$ és irreducible si i només si $a$ no és un quadrat. Ademés, per a $p$ diferent de 2, existixen en ${𝔽}_p$ elements no quadrats. En efecte, els quadrats dels $p-1$ elements no nuls de ${𝔽}_p$ són exactament $\frac{p-1}{2}$, puix cada quadrat no nuls és el quadrat d'exactament dos elements, un l'opost de l'atre. Per tant, queden atres $\frac{p-1}{2}$ no quadrats, entre els quals es pot prendre $a$. Aixina, sempre es podrà prendre el polinomi irreducible desijat i construir el cos 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.

Vore també

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