Grgurica, Josip (2014) Problem PRIMES pripada klasi PTIME. Diploma thesis, Faculty of Science > Department of Mathematics.

PDF
Language: Croatian Download (306kB)  Preview 
Abstract
Deterministic algorithm for primality test was long time expected thing in computer science. AgrawalKayal 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 AgrawalKayalSaxena 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 AgrawalKayalSaxena 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 AgrawalKayalSaxena 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 AgrawalKayalSaxena primality test has polynomial complexity.
Item Type:  Thesis (Diploma thesis) 

Supervisor:  Širola, Boris and Vuković, Mladen 
Date:  2014 
Number of Pages:  54 
Subjects:  NATURAL SCIENCES > Mathematics 
Divisions:  Faculty of Science > Department of Mathematics 
Depositing User:  Iva Prah 
Date Deposited:  02 Jun 2015 11:38 
Last Modified:  02 Jun 2015 11:38 
URI:  http://digre.pmf.unizg.hr/id/eprint/3945 
Actions (login required)
View Item 