Ringar_och_kroppar.sagews

Ringar, kroppar och polynomringar

typeset_mode(True)
implicit_multiplication(True)

De klassiska talmängderna är exempel på ringar och kroppar.

ZZ
print ZZ

$\displaystyle \Bold{Z}$

Integer Ring

QQ
print QQ

$\displaystyle \Bold{Q}$

Rational Field

RR
print RR

$\displaystyle \Bold{R}$

Real Field with 53 bits of precision

CC
print CC

$\displaystyle \Bold{C}$

Complex Field with 53 bits of precision

Ändliga ringar

Låt $m$ vara ett positivt heltal större än $1$. Mängden $\mathbb{Z}_m = \mathbb{Z}/m\mathbb{Z} = \{0, 1, \ldots, m - 1\}$ är en ring under vanlig addition och multiplikation modulo $m$. Om $m$ är ett primtal, så är $\mathbb{Z}_m$ en kropp.

Z28 = Zmod(28)
Z28
print Z28

$\displaystyle \ZZ/28\ZZ$

Ring of integers modulo 28

Z28.list()  # elementen i Z28

[$\displaystyle 0$, $\displaystyle 1$, $\displaystyle 2$, $\displaystyle 3$, $\displaystyle 4$, $\displaystyle 5$, $\displaystyle 6$, $\displaystyle 7$, $\displaystyle 8$, $\displaystyle 9$, $\displaystyle 10$, $\displaystyle 11$, $\displaystyle 12$, $\displaystyle 13$, $\displaystyle 14$, $\displaystyle 15$, $\displaystyle 16$, $\displaystyle 17$, $\displaystyle 18$, $\displaystyle 19$, $\displaystyle 20$, $\displaystyle 21$, $\displaystyle 22$, $\displaystyle 23$, $\displaystyle 24$, $\displaystyle 25$, $\displaystyle 26$, $\displaystyle 27$]

Genom att skriva Z28($a$) konverterar man $a$ till ett element i $\mathbb{Z}_{28}$ under förutsättning att det går. Speciellt utförs all aritmetik modulo $28$ för element i $\mathbb{Z}_{28}$.

a = Z28(11)
a

$\displaystyle 11$

Vid utskrift ser det ut som vilka heltal som helst. Men internt har Sage koll på i vilken algebraisk struktur som variabelns värde hör hemma.

parent(a)

$\displaystyle \ZZ/28\ZZ$

b = Z28(50)  # 50 är kongruent med 22 modulo 28
b

$\displaystyle 22$

Aritmetik sker nu automatiskt modulo $28$.

a + b  # 11 + 22

$\displaystyle 5$

Vi kan betrakta $a$ och $b$ som vanliga heltal, d.v.s. lyfta dem till $\mathbb{Z}$.

ZZ(a) + ZZ(b)

$\displaystyle 33$

Vilket är det minsta positiva heltal $k$ sådant att $a^k = 1$?

k = a.multiplicative_order()
k

$\displaystyle 6$

Aha! Den multiplikativa inversen till $a$ ges således av $a^{k-1}$.

a_inv = a^(k-1)
a_inv

$\displaystyle 23$

a_inv * a  # kontroll

$\displaystyle 1$

Ändliga kroppar

För att deklarera en ändlig kropp använder man funktionen GF (Galois Field).

F7 = GF(7)
F7
print F7

$\displaystyle \Bold{F}_{7}$

Finite Field of size 7

F7.list()

[$\displaystyle 0$, $\displaystyle 1$, $\displaystyle 2$, $\displaystyle 3$, $\displaystyle 4$, $\displaystyle 5$, $\displaystyle 6$]

$\displaystyle \mathrm{True}$

a = F7.random_element()
a

$\displaystyle 3$

a^(-1)  # bestäm den multiplikativa inversen till a

$\displaystyle 5$

Polynomringar

Vi börjar med att deklarera polynomringen $\mathbb{Z}[X]$, d.v.s. ringen av alla polynom med heltalskoefficienter.

Z.<X> = ZZ[]  # alternativt: PolynomialRing(ZZ)
Z
print Z

$\displaystyle \Bold{Z}[X]$

Univariate Polynomial Ring in X over Integer Ring

Vidare deklarerar vi kvotringen $\mathbb{Z}[X]/(X^5 - 1)\mathbb{Z}[X]$, vilket är ringen av alla polynom med heltalskoefficienter modulo $X^5 - 1$. Vi låter Sage använda x som variabel för polynom i denna ring.

R.<x> = Z.quotient(X^5 - 1)
R

Univariate Quotient Polynomial Ring in x over Integer Ring with modulus X^5 - 1

Det finns flera olika sätt att deklarera ett polynom. Dels på sedvanligt sätt:

p = 45X^11 - 12X^6 + 9X + 1
p

$\displaystyle 45X^{11} - 12X^{6} + 9X + 1$

Man kan även specificera koefficienterna i en lista, med konstanttermen först och högstagradskoefficienten sist.

q = Z([1, -4, 0, 8, 5])
q

$\displaystyle 5X^{4} + 8X^{3} - 4X + 1$

r = R([3, 4 , 5, 1])
r

$\displaystyle x^{3} + 5x^{2} + 4x + 3$

Variabeln avslöjar till vilken polynomring respektive polynom hör (Sage skiljer på gemener och versaler).

parent(p)

$\displaystyle \Bold{Z}[X]$

parent(r)

Univariate Quotient Polynomial Ring in x over Integer Ring with modulus X^5 - 1

q in Z

