Το πρόβλημα της ντετερμενιστικής πιστοποίησης πρώτου σε πολυωνυμικό χώρο.

  1. MSc thesis
  2. ΜΗΛΙΩΡΗΣ, ΦΛΩΡΕΝΤΙΟΣ
  3. Μεταπτυχιακές Σπουδές στα Μαθηματικά (ΜΣΜ)
  4. 30 Σεπτεμβρίου 2018 [2018-09-30]
  5. Ελληνικά
  6. 51
  7. ΤΖΕΡΜΙΑΣ, ΠΑΥΛΟΣ
  8. Αλγόριθμος AKS, εύρεση πρώτων αριθμών, πρώτοι αριθμοί, ντετερμινιστικός αλγόριθμος, πολυωνυμικός χρόνος
  9. 2
  10. 24
  11. πίνακες
    • Η παρούσα διπλωματική εργασία μελετά το πρόβλημα της ντετερμινιστικής πιστοποίησης πρώτου σε πολυωνυμικό χώρο, ένα πρόβλημα που ταλαιπώρησε για πολλούς αιώνες και εξακολουθεί να ταλαιπωρεί και σήμερα τους ερευνητές. Συγκεκριμένα, ασχολείται με τον αλγόριθμο Agrawal–Kayal–Saxena (AKS), ο οποίος είναι ο μόνος ντετερμινιστικός αλγόριθμος που λύνει το πρόβλημα πιστοποίησης πρώτων αριθμών σε πολυωνυμικό χρόνο. Η παρούσα μελέτη ξεκινά με την εισαγωγή στην οποία αναφέρεται η ιστορική αναδρομή στη Θεωρία Αριθμών και στο πρόβλημα εύρεσης αλγορίθμων πιστοποίησης πρώτων αριθμών. Στη συνέχεια γίνεται αναφορά στους διάσημους αρχαίους και σύγχρονους μαθηματικούς που ασχολήθηκαν με τις ιδιότητες των πρώτων και τους αλγόριθμους εύρεσης πρώτων αριθμών. Παρατίθενται κάποια σημαντικά θεωρήματα και οι σημαντικότερες παρατηρήσεις που έχουν γίνει ως προς τους πρώτους αριθμούς από την αρχαιότητα μέχρι τα νεότερα χρόνια. Επίσης γίνεται αναφορά στην καταλυτική συνεισφορά και επίδραση της πληροφορικής στην προσπάθεια εύρεσης και υλοποίησης ταχύτερων αλγορίθμων στη σύγχρονη εποχή. Συνεχίζει με το δεύτερο κεφάλαιο όπου παρουσιάζονται οι δύο κατηγορίες αλγορίθμων: πιθανοτικών και ντετερμινιστικών. Γίνεται αναφορά στα πλεονεκτήματα και μειονεκτήματα και των δύο κατηγοριών και περιγράφονται μερικοί από τους πιο σημαντικούς πιθανοτικούς και ντετερμινιστικούς αλγορίθμους. Επίσης σε αυτό το κεφάλαιο γίνεται μια σύντομη αναφορά του σκοπού και της σημασίας της παρούσας εργασίας. Στο τρίτο κεφάλαιο, περιγράφεται ο αλγόριθμος AKS και τα βήματα του. Σε αυτό το κεφάλαιο περιγράφονται επίσης τα θεωρήματα και τα λήμματα τα οποία πιστοποιούν την ορθότητα του αλγορίθμου AKS. Στο τέταρτο κεφάλαιο γίνεται αναφορά στις δυνατότητες και στους περιορισμούς του αλγορίθμου AKS και των άλλων ντετερμινιστικών αλγορίθμων, καθώς και στην ανάλυση και βελτίωση της χρονικής του πολυπλοκότητας. Γίνεται επίσης αναφορά και σε μελλοντικές εργασίες με στόχο την βελτίωση της χρονικής πολυπλοκότητας
    • In this diploma thesis, we study the problem of deterministic certification of primes in polynomial space. This problem has troubled researchers for many centuries and continues to trouble them today. In particular, our main focus is on the algorithm Agrawal–Kayal– Saxena (AKS), which is the only deterministic algorithm that solves the primality testing problem in polynomial time. The current study begins with the introduction to which the historical review of Number Theory and the problem of finding primality testing algorithms is mentioned. Then reference is made to the famous ancient and modern mathematicians who dealt with the properties primes and the algorithms of finding prime numbers. We then refer to some important theorems and to the most important observations made, from antiquity to modern times. Also, reference is made to the catalytic contribution and influence of Information Technology in the effort to find and implement faster algorithms in modern time. It continues with the second chapter where the two categories of algorithms are presented: probabilistic and deterministic algorithms. Reference is made to the advantages and disadvantages of both categories and some of the most important probabilistic and deterministic algorithms are described. Also in this chapter a brief reference is made about the purpose and importance of this diploma thesis. In the third chapter, we explain the AKS algorithm and its steps. This chapter also describes the theorems and lemmas that certify the correctness of the AKS algorithm. In the fourth chapter reference is made to the capabilities and limitations of the AKS algorithm and other deterministic algorithms, as well as in the analysis and improvement of its time complexity. Reference is also made to future work to improve the time complexity
  13. Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.