Problem PRIMES pripada klasi PTIME

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

[img]
Preview
PDF
Language: Croatian

Download (306kB) | Preview

Abstract

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.

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 View Item