Alkulukutesteistä

Abstract

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.