| Περίληψη: | Πολλά κρυπτογραφικά σχήματα δημόσιου κλειδιού βασίζονται στο γεγονός ότι είναι υπολογιστικά δύσκολο να παραγοντοποιήσουμε μεγάλους ακέραιους αριθμούς. Ο ταχύτερος, και ταυτόχρονα πολυπλοκότερος, κλασσικός αλγόριθμος που είναι γνωστός μέχρι σήμερα για την παραγοντοποίηση ακεραίων μήκους άνω των 110 δεκαδικών ψηφίων είναι ο General Number Field Sieve (GNFS). Ο αλγόριθμος αυτός είναι ο καρπός πολλών ετών έρευνας, κατά τη διάρκεια της οποίας παράγονταν ολοένα και ταχύτεροι αλγόριθμοι για να καταλήξουμε μέχρι στιγμής στον αλγόριθμο GNFS.
Πρωταρχικός σκοπός της παρούσης μεταπτυχιακής εργασίας είναι η παρουσίαση του θεωρητικού μαθηματικού υπόβαθρου πάνω στο οποίο βασίζεται ο GNFS καθώς και η ακολουθιακή υλοποίηση της βασικής εκδοχής του αλγορίθμου. Ως γλώσσα υλοποίησης επιλέχθηκε η C++. Η υλοποίηση έγινε σε συνεργασία με τον συμφοιτητή μου και αγαπητό φίλο Χρήστο Μπακογιάννη, όπου στα πλαίσια της μεταπτυχιακής του εργασίας πραγματοποιήθηκε η μεταφορά της ακολουθιακής υλοποίησης του αλγορίθμου σε παράλληλο κατανεμημένο περιβάλλον χρησιμοποιώντας το Message Passing Interface (MPI). Ο πηγαίος κώδικας της υλοποίησης καθώς και σχετικές πληροφορίες υπάρχουν online στη σελίδα http://kmgnfs.cti.gr.
Σημειώνεται πως για την ευκολότερη και απρόσκοπτη ανάγνωση της εργασίας αυτής, ο αναγνώστης θα πρέπει να έχει ένα βαθμό εξοικείωσης με βασικές έννοιες της θεωρίας αριθμών, της αλγεβρικής θεωρίας αριθμών και της γραμμικής άλγεβρας.
|
|---|
