Äärellinen kunta

Wikipedia
Loikkaa: valikkoon, hakuun

Äärellinen kunta tarkoittaa matematiikassa kuntaa, jonka alkioiden lukumäärä on äärellinen. Äärellisiä kuntia kutsutaan myös Galois'n kunniksi.

Äärellisen kunnan kertaluvulla tarkoitetaan kunnan alkioiden lukumäärää. Kertalukua q olevaa kuntaa merkitään GF(q) tai \mathbb{F}_q.

Matemaattisesti voidaan osoittaa, että äärellisen kunnan kertaluku on aina jonkin alkuluvun potenssi. Siis q=p^k, missä p on jokin alkuluku ja k jokin nollaa suurempi luonnollinen luku. Toisaalta voidaan osoittaa, että on olemassa jokaista alkuluvun potenssia kertaluvultaan vastaava kunta, ja että samaa kertalukua olevat kunnat ovat isomorfisia eli olennaisesti samoja. Siis on olemassa esimerkiksi 7^6-alkioinen kunta, ja täsmälleen yksi tuollainen kunta.

Edelläolevaa alkulukua p kutsutaan kunnan \mathbb{F}_q karakteristikaksi.

Yksinkertaisin esimerkki äärellisestä kunnasta on binäärikunta \mathbb{F}_2=(\mathbb{Z}_2,+,\cdot). Tämä kunta voidaan muodostaa tarkastelemalla kokonaislukujen joukon \mathbb{Z} jäännösluokkarengasta modulo 2 tai määrittelemällä logiikassa totuusarvojen '0' (epätosi) ja '1' (tosi) joukossa operaatiot AND (kertolasku) ja XOR (yhteenlasku).

Kunnan \mathbb{F}_2 määrittelevät yhteen- ja kertolaskutaulut:

+ 0 1
0 0 1
1 1 0


x 0 1
0 0 0
1 0 1

Alkulukukertalukua q=p on yleisemminkin helppo muodostaa tarkastelemalla jäännösluokkarengasta (\mathbb{Z}_p,+,\cdot ). Alkeislukuteorian avulla on helppo osoittaa, että (\mathbb{Z}_p,+,\cdot ) muodostaa kunnan.

Kertalukua q=p^k, missä k on suurempi kuin 1, muodostaminen on jo hiukan vaikeampaa. Tällaisten kuntien muodostamiseen käytetään yleisesti polynomialgebraa. Matemaattisesti voidaan osoittaa, että kaikki yhtä monta alkiota sisältävät äärelliset kunnat ovat keskenään rakenneyhtäläisiä eli isomorfisia. Polynomialgebran avulla voidaan siis muodostaa kaikki mahdolliset äärelliset kunnat.

Kertalukua q=p^k olevan kunnan muodostamiseksi on ensin löydettävä astetta k oleva jaoton polynomi polynomirenkaasta (\mathbb{Z}_p\lbrack x\rbrack,+,\cdot).

Muodostetaan esimerkiksi kertalukua q=4=2^2 oleva äärellinen kunta. Kunnan karakteristika p=2, joten etsitään astetta 2 oleva jaoton polynomi polynomirenkaasta \mathbb{Z}_2\lbrack x\rbrack. Valitaan h(x)=x^2+x+1. Merkitsemällä polynomeja lyhyemmin luettelemalla vain niiden kertoimet (esim. 110 vastaa polynomia f(x)=1\cdot x^2+1\cdot x+0=x^2+x) saamme näin muodostuvat yhteen- ja kertolaskutaulukot muotoon:

+ 00 01 10 11
00 00 01 10 11
01 01 00 11 10
10 10 11 00 01
11 11 10 01 00


* 00 01 10 11
00 00 00 00 00
01 00 01 10 11
10 00 10 11 01
11 00 11 01 10

Matemaattisesti voidaan osoittaa, että äärellisen kunnan kertolaskuryhmä eli multiplikatiivinen ryhmä on aina syklinen. Toisin sanoen on aina olemassa sellainen nollasta eroava alkio \alpha, jonka eksponentit \alpha^n, n=0,1,...,q-2 ovat erisuuret ja kattavat koko multiplikatiivisen ryhmän. Jokainen multiplikatiivisen ryhmän alkio saadaan potenssiinkorotuksella tästä ns. primitiivisestä alkiosta \alpha.

Potenssiinkorotus on tehokkaasti laskettavissa. Päinvastainen operaatio, eksponentin laskeminen annetulle multiplikatiivisen ryhmän alkiolle, on huomattavasti hankalampi operaatio. Tätä ongelmaa kutsutaan diskreetin logaritmin ongelmaksi äärellisessä kunnassa.

Jos kunnan alkioiden lukumäärä on p^n, niin sen automorfismien muodostama ryhmä on niin ikään syklinen ja kertalukua n. Tämän ryhmän virittäjä on Frobeniuksen automorfismi \varphi:\mathbb{F}_{p^n}\to\mathbb{F}_{p^n}