Alkulukutesteistä

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...

Täydet tiedot

Bibliografiset tiedot
Päätekijä: Sormunen, Lauri
Muut tekijät: Matemaattis-luonnontieteellinen tiedekunta, Faculty of Sciences, Matematiikan ja tilastotieteen laitos, Department of Mathematics and Statistics, University of Jyväskylä, Jyväskylän yliopisto
Aineistotyyppi: Pro gradu
Kieli:fin
Julkaistu: 2016
Aiheet:
Linkit: https://jyx.jyu.fi/handle/123456789/48817
Kuvaus
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.