Show simple item record

dc.contributor.advisorKurittu, Lassi
dc.contributor.authorSormunen, Lauri
dc.date.accessioned2016-02-17T18:36:22Z
dc.date.available2016-02-17T18:36:22Z
dc.date.issued2016
dc.identifier.otheroai:jykdok.linneanet.fi:1522472
dc.identifier.urihttps://jyx.jyu.fi/handle/123456789/48817
dc.description.abstractTä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.
dc.format.extent1 verkkoaineisto (77 sivua)
dc.language.isofin
dc.rightsJulkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.fi
dc.rightsThis publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.en
dc.subject.otherAlkuluvut
dc.subject.otherAlkulukutesti
dc.subject.otherMiller-Rabin
dc.subject.otherFermat
dc.subject.otherLucas-Lehmer
dc.subject.otherAKS
dc.subject.otheralgoritmi
dc.titleAlkulukutesteistä
dc.identifier.urnURN:NBN:fi:jyu-201602171600
dc.type.ontasotPro gradufi
dc.type.ontasotMaster's thesisen
dc.contributor.tiedekuntaMatemaattis-luonnontieteellinen tiedekuntafi
dc.contributor.tiedekuntaFaculty of Sciencesen
dc.contributor.laitosMatematiikan ja tilastotieteen laitosfi
dc.contributor.laitosDepartment of Mathematics and Statisticsen
dc.contributor.yliopistoUniversity of Jyväskyläen
dc.contributor.yliopistoJyväskylän yliopistofi
dc.contributor.oppiaineMatematiikkafi
dc.contributor.oppiaineMathematicsen
dc.date.updated2016-02-17T18:36:22Z
dc.rights.accesslevelopenAccessfi
dc.contributor.oppiainekoodi4041
dc.subject.ysoalkuluvut
dc.subject.ysoalgoritmit


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record