Äärelliset kunnat ja niiden sovelluksia

Abstract

Tässä tutkielmassa käsitellään äärellisiä kuntia ja tarkastellaan joitakin niiden sovelluksia salakirjoituksiin liittyen. Aluksi määritellään polynomit sekä polynomin juuri ja tutkitaan niiden erilaisia ominaisuuksia. Lisäksi todistetaan ensimmäisen luvun ehkä tärkein lause, polynomien jakoyhtälö, jota käytetään myöhemmin muun muassa polynomien jaollisuuden tarkastelussa. Jaollisuuden yhteydessä käsitellään polynomien suurinta yhteistä tekijää, jaottomia polynomeja sekä juurien monikertaisuutta. Seuraavaksi määritellään, mitä ovat äärelliset kunnat ja tarkastellaan niiden olemassaoloa sekä sitä, miten ja millä ehdoilla niitä voidaan muodostaa, esimerkiksi millainen on oltava alkioiden lukumäärä äärellisessa kunnassa. Määritellään myös äärellisiin kuntiin liittyviä muita käsitteitä ja niiden ominaisuuksia. Lisäksi tarkastellaan erilaisia äärellisiin kuntiin liittyviä kuvauksia, kuten Eulerin φ-funktio, joka kertoo alkioiden lukumäärän tietylle kertaluvulle. Eräs tärkeimmistä toisen luvun tuloksista on, että jokaiselle luvulle q, joka on muotoa p^n, missä p on alkuluku ja n positiivinen kokonaisluku, voidaan muodostaa yksi ja vain yksi äärellinen kunta. Tutkielman kaksi viimeistä lukua liittyvät äärellisten kuntien soveltamiseen. Kolmannessa luvussa määritellään salakirjoituksen periaatteet ja käsitteet sekä esitellään joitakin tunnettuja salausmenetelmiä, kuten RSA. Tarkastellaan myös toistetun neliöinnin ideaa, joka siis nopeuttaa huomattavasti luvun b^n mod m laskemista, kun luku n on todella suuri. Viimeisessä luvussa keskitytään yhteen tärkeimpään äärellisiin kuntiin liittyvään ongelmaan, nimittäin diskreettiin logaritmiin. Diskreetti logaritmi nousee äärellisten kuntien yhteydessä oleelliseksi ongelmaksi, kun käsitellään salausjärjestelmiä. Esimerkiksi Diffien ja Hellmanin avaintenvaihdossa ja ElGamalin salausjärjestelmässä hyödynnetään tätä ongelmaa. Lisäksi tarkastellaan erästä algoritmia, joka on kehitelty diskreettien logaritmien ratkaisemiseksi äärellisissä kunnissa. Tätä algoritmia varten todistetaan myös tärkeä kiinalainen jäännöslause.