Alkulukutestejä

Abstract

Tämän tutkielman aiheena on alkulukutestit, jotka ovat sellaisia menetelmiä ja algoritmeja, joiden avulla voidaan tutkia, onko jokin luku alkuluku vai alkulukujen tulo. Tutkielman alussa käydään läpi joitakin yksinkertaisia määritelmiä ja aputuloksia jaollisuuteen liittyen sekä Eratostheneen seula, jonka avulla voidaan etsiä pienempiä alkulukuja. Toisessa luvussa käydään läpi joitakin kongruenssiin liittyviä tuloksia, joita tarvitaan myöhemminkin tutkielmassa. Toisessa luvussa osoitetaan myös Fermat'n pieni lause ja Wilsonin lause, joiden avulla voidaan tutkia hieman suurempienkin lukujen jaollisuutta.

Tutkielman ensimmäinen päätulos on probabilistinen Solovay-Strassenin alkulukutesti. Se antaa todennäköisen vastauksen, onko tutkittava luku alkuluku. Tätä testiä varten kolmannen luvun alussa osoitetaan erilaisia tuloksia sekä lukuteorian että myös algebran osa-alueilta. Lisäksi luvussa tutustutaan erilaisten pseudoalkulujen käsitteisiin ja osoitetaan niihin liittyviä aputuloksia, ennen kuin voidaan varsinaisesti käsitellä Solovay-Strassenin alkulukutestiä.

Toinen päätulos on deterministinen Miller-Rabinin alkulukutesti. Se antaa varman vastauksen, onko tutkittava luku alkuluku. Tätä testiä varten on neljännen luvun alussa jälleen aputuloksia, joita tarvitaan Miller-Rabinin alkulukutestin käsittelyyn. Tutkielman viidennessä luvussa esitellään vielä alkulukutestien sovelluksena RSA-salausmenetelmä, johon alkulukutestejä voidaan hyödyntää.