Ringar, kroppar och polynomringar

typeset_mode(True)
implicit_multiplication(True)
De klassiska talmängderna är exempel på ringar och kroppar.
ZZ
print ZZ
Z\displaystyle \Bold{Z}
Integer Ring
QQ
print QQ
Q\displaystyle \Bold{Q}
Rational Field
RR
print RR
R\displaystyle \Bold{R}
Real Field with 53 bits of precision
CC
print CC
C\displaystyle \Bold{C}
Complex Field with 53 bits of precision

Ändliga ringar

Låt mm vara ett positivt heltal större än 11. Mängden Zm=Z/mZ={0,1,,m1}\mathbb{Z}_m = \mathbb{Z}/m\mathbb{Z} = \{0, 1, \ldots, m - 1\} är en ring under vanlig addition och multiplikation modulo mm. Om mm är ett primtal, så är Zm\mathbb{Z}_m en kropp.
Z28 = Zmod(28)
Z28
print Z28
Z/28Z\displaystyle \ZZ/28\ZZ
Ring of integers modulo 28
Z28.list()  # elementen i Z28
[0\displaystyle 0, 1\displaystyle 1, 2\displaystyle 2, 3\displaystyle 3, 4\displaystyle 4, 5\displaystyle 5, 6\displaystyle 6, 7\displaystyle 7, 8\displaystyle 8, 9\displaystyle 9, 10\displaystyle 10, 11\displaystyle 11, 12\displaystyle 12, 13\displaystyle 13, 14\displaystyle 14, 15\displaystyle 15, 16\displaystyle 16, 17\displaystyle 17, 18\displaystyle 18, 19\displaystyle 19, 20\displaystyle 20, 21\displaystyle 21, 22\displaystyle 22, 23\displaystyle 23, 24\displaystyle 24, 25\displaystyle 25, 26\displaystyle 26, 27\displaystyle 27]
Genom att skriva Z28(aa) konverterar man aa till ett element i Z28\mathbb{Z}_{28} under förutsättning att det går. Speciellt utförs all aritmetik modulo 2828 för element i Z28\mathbb{Z}_{28}.
a = Z28(11)
a
11\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)
Z/28Z\displaystyle \ZZ/28\ZZ
b = Z28(50)  # 50 är kongruent med 22 modulo 28
b
22\displaystyle 22
Aritmetik sker nu automatiskt modulo 2828.
a + b  # 11 + 22
5\displaystyle 5
Vi kan betrakta aa och bb som vanliga heltal, d.v.s. lyfta dem till Z\mathbb{Z}.
ZZ(a) + ZZ(b)
33\displaystyle 33
Vilket är det minsta positiva heltal kk sådant att ak=1a^k = 1?
k = a.multiplicative_order()
k
6\displaystyle 6
Aha! Den multiplikativa inversen till aa ges således av ak1a^{k-1}.
a_inv = a^(k-1)
a_inv
23\displaystyle 23
a_inv * a  # kontroll
1\displaystyle 1

Ändliga kroppar

För att deklarera en ändlig kropp använder man funktionen GF (Galois Field).
F7 = GF(7)
F7
print F7
F7\displaystyle \Bold{F}_{7}
Finite Field of size 7
F7.list()
[0\displaystyle 0, 1\displaystyle 1, 2\displaystyle 2, 3\displaystyle 3, 4\displaystyle 4, 5\displaystyle 5, 6\displaystyle 6]

True\displaystyle \mathrm{True}
a = F7.random_element()
a
3\displaystyle 3
a^(-1)  # bestäm den multiplikativa inversen till a
5\displaystyle 5

Polynomringar

