Cuerpos Beamer

Ampliacion Matematica Discreta

Justo Peralta Lopez

U AıD A A M

Extensiones de Cuerpos

1 Introduccion

Ampliacion Matematica Discreta Extensiones de Cuerpos


Introduccion

Ejemplo

Sea f (x) = x2 + x + 1 sobre GF(2). Como se puede observar no tiene raıces en GF(2), perosi en la extension del cuerpo GF(22). Llamemos α a dicha raız. Luego f (α) = 0 = α2 +α+ 1,es decir, α2 = −α − 1 = α + 1 (GF(22) tiene caracterıstica 2). A esta ultima ecuacion lellamamos ecuacion caracterıstica. Luego GF(22) = {0, α0 = 1, α1 = α, α2 = α + 1}.Observese que GF(22)∗ es un grupo multiplicativo generado por α, lo cual simplifica labusqueda del inverso de cualquier elemento del cuerpo.



Introduccion

Ejemplo

Sea ahora f (x) = x2 + 2x + 2 un polinomio irreducible sobre GF(3). Sea α su raız enGF(32). Entonces

α0 = 1α1 = αα2 = 1 + αα3 = α(1 + α) = α + α + 1 = 2α + 1α4 = αα3 = 2α2 + α = 2(α + 1) + α = 2α + 2 + α = 2α5 = αα4 = 2αα6 = αα5 = 2 + 2αα7 = αα6 = α(2α + 2) = 2α2 + 2α = 2(α + 1) + 2α = 2α + 2 + 2α = α + 2α8 = αα7 = α2 + 2α = α + 1 + 2α = 1

Luego GF(32) = {0, 1, α, α2 = 1 + α, α3 = 2α + 1, α4 = 2, α5 = 2α, α6 = 2α + 2, α7 = α + 2}.Escrito de esta forma y teniendo en cuenta que α8 = 1, la busqueda de cualquier inversoes muy sencillo. Por ejemplo, el inverso de 2α + 2 = α6 es α2 = 1 + α. Ya queα6α2 = (2 + 2α)α2 = 2α2 + 2α3 = 2(1 + α) + 2(2α + 1) = 2 + 2α + 4α = 6α + 4 = 1



Introduccion

Definicion

Sea α una raız de f (x), un polinomio irreducible de grado m sobre GF(q). Si α generaGF(qm)∗, todos los elementos no nulos de GF(qm), entonces α es un elemento primitivo deGF(qm) y f (x) un polinomio primitivo.

Ejemplo

Sea f (x) = x2 + 1 irreducible en GF(3). Si α es su raız en GF(32), entoncesf (α) = 0 = α2 + 1 y la ecuacion caracterıstica es α2 = 2. El grupo cıclico generado por αviene dado por

< α >= {α, α2 = 2, α3 = 2α, α4 = 1}

Luego α no genera a GF(32)∗ y por lo tanto no es un elemento primitivo. Aun ası, elconjunto

S = {0, 1, 2, α, α + 1, α + 2, 2α, 2α + 1, 2α + 2}

bajo la adicion y multiplicacion modulo f (x) = α2 + 1, tiene la misma estructura que GF(32).



Introduccion

Ejemplo

SEa f (x) = x4 + x + 1 irreducible sobre F2[x], podemos construir el cuerpo GF(24). Sea αes la raız de f (x) en GF(2), los elementos de GF(24) viene dados por

Vector Polinomio Elemento0000 0 00001 1 10010 α α0100 α2 α2

1000 α3 α3

0011 α + 1 α4

0110 α2 + α α5

1100 α3 + α2 α6

1011 α3 + α + 1 α7

0101 α2 + 1 α8

1010 α3 + α α9

0111 α2 + α + 1 α10

1110 α3 + α2 + α α11

1111 α3 + α2 + α + 1 α12

1101 α3 + α2 + 1 α13

1001 α3 + 1 α14



Introduccion

Teorema

Sea β un elemento no nulo de un cuerpo de cardinal q, entonces βq−1 = 1.

Lema

Si α tiene orden r en un grupo multiplicativo, entonces αi tiene orden i/(r , i)

Teorema

El orden de un elemento no nulo de GF(q) es un divisor de q − 1.

Estos quiere decir que en un cuerpo finito de caracterıstica q, los elementos α y αq tienenel mismo orden.



Introduccion

Teorema

En todo cuerpo finito existe un elemento primitivo. Si α es un elemento primitivo de uncuerpo con caracterıstica q, entonces los elementos αq , αq2

, . . . , αqm−1tambien lo son.

Teorema (Fermat)

Si q es la caracterıstica de un cuerpo finito F, entonces todo elemento de F es raız de laecuacion xq = x y por lo tanto

xq − x =∏α∈F

(x − α)

Teorema

1 Todos los cuerpos finitos tienen tamano q = pn para algun primo p.

2 El cardinal de un subcuerpo de GF(pm) es ps , siendo s un divisor positivo de m.Recıprocamente, si s|m, entonces GF(ps ) ⊆ GF(pm)

