Browsing by Author "Saareke, Jade"

Tutkielmassa perehdytään vaativuusteorian näkökulmasta lukuteoreettiseen ongelmaan alkuluvun tunnistamisesta.Työn aiheena on alkulukutestauksen polynomiaikaisuus ja keskiössä on tämän osoittava matemaattinen tulos, ehdoton deterministinen polynomisessa ajassa toimiva alkulukutestausalgoritmi. Tutkielmassa käydään läpi kyseisen algoritmin oikean toiminnan ja aikavaativuuden todistukset. Alkulukutestauksessa pyritään selvittämään, onko annettu luku alkuluku. Vaativuusteoriassa tämä kysymys muotoillaan kielen PRIMES päätösongelmaksi. Päätösongelman ratkaisuun haetaan algoritmia, joka kertoo vastauksen kysymykseen, kuuluuko annettu syöte joukkoon vai ei. Algoritmin katsotaan olevan tehokas, jos se on vaativuusluokassa P. Vaativuusluokka P on determinististen polynomiaikaisten algoritmien luokka. Tutkielman ensimmäinen luku on johdanto aiheeseen. Toisessa luvussa käsitellään vaativuusteoriaa. Käydään läpi aikavaativuuden analysointia asymptoottisen analyysin keinoin ja tutustutaan Turingin koneisiin sekä niiden algoritmiyhteyteen. Lopuksi esitellään vaativuusluokat P, NP ja co-NP. Kolmas luku sisältää lukuteorian perusteita ja erityisesti alkulukuja koskevia tuloksia. Aluksi käsitellään jaollisuutta ja kongruenssia sekä binomikertoimia, minkä jälkeen keskitytään alkulukuihin. Perehdytään alkuluvun tunnistamiseen ja lopuksi tuodaan mukaan vaativuusteorian näkökulma alkuluvuntunnistamisongelman PRIMES esittelyn muodossa. Neljännessä luvussa käsitellään algebran sisältöjä. Keskeisinä aiheina ovat äärelliset kunnat ja syklotomiset polynomit. Tutkielman viidennessä luvussa käydään läpi todistus alkulukutestauksen polynomiaikaisuudelle. Käsitellään tarkoitukseen kehitetyn ehdottoman deterministisen algoritmin toiminta, sen todistus ja polynomiaikainen aikavaativuus.