Katsaus lukuteoriaan ja kryptografiaan.
JOKINEN, RIKU (2004)
2004
Matematiikka - Mathematics
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2004-10-20
Julkaisun pysyvä osoite on
http://urn.fi/urn:nbn:fi:uta-1-13497
http://urn.fi/urn:nbn:fi:uta-1-13497
Tiivistelmä
Hakutermit: matematiikka, lukuteoria, kryptografia
Tämä tutkielma käsittelee lukuteorian perusteita ja lukuteorian tärkeintä sovellusta, kryptografiaa. Tarkoituksena on antaa kattava yleiskuva lukuteorian alkeista ja soveltaa niitä käytäntöön.
Luvussa 1, Valmistelevia tarkasteluja, käydään läpi joitakin peruskäsitteitä, kuten jaollisuus ja määritellään alkuluvut. Luvussa 2, Kongruensseista, esitellään jaollisuuden sovellus, kongruenssit ja sen johdannaisia, kuten kiinalainen jäännöslause ja Fermat'n pieni lause. Lisäksi määritellään valealkuluvut. Luvussa 3, Primitiiviset juuret, esitellään aluksi Eulerin phi - funktio ja siitä seuraava Eulerin lause. Tämän jälkeen määritellään kokonaisluvun kertaluku sekä sovelletaan Eulerin lausetta siihen. Lopuksi esitellään primitiiviset juuret. Luvussa 4, Neliönjäännökset, määritellään neliönjäännökset ja Legendren symboli sekä todistetaan Eulerin kriteeri. Lisäksi esitellään ja todistetaan Gaussin lemma ja neliönjäännösten resiprookkilaki. Luvussa 5, Kryptografia, sovelletaan luvuissa 1 - 4 esiteltyjä asioita erilaisiin salausjärjestelmiin. Erityisen mielenkiinnon kohteena ovat julkisen avaimen salausjärjestelmät, kuten Fermat'n pientä lausetta soveltava RSA-salausjärjestelmä sekä primitiivisiä juuria soveltava ElGamal-salausjärjestelmä.
Tutkielman rakenne noudattelee pääosin Kenneth H. Rosen teosta Elementary Number Theory and Its Applications, joka on ollut myös tärkein lähdeteos. Tärkeinä lähteinä ovat olleet myös James J. Tattersallin kirja Elemetary Number Theory in Nine Chapters sekä Melvyn B. Nathansonin kirja Elementary Methods in Number Theory. Muita lähteitä on käytetty lähinnä yksittäisissä todistuksissa.
Tämä tutkielma käsittelee lukuteorian perusteita ja lukuteorian tärkeintä sovellusta, kryptografiaa. Tarkoituksena on antaa kattava yleiskuva lukuteorian alkeista ja soveltaa niitä käytäntöön.
Luvussa 1, Valmistelevia tarkasteluja, käydään läpi joitakin peruskäsitteitä, kuten jaollisuus ja määritellään alkuluvut. Luvussa 2, Kongruensseista, esitellään jaollisuuden sovellus, kongruenssit ja sen johdannaisia, kuten kiinalainen jäännöslause ja Fermat'n pieni lause. Lisäksi määritellään valealkuluvut. Luvussa 3, Primitiiviset juuret, esitellään aluksi Eulerin phi - funktio ja siitä seuraava Eulerin lause. Tämän jälkeen määritellään kokonaisluvun kertaluku sekä sovelletaan Eulerin lausetta siihen. Lopuksi esitellään primitiiviset juuret. Luvussa 4, Neliönjäännökset, määritellään neliönjäännökset ja Legendren symboli sekä todistetaan Eulerin kriteeri. Lisäksi esitellään ja todistetaan Gaussin lemma ja neliönjäännösten resiprookkilaki. Luvussa 5, Kryptografia, sovelletaan luvuissa 1 - 4 esiteltyjä asioita erilaisiin salausjärjestelmiin. Erityisen mielenkiinnon kohteena ovat julkisen avaimen salausjärjestelmät, kuten Fermat'n pientä lausetta soveltava RSA-salausjärjestelmä sekä primitiivisiä juuria soveltava ElGamal-salausjärjestelmä.
Tutkielman rakenne noudattelee pääosin Kenneth H. Rosen teosta Elementary Number Theory and Its Applications, joka on ollut myös tärkein lähdeteos. Tärkeinä lähteinä ovat olleet myös James J. Tattersallin kirja Elemetary Number Theory in Nine Chapters sekä Melvyn B. Nathansonin kirja Elementary Methods in Number Theory. Muita lähteitä on käytetty lähinnä yksittäisissä todistuksissa.