Primitiiviset juuret: teoriaa ja sovelluksia

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 logaritm