3 Ademas, si α es un elemento primitivo de GF(pm), entonces β = αt ,t = (pm − 1)/(ps − 1), es un elemento primitivo de GF(ps ), y

GF(ps ) = {β ∈ GF(pm) : βps= β}



Introduccion

Definicion

Sea F un subcuerpo de C. El polinomio mınimo Mα(x) con α ∈ C sobre F es el polinomiomonico de menor grado con coeficientes en F que admite a α como raız.

Ejemplo

Polinomios primitivos de los elementos de GF(24) del ultimo ejemplo.

Elemento Polinomio Mınimo0 x1 1 + x

α, α2, α4, α8 x4 + x + 1α3, α6., α9, α12 x4 + x3 + x2 + x + 1α5, α10 x2 + x + 1

α7, α11, α13, α14 x4 + x3 + 1



Introduccion

Teorema

Sea GF(pm) una extension de GF(p), y sea α un elemento de GF(pm) con polinomiomınimo Mα(x) en Fp[x].

1 Mα(x) es irreducible y unico en Fp[x].

2 Si g(x) es un polinomio de Fp[x] y g(α) = 0, entonces Mα(x) divide a g(x).

3 Mα(x) divide a xpm− x.

4 El grado de Mα(x) es un divisor de m.

5 El polinomio mınimo de un elemento primitivo de GF(pm) es de grado m.

Definicion

El elemento polinomio mınimo de un elemento primitivo es un polinomio primitivo.



Introduccion

Teorema

Sean f (x) un polinomio con coeficientes en GF(q) y α una raız de f (x) en la extensionGF(qm).

1 αq es una raız de f (x) en GF(qm).

2 Si α tiene orden n y t es el orden multiplicativo de q modulo n, entonces α, α, . . . , αqt−1

son raıces distintas de f (x) en GF(qm).

Definicion

Al conjunto Ci = {i, iq, . . . , iqd−1} donde d es el menor entero tal que iqd−1 ≡n i es elconjunto q-ciclotomico de i modulo n.

Nota

Como se observa en el ultimo teorema, el polinomio mınimo con raız αi , tambientendra como raıces a los elementos del conjuntos

Aαi = {αi , αiq , . . . , αiqd−1}

cuyos exponentes son los asociados al conjunto q-ciclotomico de i modulo n, Ci . Y por lotanto el polinomio mınimo viene dado por el siguiente teorema.



Introduccion

Teorema

Sea GF(qs ) una extension de GF(q) y sea α una raız primitiva n-esima en GF(qs ).

1 El polinomio mınimo de αs sobre GF(q) es

Mαs (x) =∏i∈Ci

(x − αi )

siendo Ci el conjunto q-ciclotomico de i modulo n.

2 xpm− 1 =

∏j Mαj (x), donde j recorre todos los conjuntos ciclotomicos.



Introduccion

Ejemplo

GF(22), p(x) = x2 + x + 1

Elementos Conjuntos Ciclotomicos Polinomio Mınimo00 001 1 {0} x + 110 α {1, 2} x2 + x + 111 α2

Ejemplo

GF(23), p(x) = x3 + x + 1

Elementos: C. Ciclotomicos P. Mınimo000 0 011 α3

001 1 110 α4 {0} x + 1010 α 111 α5 {1, 2, 4} x3 + x + 1100 α2 101 α6 {3, 6, 5} x3 + x2 + 1



Introduccion

Ejemplo

GF(24), p(x) = x4 + x + 1

Elementos C.Ciclotomicos P.Mınimo0000 0 1011 α7

0001 1 0101 α8

0010 α 1010 α9 {0} x + 10100 α2 0111 αlO {1, 2, 4, 8} x4 + x + 11000 α3 1110 αll {3, 6, 12, 9} x4 + x3 + x2 + x + 10011 α4 1111 αl2 {5, lO} x2 + x + 10110 α5 1101 αl3 {7, 14, 13, 11} x4 + x3 + 11100 α6 1001 αl4



Introduccion

Ejemplo

GF(25), p(x) = x5 + x2 + 1

Elementos C.Ciclotomicos P.Mınimo00000 0 11111 α15

00001 1 11011 α16

00010 α 10011 α17

00100 α2 00011 α18

01000 α3 00110 α19

10000 α4 01100 α20 {0} x + 100101 α5 11000 α21 {1, 2, 4, 8, 16} x5 + x2 + 101010 α6 10101 α22 {3, 6, 12, 24, 17} x5 + x4 + x3 + x2 + 110100 α7 01111 α23 {5, 10, 20, 9, 18} x5 + x4 + x2 + x + 101101 α8 11110 α24 {7, 14, 28, 25, 19} x5 + x3 + x2 + x + 111010 α9 11001 α25 {11, 22, 13, 26, 21} x5 + x4 + x3 + x + 110001 α10 10111 α26 {15, 30, 29, 27, 23} x5 + x3 + 100111 α11 01011 α27

01110 α12 10110 α28

11100 α13 01001 α29

11101 α14 10010 α30


Cuerpos Beamer

Documents

Transcript of Cuerpos Beamer