Äärellinen kunta
Wikipedia
Ää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 .
Matemaattisesti voidaan osoittaa, että äärellisen kunnan kertaluku on aina jonkin alkuluvun potenssi. Siis q = pk, missä p on jokin alkuluku ja k jokin nollaa suurempi luonnollinen luku. Alkulukua p 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 q = p on yleisemminkin helppo muodostaa tarkastelemalla jäännösluokkarengasta . Alkeislukuteorian avulla on helppo osoittaa, että muodostaa kunnan.
Kertalukua q = pk, 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 = pk olevan kunnan muodostamiseksi on ensin löydettävä astetta k oleva jaoton polynomi polynomirenkaasta .
Muodostetaan esimerkiksi kertalukua q = 4 = 22 oleva äärellinen kunta. Kunnan karakteristika p = 2, joten etsitään astetta 2 oleva jaoton polynomi polynomirenkaasta . Valitaan h(x) = x2 + x + 1. 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 α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 α.
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.
pn alkiota sisältävän äärellisen kunnan automorfismien muodostama ryhmä on niin ikään syklinen ja kertalukua n. Tämän ryhmän virittäjä on Frobeniuksen automorfismi