$\displaystyle \mathrm{True}$

r in Z

$\displaystyle \mathrm{False}$

Vi kan lyfta ett polynom från $R$ till $Z$. (Notera ''variabelbytet''.)

r.lift()

$\displaystyle X^{3} + 5X^{2} + 4X + 3$

Vid omvandling av polynom $f$ i $Z$ till ''motsvarande'' polynom i $R$, så ersätts $f$ med det polynom $g$ för vilket $f = (X^5 - 1)h + g$ och $\deg g [removed]

R(p)

$\displaystyle 42x + 1$

Vid aritmetik med denna typ av polynom sker förenkling per automatik.

p^2 + 3q

$\displaystyle 2025X^{22} - 1080X^{17} + 954X^{12} + 90X^{11} - 216X^{7} - 24X^{6} + 15X^{4} + 24X^{3} + 81X^{2} + 6X + 4$

Kroppsutvidnignar av ändliga kroppar

Låt $p = 3$. Vi ska studera hur man konstruerar en kropp av ordning $q = 3^5$. Till att börja med behöver vi polynomringen $R = \mathbb{Z}_3[x]$.

reset()  # rensa alla egendefinierade variabler
R.<X> = PolynomialRing(GF(3))
R
print R

$\displaystyle \Bold{F}_{3}[X]$

Univariate Polynomial Ring in X over Finite Field of size 3

Låt oss definiera några element i $R$.

a = X^4 + 2X^3 + X + 2
a

$\displaystyle X^{4} + 2 X^{3} + X + 2$

b = R([0 , 1, 2, 1, 0, 1, 2])
b

$\displaystyle 2 X^{6} + X^{5} + X^{3} + 2 X^{2} + X$

Man kan även givet ett polynom bestämma motsvarande lista av koefficienter.

list(X^5 + 2X^2 + X + 2)

[$\displaystyle 2$, $\displaystyle 1$, $\displaystyle 2$, $\displaystyle 0$, $\displaystyle 0$, $\displaystyle 1$]

Vid addition och multiplikation hanterar Sage koefficienterna modluo 3.

a + b

$\displaystyle 2 X^{6} + X^{5} + X^{4} + 2 X^{2} + 2 X + 2$

a b

$\displaystyle 2 X^{10} + 2 X^{9} + 2 X^{8} + X^{5} + X^{3} + 2 X^{2} + 2 X$

Vi behöver ett irreducibelt femtegradspolynom.

g = X^5 + 2X + 1
g.is_irreducible()

$\displaystyle \mathrm{True}$

Om vi delar $b$ med $g$ får vi följande kvot och rest.

b // g  # kvot

$\displaystyle 2 X + 1$

b % g  # rest

$\displaystyle X^{3} + X^{2} + 2$

Låt $F = \mathrm{GF}(3^5)$ vara kroppen där aritmetiken sker moldulo $g$. Notera hur vi i definitionen nedan väljer att använda gement $x$ som symbol i polynom ur $F$.

F.<x> = FiniteField(3^5 , modulus = g)
F

$\displaystyle \Bold{F}_{3^{5}}$

print F

Finite Field in x of size 3^5

($\displaystyle x$)

Vi kan definiera element i $F$ på samma sätt som ovan.

c = x^2 + 2x + 1
c

$\displaystyle x^{2} + 2 x + 1$

d = F([2 , 2, 1, 0, 2])
d

$\displaystyle 2 x^{4} + x^{2} + 2 x + 2$

Men vi kan även konvertera mellan $R$ och $F$.

R(c)

$\displaystyle X^{2} + 2 X + 1$

F(a)

$\displaystyle x^{4} + 2 x^{3} + x + 2$

För att kunna bestämma en koefficientlista måste polynomet lyftas till polynomringen $R$.

list(R(x^3 + 2x^2 + 2x + 2))

[$\displaystyle 2$, $\displaystyle 2$, $\displaystyle 2$, $\displaystyle 1$]

Eftersom $b$ är av grad större än $4$, så bestämmer Sage automatiskt resten modulo $g$. Jämför nedanstående resultat med resten vid divisionen av $b$ med $g$ som vi bestämde ovan.

b.substitute(x)

$\displaystyle x^{3} + x^{2} + 2$

Sage gör skillnad på vilken symbol som används. Därför kan man inte blanda X och x i samma algebraiska uttryck.

X^2 + 1 == x^2 + 1

$\displaystyle \mathrm{False}$

Notera att polynomet $g$ motsvarar 0 i kroppen $F$.

F(g)

$\displaystyle 0$

Produkten $cd$ i $F$ respektive $R$.

c d  # i F

$\displaystyle x^{3} + 2 x + 1$

R(c) R(d)  # i R

$\displaystyle 2 X^{6} + X^{5} + X^{3} + X^{2} + 2$

I det senare fallet bestämmer inte Sage resten modulo $g$. Det sker automatiskt vid beräkningar i kroppen $F$.

(R(c) R(d)) % g

$\displaystyle X^{3} + 2 X + 1$

Eftersom $F$ är en kropp har alla element i $F$ utom nollpolynomet en multiplikativ invers.

c_inv = c^(-1)
c_inv

$\displaystyle x^{4} + x^{3} + 2 x + 1$

Kontroll i $F$:

c c_inv

$\displaystyle 1$

Kontroll i $R:

R(c) R(c_inv)

$\displaystyle X^{6} + 2 X^{2} + X + 1$

(R(c) R(c_inv)).mod(g)  # alterntivt sätt att beräkna resten

$\displaystyle 1$