Äärellinen kunta
Äärellinen kunta tarkoittaa matematiikassa kuntaa, jonka alkioiden lukumäärä on äärellinen. Äärellisiä kuntia kutsutaan myös Galois'n kunniksi ranskalaismatemaatikko Évariste Galois'n mukaan.
Äärellisen kunnan kertaluvulla tarkoitetaan kunnan alkioiden lukumäärää. Kertalukua olevaa kuntaa merkitään tai .
Matemaattisesti voidaan osoittaa, että äärellisen kunnan kertaluku on aina jonkin alkuluvun potenssi. Siis , missä on jokin alkuluku ja 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 -alkioinen kunta, ja täsmälleen yksi tuollainen kunta.
Edellä olevaa alkulukua kutsutaan kunnan karakteristikaksi.
Yksinkertaisin esimerkki äärellisestä kunnasta on binäärikunta . Tämä kunta voidaan muodostaa tarkastelemalla kokonaislukujen joukon 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 määrittelevät yhteen- ja kertolaskutaulut:
0 | 1 | |
0 | 0 | 1 |
1 | 1 | 0 |
x | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
Alkulukukertalukua on yleisemminkin helppo muodostaa tarkastelemalla jäännösluokkarengasta . Alkeislukuteorian avulla on helppo osoittaa, että muodostaa kunnan.
Kertalukua , missä on suurempi kuin , 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 olevan kunnan muodostamiseksi on ensin löydettävä astetta oleva jaoton polynomi polynomirenkaasta .
Muodostetaan esimerkiksi kertalukua oleva äärellinen kunta. Kunnan karakteristika , joten etsitään astetta oleva jaoton polynomi polynomirenkaasta . Valitaan . Merkitsemällä polynomeja lyhyemmin luettelemalla vain niiden kertoimet (esim. 110 vastaa polynomia ) 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 , jonka eksponentit , ovat erisuuret ja kattavat koko multiplikatiivisen ryhmän. Jokainen multiplikatiivisen ryhmän alkio saadaan potenssiinkorotuksella tästä ns. primitiivisestä alkiosta .
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 , niin sen automorfismien muodostama ryhmä on niin ikään syklinen ja kertalukua n. Tämän ryhmän virittäjä on Frobeniuksen automorfismi