| Yhteenveto: | Tämän tutkielman tavoitteena on esittää tunnetuimmat alkulukutestit niin matemaattiselta
perustoiltaan kuin käytännön toteutuksiltaan ohjelmakoodin muodossa.
Alkulukutestit jaotellaan yleisesti deterministisiin ja probabilistisiin testeihin; deterministiset
testit antavat täysin varman vastauksen, mutta ovat suurille luvuille huomattavasti
probabilistia testejä hitaampia. Probabilistiset testit ovat nopeita tehdä,
mutta saattavat antaa väärän vastauksen. Testien suoritusaikaa mitataan karkeasti
niiden suorittamiseksi vaadittavien laskutoimitusten lukumääarällä.
Tutkielmassa käsitellään deterministisistä testeistä jakolaskumenetelmä, Wilsonin
lause, Prothin testi, Lucasin ja Lehmerin testi ja viimeisenä suhteellisen uusi AKStesti.
Yleisesti deterministiset testit eivät ole kovin käyttökelpoisia, sillä niiden suoritusaika
kasvaa eksponentiaalisesti testattavan luvun kasvaessa tai ne toimivat ainoastaan
tiettyä muotoa oleville luvuille. Probabilistisiin testeihin päädytään hyöyntämällä
Fermat’n pientä lausetta käänteisesti, ja tätä kutsutaan Fermat’n alkulukutestiksi.
Kyseinen testi ei kuitenkaan toimi kovin luotettavasti: on olemassa Carmichaelin
lukuja, jotka hyvin todennäköisesti toteuttavat Fermat’n pienen lauseen yhtälön,
vaikka ovatkin yhdistettyjä lukuja. Fermat’n alkulukutestin johdannainen Millerin ja
Rabinin testi on kuitenkin erittäin käytetty sen vuoksi, ett tälle pystytääan määrittelemään
virheraja, jolla testi antaa vääriä vastauksia. Solovayn ja Strassenin testi on
hyvin lähellä kahta viimeksi mainittua testiä, muttei ole aivan yhtä luotettava kuin
Millerin ja Rabinin testi.
Alkulukutestiä, kuten monia algoritmeja yleensäkin, nimitetään polynomiaikaiseksi,
jos siinä vaadittavien laskutoimitusten lukumäärä on polynomi testattavan luvun
numeroiden lukumäärän suhteen. Pitkäänn alkulukutestaus ei ollut polynomisessa
ajassa ratkaistava ongelma, ennen kuin vuonna 2002 julkaistiin AKS-testi, joka on
ensimmäinen deterministinen ja polynomiaikainen alkulukutesti. Tutkielmassa todistetaan
lopulta myös tämän testin toimivuus sekä todetaan, että kyseessä todellakin
on polynomiaikainen algoritmi.
|
|---|