Η μέθοδος παραγοντοποίησης ακεραίων αριθμών number field sieve : θεωρία και υλοποίηση
Πολλά κρυπτογραφικά σχήματα δημόσιου κλειδιού βασίζονται στο γεγονός ότι είναι υπολογιστικά δύσκολο να παραγοντοποιήσουμε μεγάλους ακέραιους αριθμούς. Ο ταχύτερος, και ταυτόχρονα πολυπλοκότερος, κλασσικός αλγόριθμος που είναι γνωστός μέχρι σήμερα για την παραγοντοποίηση ακεραίων μήκους άνω των 110 δ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2010
|
| Θέματα: | |
| Διαθέσιμο Online: | http://nemertes.lis.upatras.gr/jspui/handle/10889/3735 |
| id |
nemertes-10889-3735 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-37352022-09-05T05:38:16Z Η μέθοδος παραγοντοποίησης ακεραίων αριθμών number field sieve : θεωρία και υλοποίηση The integer factorization algorithm number field sieve : theory and implementation Καραπάνος, Νικόλαος Σπυράκης, Παύλος Σπυράκης, Παύλος Κακλαμάνης, Χρήστος Σταματίου, Ιωάννης Karapanos, Nikolaos Παραγοντοποίηση ακέραιων αριθμών Κρυπτογραφία δημόσιου κλειδιού Αλγόριθμοι υποεκθετικής πολυπλοκότητας Κόσκινο αριθμητικού πεδίου Integer factorization Public key cryptography Subexponential time algorithms General number field sieve (GNFS) Number field sieve (NFS) 003.54 Πολλά κρυπτογραφικά σχήματα δημόσιου κλειδιού βασίζονται στο γεγονός ότι είναι υπολογιστικά δύσκολο να παραγοντοποιήσουμε μεγάλους ακέραιους αριθμούς. Ο ταχύτερος, και ταυτόχρονα πολυπλοκότερος, κλασσικός αλγόριθμος που είναι γνωστός μέχρι σήμερα για την παραγοντοποίηση ακεραίων μήκους άνω των 110 δεκαδικών ψηφίων είναι ο General Number Field Sieve (GNFS). Ο αλγόριθμος αυτός είναι ο καρπός πολλών ετών έρευνας, κατά τη διάρκεια της οποίας παράγονταν ολοένα και ταχύτεροι αλγόριθμοι για να καταλήξουμε μέχρι στιγμής στον αλγόριθμο GNFS. Πρωταρχικός σκοπός της παρούσης μεταπτυχιακής εργασίας είναι η παρουσίαση του θεωρητικού μαθηματικού υπόβαθρου πάνω στο οποίο βασίζεται ο GNFS καθώς και η ακολουθιακή υλοποίηση της βασικής εκδοχής του αλγορίθμου. Ως γλώσσα υλοποίησης επιλέχθηκε η C++. Η υλοποίηση έγινε σε συνεργασία με τον συμφοιτητή μου και αγαπητό φίλο Χρήστο Μπακογιάννη, όπου στα πλαίσια της μεταπτυχιακής του εργασίας πραγματοποιήθηκε η μεταφορά της ακολουθιακής υλοποίησης του αλγορίθμου σε παράλληλο κατανεμημένο περιβάλλον χρησιμοποιώντας το Message Passing Interface (MPI). Ο πηγαίος κώδικας της υλοποίησης καθώς και σχετικές πληροφορίες υπάρχουν online στη σελίδα http://kmgnfs.cti.gr. Σημειώνεται πως για την ευκολότερη και απρόσκοπτη ανάγνωση της εργασίας αυτής, ο αναγνώστης θα πρέπει να έχει ένα βαθμό εξοικείωσης με βασικές έννοιες της θεωρίας αριθμών, της αλγεβρικής θεωρίας αριθμών και της γραμμικής άλγεβρας. Many public-key cryptosystems build their security on our inability to factor very large integers. The General Number Field Sieve (GNFS) is the most efficient, and at the same time most complex, classical known algorithm for factoring integers larger than 110 digits. This algorithm is the result of many years of research, during which, faster and faster algorithms were developed finally winding up to the development of the GNFS. The main purpose of this master thesis is the presentation of the mathematical ideas, on which the GNFS was developed, as well as a sequential implementation of the basic version of the algorithm. C++ was the language of choice. The implementation took place in collaboration with my colleague and dear friend Christos Bakogiannis, where as part of his master thesis, a distributed implementation of the algorithm using Message Passing Interface (MPI) was also developed. The source code of the implementations is publicly available and can be found online at http://kmgnfs.cti.gr. It is presumed that the reader is familiar with basic concepts of number theory, algebraic number theory and linear algebra. 2010-09-21T08:06:37Z 2010-09-21T08:06:37Z 2010-06-08 2010-09-21T08:06:37Z Thesis http://nemertes.lis.upatras.gr/jspui/handle/10889/3735 gr Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. 0 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Παραγοντοποίηση ακέραιων αριθμών Κρυπτογραφία δημόσιου κλειδιού Αλγόριθμοι υποεκθετικής πολυπλοκότητας Κόσκινο αριθμητικού πεδίου Integer factorization Public key cryptography Subexponential time algorithms General number field sieve (GNFS) Number field sieve (NFS) 003.54 |
| spellingShingle |
Παραγοντοποίηση ακέραιων αριθμών Κρυπτογραφία δημόσιου κλειδιού Αλγόριθμοι υποεκθετικής πολυπλοκότητας Κόσκινο αριθμητικού πεδίου Integer factorization Public key cryptography Subexponential time algorithms General number field sieve (GNFS) Number field sieve (NFS) 003.54 Καραπάνος, Νικόλαος Η μέθοδος παραγοντοποίησης ακεραίων αριθμών number field sieve : θεωρία και υλοποίηση |
| description |
Πολλά κρυπτογραφικά σχήματα δημόσιου κλειδιού βασίζονται στο γεγονός ότι είναι υπολογιστικά δύσκολο να παραγοντοποιήσουμε μεγάλους ακέραιους αριθμούς. Ο ταχύτερος, και ταυτόχρονα πολυπλοκότερος, κλασσικός αλγόριθμος που είναι γνωστός μέχρι σήμερα για την παραγοντοποίηση ακεραίων μήκους άνω των 110 δεκαδικών ψηφίων είναι ο General Number Field Sieve (GNFS). Ο αλγόριθμος αυτός είναι ο καρπός πολλών ετών έρευνας, κατά τη διάρκεια της οποίας παράγονταν ολοένα και ταχύτεροι αλγόριθμοι για να καταλήξουμε μέχρι στιγμής στον αλγόριθμο GNFS.
Πρωταρχικός σκοπός της παρούσης μεταπτυχιακής εργασίας είναι η παρουσίαση του θεωρητικού μαθηματικού υπόβαθρου πάνω στο οποίο βασίζεται ο GNFS καθώς και η ακολουθιακή υλοποίηση της βασικής εκδοχής του αλγορίθμου. Ως γλώσσα υλοποίησης επιλέχθηκε η C++. Η υλοποίηση έγινε σε συνεργασία με τον συμφοιτητή μου και αγαπητό φίλο Χρήστο Μπακογιάννη, όπου στα πλαίσια της μεταπτυχιακής του εργασίας πραγματοποιήθηκε η μεταφορά της ακολουθιακής υλοποίησης του αλγορίθμου σε παράλληλο κατανεμημένο περιβάλλον χρησιμοποιώντας το Message Passing Interface (MPI). Ο πηγαίος κώδικας της υλοποίησης καθώς και σχετικές πληροφορίες υπάρχουν online στη σελίδα http://kmgnfs.cti.gr.
Σημειώνεται πως για την ευκολότερη και απρόσκοπτη ανάγνωση της εργασίας αυτής, ο αναγνώστης θα πρέπει να έχει ένα βαθμό εξοικείωσης με βασικές έννοιες της θεωρίας αριθμών, της αλγεβρικής θεωρίας αριθμών και της γραμμικής άλγεβρας. |
| author2 |
Σπυράκης, Παύλος |
| author_facet |
Σπυράκης, Παύλος Καραπάνος, Νικόλαος |
| format |
Thesis |
| author |
Καραπάνος, Νικόλαος |
| author_sort |
Καραπάνος, Νικόλαος |
| title |
Η μέθοδος παραγοντοποίησης ακεραίων αριθμών number field sieve : θεωρία και υλοποίηση |
| title_short |
Η μέθοδος παραγοντοποίησης ακεραίων αριθμών number field sieve : θεωρία και υλοποίηση |
| title_full |
Η μέθοδος παραγοντοποίησης ακεραίων αριθμών number field sieve : θεωρία και υλοποίηση |
| title_fullStr |
Η μέθοδος παραγοντοποίησης ακεραίων αριθμών number field sieve : θεωρία και υλοποίηση |
| title_full_unstemmed |
Η μέθοδος παραγοντοποίησης ακεραίων αριθμών number field sieve : θεωρία και υλοποίηση |
| title_sort |
η μέθοδος παραγοντοποίησης ακεραίων αριθμών number field sieve : θεωρία και υλοποίηση |
| publishDate |
2010 |
| url |
http://nemertes.lis.upatras.gr/jspui/handle/10889/3735 |
| work_keys_str_mv |
AT karapanosnikolaos ēmethodosparagontopoiēsēsakeraiōnarithmōnnumberfieldsievetheōriakaiylopoiēsē AT karapanosnikolaos theintegerfactorizationalgorithmnumberfieldsievetheoryandimplementation |
| _version_ |
1771297162000334848 |
