Ανάλυση Και Υλοποίηση Σύγχρονων Αλγορίθμων Εντοπισμού Πρώτων Αριθμών

Abstract

Η παρούσα διπλωματική εργασία μελετά σύγχρονους υπολογιστικούς αλγορίθμους εύρεσης πρώτων αριθμών. Συγκεκριμένα, ασχολείται με δύο αλγορίθμους, έναν ντετερμινιστικό πολυωνυμικού λογαριθμικού χρόνου, τον Agrawal-Kayal-Saxena (AKS), και έναν πιθανοθεωρητικό αλγόριθμο ευρετικού χρόνου, τον Elliptic Curve Primality Proving (ECPP). Ο αλγόριθμος AKS είναι ο πρώτος αλγόριθμος πολυωνυμικού λογαριθμικού χρόνου και ταυτόχρονα ντετερμινιστικός που έχει αναπτυχθεί, ενώ ο ECPP είναι ένας γρήγορος και ευρέως διαδεδομένος στατιστικός αλγόριθμος αναζήτησης. Με χρήση της γλώσσας C, και με τη βοήθεια δύο βιβλιοθηκών πολλαπλής ακρίβειας υπολογισμών, τη βιβλιοθήκη GMP και τη βιβλιοθήκη MPFR, υλοποιούμε τον αλγόριθμο AKS. Η υλοποίηση αυτή μας δείχνει ότι ο αλγόριθμος AKS είναι ακριβής, αλλά ταυτόχρονα και αρκετά αργός σε σύγκριση με τους ήδη υπάρχοντες αλγορίθμους για αναζήτηση μικρών πρώτων (n < O(10*19)). Η εργασία δομείται σε τέσσερα κεφάλαια. Στο πρώτο κεφάλαιο γίνεται εισαγωγή στο πρόβλημα εύρεσης πρώτων αριθμών, μέσα από μία ιστορική ανασκόπηση. Στο δεύτερο κεφάλαιο, παρουσιάζονται οι δύο αλγόριθμοι που μελετά η εργασία. Στο τρίτο κεφάλαιο, περιγράφεται η υλοποίηση των δύο αλγορίθμων. Τέλος, στο τελευταίο κεφάλαιο, γίνεται συζήτηση όσον αφορά τις δυνατότητες και τους περιορισμούς του αλγορίθμου AKS.