Πιστοποίηση πρώτου αριθμού και ο αλγόριθμος AKS

Primality testing and the AKS algorith (english)

  1. MSc thesis
  2. Λουμπάρδης, Παναγιώτης
  3. Μεταπτυχιακές Σπουδές στα Μαθηματικά (ΜΣΜ)
  4. 30 September 2018 [2018-09-30]
  5. Ελληνικά
  6. 90
  7. Πουλάκης, Δημήτριος
  8. Πουλάκης, Δημήτριος | Ανούσης, Μιχαήλ
  9. Πιστοποίηση πρώτου | AKS αλγόριθμος
  10. 3
  11. 31
  12. 2
    • Η παρούσα εργασία έχει σκοπό να παρουσιάσει συνοπτικά βασικά στοιχεία της Θεωρίας Αριθμών και να αναλύσει πως ο αλγόριθμος AKS, ο πρώτος αλγόριθμος πολυωνιμικού λογαριθμικού χρόνου και ταυτόχρονα ντετερμινιστικός, εφαρμόζεται στην πιστοποίηση πρώτων αριθμών. Αρχικά, στο πρώτο κεφάλαιο, γίνεται μια ιστορική αναδρομή και παρουσιάζονται τα στοιχεία που θα κάνουν κατανοητή την πιστοποίηση πρώτων αριθμών και την παραγοντοποίησή τους, καθώς και πως ταξινομούνται οι μέθοδοι πιστοποίησης πρώτων αριθμών. Ακολούθως, στο δεύτερο κεφάλαιο, παρουσιάζονται τα στοιχεία της Υπολογιστικής Θεωρίας Αριθμών που είναι απαραίτητα για την πιστοποίηση πρώτων αριθμών, καθώς και κάποιοι αλγόριθμοι πιστοποίησης πρώτων αριθμών. Τέλος, στο τρίτο κεφάλαιο, γίνεται μία ιστορική αναδρομή στους δημιουργούς του AKS, την θεωρητική του προσέγγιση, την αξιολόγηση τού και τέλος τις μελλοντικές προσεγγίσεις - επεκτάσεις.
    • This thesis is intended to summarize basic elements of Number Theory and to analyze how the AKS algorithm, the first algorithm of polynomial - logarithmic time and simultaneously deterministic, is applied to the primality testing. Initially, in the first chapter, a historical overview is made, the elements that will explain the prime number certification and their factorization are presented and finally how the prime number certification methods are classified. Subsequently, the second chapter presents the elements of the Computational Number Theory that are necessary for the certification of prime numbers, as well as some primality testing algorithms. Finally, in the third chapter, there is a historical review of the authors of the AKS, its theoretical approach, its evaluation and finally the future approaches - extensions.
  14. Αναφορά Δημιουργού 4.0 Διεθνές