Problem PRIMES pripada klasi PTIME

diplomski rad

• Autor: Josip Grgurica
• Mentor: Mladen Vuković (mentor)
• Mentor: Boris Širola (mentor)
• Član povjerenstva: Boris Širola (predsjednik povjerenstva)
• Član povjerenstva: Mladen Vuković (član povjerenstva)
• Član povjerenstva: Lavoslav Čaklović (član povjerenstva)
• Član povjerenstva: Goranka Nogo (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2014-09-15, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U računalnoj znanosti se dugo vremena čekalo na deterministički algoritam koji u polinomnom vremenu može odrediti je li neki prirodan broj prost. Agrawal-Kayal-Saxenin algoritam je prvi algoritam za koji se dokazalo da određuje prostost nekog broja u polinomnom vremenu, tj. navedena trojica matematičara su pokazali da jezik PRIMES pripada klasi složenosti P. Cilj ovog diplomskog rada bio je pokazati da jezik PRIMES pripada klasi P, tj. predstaviti Agrawal-Kayal-Saxenov algoritam, dokazati njegovu korektnost i odrediti njegovu složenost. U prvom, uvodnom poglavlju diplomskog rada dali smo bitne definicije i rezultate iz teorije brojeva, teorije složenosti i algebre. Te definicije i rezultati su nam bili potrebni da bi u drugom, glavnom dijelu diplomskog rada mogli dokazati korektnost Agrawal-Kayal-Saxeninog algoritam i pokazati da pripada klasi složenosti P. Također smo u prvom poglavlju opisali algoritme sa slučajnim elementima te smo prošli kroz povijest problema PRIMES. Glavni dio diplomskog rada smo podijelili u dva dijela. U prvom dijelu, AKS algoritam dokaz korektnosti, dali smo motivaciju za algoritam koja se temeljila na Pascalovu trokutu, te smo predstavili Agrawal-Kayal-Saxenin algoritam i kroz niz rezultata pokazali smo da je korektan. U drugom dijelu smo uz pomoć raznih algoritama, koji su nam olakšali dokazivanje, pokazali da je Agrawal-Kayal-Saxenin algoritam polinomne složenosti.

Sažetak (engleski)

Deterministic algorithm for primality test was long time expected thing in computer science. Agrawal-Kayal- Saxena algorithm is the first algorithm which in polynomial time determines whether a given number is prime, namely the threesome has shown that language PRIMES is in complexity class P. The main goal of this work is to show that language PRIMES is in complexity class P, namely introduce Agrawal-Kayal-Saxena primality test, prove its correctness and determine its complexity. In the first, introductory chapter of this work we have gave essential definitions and results from number theory, complexity theory and algebra. We need this definitions and results for our second, main chapter, so that we can prove correctness of Agrawal-Kayal-Saxena primality test and show that it is in complexity class P. In the introductory chapter we have also described randomized algorithms and we have gave walk through the histroy of PRIMES problem. The main part of this work we have divided into two parts. We have mentioned Pascal triangle as a motivation for the AKS algorithm. We have also introduced Agrawal-KayalSaxena primality test and with help of various results we have proved its correctness. In the second part of main chapter, with help of various algorithms we have proved that AgrawalKayal-Saxena primality test has polynomial complexity.

• Ključne riječi: deterministički algoritam; prosti broj; Agrawal-Kayal-Saxenin algoritam; PRIMES; AKS algoritam
• Ključne riječi (engleski): deterministic algorithm; primality test; prime number; Agrawal-Kayal- Saxena algorithm; PRIMES; AKS algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:343801
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-01-25 11:54:36