E-Locus - Institutional Repository of the University of Crete

Home Collections School/Department School of Sciences and Engineering Department of Mathematics and Applied Mathematics Post-graduate theses

Post-graduate theses

Current Record: 69 of 125

[Add to Basket]

Identifier

000415082

Title

Έλεγχος πρώτων αριθμών : πιθανοθεωρητικοί και ντετερμινιστικοί αλγόριθμοι

Alternative Title

Primality testing

Author

Μανιού, Δήμητρα

Thesis advisor

Κολουντζάκης, Μιχάλης

Reviewer

Τζανάκης, Νικόλαος
Γαρεφαλάκης, Θεόδουλος

Abstract

The topic of the thesis is primality checking. In particular, we will look at randomized and deterministic algorithms, that check if an integer p is a prime, requiring polynomial time with respect to the size of p, i.e. with respect to log p. At .rst we refer to Pratt’s theorem that there exists a polynomial algorithm for the veri.cation of prime numbers. Speci.cally, there exists an algorithm of polynomial time with respect to log p that, given p and some additional information (the “certi.cate”), can verify that p is indeed a prime number. Afterwards, we describe three randomized algorithms, the Fermat test, the Miller-Rabin test and the Solovay-Strassen test. These algorithms, applied to a prime number n, return the output “prime”, and applied to a composite number n they return the correct output “composite” with probability greater than 12 . Finally, we present the deterministic algorithm of Agrawal, Kayal and Saxena for primality checking, which runs in polynomial time, and we look at the correctness proof of this algorithm.

Language

Greek

Subject

Fermat test

Miller-Rabin test

Prime number

Έλεγχος Fermat

Issue date

2018-3-23

Collection

School/Department--School of Sciences and Engineering--Department of Mathematics and Applied Mathematics--Post-graduate theses

Type of Work--Post-graduate theses