Primitiiviset juuret: teoriaa ja sovelluksia
SUTINEN, OUTI (2006)
2006
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ä
2006-04-20
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-15595
https://urn.fi/urn:nbn:fi:uta-1-15595
Tiivistelmä
Tutkielman tarkoituksena on perehdyttää lukija primitiivisten juurten teoriaan ja muutamiin sovelluksiin lukuteoriassa.
Ensimmäisessä luvussa määritetään kokonaisluvun kertaluku ja sen avulla primitiivinen juuri ja esitetään kuinka monta primitiivistä juurta luvulla voi olla. Lisäksi todistetaan lause, jonka avulla löydetään luvun kaikki primitiiviset juuret, kun tiedetään yksi luvun primitiivisistä juurista.
Toisessa luvussa määritetään ne luvut, joilla on primitiivinen juuri. Ensimmäisessä pykälässä käsitellään alkulukuja ja todetaan, että kaikilla alkuluvuilla on primitiivinen juuri. Toisessa pykälässä todistetaan, että ainoat positiiviset kokonaisluvut, joilla on primitiivinen juuri, ovat 1, 2, 4, p^k ja 2p^k, kun p on pariton alkuluku ja k on positiivinen kokonaisluku.
Kolmannessa luvussa käsitellään primitiivisten juurten sovelluksista diskreettiä logaritmia ja potenssin jäännöstä. Tässä luvussa esitellään muun muassa muutamia diskreetin logaritmin ominaisuuksia, joiden avulla ratkaistaan muotoa ax^b≡c (mod m) ja a^(bx)≡c (mod m) olevia kongruensseja, kun (a, m)=1.
Viimeisessä luvussa esitetään kaksi primitiivisten juurien avulla suoritettavaa alkulukutestiä, jotka ovat tehokkaita alkulukutestejä luvulle n, jos tiedetään jotain luvun n-1 alkulukutekijöistä. Lisäksi tässä luvussa käsitellään primitiivisten juurten sovelluksista universaaleja eksponentteja.
Tutkielman päälähteinä on käytetty sekä Kenneth H. Rosenin teosta Elementary Number Theory and Its Applications että Thomas Koshyn teosta Elementary Number Theory with Applications.
Hakutermit: lukuteoria, primitiivinen juuri, diskreetti logaritmi
Ensimmäisessä luvussa määritetään kokonaisluvun kertaluku ja sen avulla primitiivinen juuri ja esitetään kuinka monta primitiivistä juurta luvulla voi olla. Lisäksi todistetaan lause, jonka avulla löydetään luvun kaikki primitiiviset juuret, kun tiedetään yksi luvun primitiivisistä juurista.
Toisessa luvussa määritetään ne luvut, joilla on primitiivinen juuri. Ensimmäisessä pykälässä käsitellään alkulukuja ja todetaan, että kaikilla alkuluvuilla on primitiivinen juuri. Toisessa pykälässä todistetaan, että ainoat positiiviset kokonaisluvut, joilla on primitiivinen juuri, ovat 1, 2, 4, p^k ja 2p^k, kun p on pariton alkuluku ja k on positiivinen kokonaisluku.
Kolmannessa luvussa käsitellään primitiivisten juurten sovelluksista diskreettiä logaritmia ja potenssin jäännöstä. Tässä luvussa esitellään muun muassa muutamia diskreetin logaritmin ominaisuuksia, joiden avulla ratkaistaan muotoa ax^b≡c (mod m) ja a^(bx)≡c (mod m) olevia kongruensseja, kun (a, m)=1.
Viimeisessä luvussa esitetään kaksi primitiivisten juurien avulla suoritettavaa alkulukutestiä, jotka ovat tehokkaita alkulukutestejä luvulle n, jos tiedetään jotain luvun n-1 alkulukutekijöistä. Lisäksi tässä luvussa käsitellään primitiivisten juurten sovelluksista universaaleja eksponentteja.
Tutkielman päälähteinä on käytetty sekä Kenneth H. Rosenin teosta Elementary Number Theory and Its Applications että Thomas Koshyn teosta Elementary Number Theory with Applications.
Hakutermit: lukuteoria, primitiivinen juuri, diskreetti logaritmi