Vi börjar med att deklarera polynomringen Z[X]\mathbb{Z}[X], d.v.s. ringen av alla polynom med heltalskoefficienter.
Z.<X> = ZZ[]  # alternativt: PolynomialRing(ZZ)
Z
print Z
Z[X]\displaystyle \Bold{Z}[X]
Univariate Polynomial Ring in X over Integer Ring
Vidare deklarerar vi kvotringen Z[X]/(X51)Z[X]\mathbb{Z}[X]/(X^5 - 1)\mathbb{Z}[X], vilket är ringen av alla polynom med heltalskoefficienter modulo X51X^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
45X1112X6+9X+1\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
5X4+8X34X+1\displaystyle 5X^{4} + 8X^{3} - 4X + 1
r = R([3, 4 , 5, 1])
r
x3+5x2+4x+3\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)
Z[X]\displaystyle \Bold{Z}[X]
parent(r)
Univariate Quotient Polynomial Ring in x over Integer Ring with modulus X^5 - 1
q in Z
True\displaystyle \mathrm{True}
r in Z
False\displaystyle \mathrm{False}
Vi kan lyfta ett polynom från RR till ZZ. (Notera ''variabelbytet''.)
r.lift()
X3+5X2+4X+3\displaystyle X^{3} + 5X^{2} + 4X + 3
Vid omvandling av polynom ff i ZZ till ''motsvarande'' polynom i RR, så ersätts ff med det polynom gg för vilket f=(X51)h+gf = (X^5 - 1)h + g och degg<5\deg g < 5 för något polynom hh i ZZ.
R(p)
42x+1\displaystyle 42x + 1
Vid aritmetik med denna typ av polynom sker förenkling per automatik.
p^2 + 3q
2025X221080X17+954X12+90X11216X724X6+15X4+24X3+81X2+6X+4\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=3p = 3. Vi ska studera hur man konstruerar en kropp av ordning q=35q = 3^5. Till att börja med behöver vi polynomringen R=Z3[x]R = \mathbb{Z}_3[x].
reset()  # rensa alla egendefinierade variabler
R.<X> = PolynomialRing(GF(3))
R
print R
F3[X]\displaystyle \Bold{F}_{3}[X]
Univariate Polynomial Ring in X over Finite Field of size 3
Låt oss definiera några element i RR.
a = X^4 + 2X^3 + X + 2
a
X4+2X3+X+2\displaystyle X^{4} + 2 X^{3} + X + 2
b = R([0 , 1, 2, 1, 0, 1, 2])
b
2X6+X5+X3+2X2+X\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)
[2\displaystyle 2, 1\displaystyle 1, 2\displaystyle 2, 0\displaystyle 0, 0\displaystyle 0, 1\displaystyle 1]
Vid addition och multiplikation hanterar Sage koefficienterna modluo 3.
a + b
2X6+X5+X4+2X2+2X+2\displaystyle 2 X^{6} + X^{5} + X^{4} + 2 X^{2} + 2 X + 2
a b
2X10+2X9+2X8+X5+X3+2X2+2X\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()
True\displaystyle \mathrm{True}
Om vi delar bb med gg får vi följande kvot och rest.
b // g  # kvot
2X+1\displaystyle 2 X + 1
b % g  # rest
X3+X2+2\displaystyle X^{3} + X^{2} + 2
Låt F=GF(35)F = \mathrm{GF}(3^5) vara kroppen där aritmetiken sker moldulo gg. Notera hur vi i definitionen nedan väljer att använda gement xx som symbol i polynom ur FF.
F.<x> = FiniteField(3^5 , modulus = g)
F
F35\displaystyle \Bold{F}_{3^{5}}
print F
Finite Field in x of size 3^5

(x\displaystyle x)
Vi kan definiera element i FF på samma sätt som ovan.
c = x^2 + 2x + 1
c
x2+2x+1\displaystyle x^{2} + 2 x + 1
d = F([2 , 2, 1, 0, 2])
d
2x4+x2+2x+2\displaystyle 2 x^{4} + x^{2} + 2 x + 2
Men vi kan även konvertera mellan RR och FF.
R(c)
X2+2X+1\displaystyle X^{2} + 2 X + 1
F(a)
x4+2x3+x+2\displaystyle x^{4} + 2 x^{3} + x + 2
För att kunna bestämma en koefficientlista måste polynomet lyftas till polynomringen RR.
list(R(x^3 + 2x^2 + 2x + 2))
[2\displaystyle 2, 2\displaystyle 2, 2\displaystyle 2, 1\displaystyle 1]
Eftersom bb är av grad större än 44, så bestämmer Sage automatiskt resten modulo gg. Jämför nedanstående resultat med resten vid divisionen av bb med gg som vi bestämde ovan.
b.substitute(x)
x3+x2+2\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
False\displaystyle \mathrm{False}
Notera att polynomet gg motsvarar 0 i kroppen FF.
F(g)
0\displaystyle 0
Produkten cdcd i FF respektive RR.
c d  # i F
x3+2x+1\displaystyle x^{3} + 2 x + 1
R(c) R(d)  # i R
2X6+X5+X3+X2+2\displaystyle 2 X^{6} + X^{5} + X^{3} + X^{2} + 2
I det senare fallet bestämmer inte Sage resten modulo gg. Det sker automatiskt vid beräkningar i kroppen FF.
(R(c) R(d)) % g
X3+2X+1\displaystyle X^{3} + 2 X + 1
Eftersom FF är en kropp har alla element i FF utom nollpolynomet en multiplikativ invers.
c_inv = c^(-1)
c_inv
x4+x3+2x+1\displaystyle x^{4} + x^{3} + 2 x + 1
Kontroll i FF:
c c_inv
1\displaystyle 1
Kontroll i $R:
R(c) R(c_inv)
X6+2X2+X+1\displaystyle X^{6} + 2 X^{2} + X + 1
(R(c) R(c_inv)).mod(g)  # alterntivt sätt att beräkna resten
1\displaystyle 1