|
|
| Κωδικός Πόρου |
000410152 |
| Τίτλος |
The number field sieve and its applications in factorization |
| Άλλος τίτλος |
Το κόσκινο αλγεβρικών σωμάτων αριθμών και παραγοντοποίηση |
|
Συγγραφέας
|
Δουλγεράκης, Εμμανουήλ
|
|
Σύμβουλος διατριβής
|
Αντωνιάδης, Ιωάννης
|
| Περίληψη |
Από την στιγμή που εισήχθη η κρυπρογραφία δημοσίου κλειδιού έχουν αναπτυχθεί αρκετά κρυπτοσυστήματα αυτού του τύπου. Τα πε¬ρισσότερα από αυτά τα κρυπτοσυστήματα βασίζουν την ασφάλειά τους στην δυσκολία ενός εκ των δύο παρακάτω προβλημάτων, της παραγο-ντοποίησης ακεραίων και το πρόβλημα του διακριτού λογάριθμου. Ένα από τα πρώτα κρυπτοσυστήματα δημοσίου κλειδιού που αναπτύχθηκε ήταν το RSA το οποίο εισήχθη το 1977 από τους RonRivest, Adi Shamir και Leonard Adleman και χρησιμοποιείται ευρέως. Αυτό το κρυπτοσύ-στημα βασίζει την ασφάλεια του στην δυσκολία του προβλήματος της παραγοντοποίησης. Οπότε για να εξεταστεί η ασφάλεια τέτοιου είδους κρυπτοσυστημάτων τα προβλήματα της παραγοντοποίησης και του δια¬κριτού λογάριθμου εξετάστηκαν εκτενώς τα τελευταία 40 χρόνια. Ένας αλγόριθμος που προέκυψε από αυτές τις μελέτες ήταν το Κόσκινο Αλ-γεβρικών Σωμάτων Αριθμών. Καθώς αυτός είναι ο αλγοριθμός με τα μεγαλύτερα ρεκόρ στην παραγοντοποίηση ακεραίων αυτή τη στιγμή επιλέγουμε να μελετήσουμε αυτόν.
Ο σκοπός της παρούσης μεταπτυχιακής εργασίας είναι να παρουσιά¬σει το Κόσκινο Αλγεβρικών Σωμάτων Αριθμών και το μαθηματικό του υπόβαθρο. Ο αλγόριθμος αυτός αρχικά εισήχθη ως αλγόριθμος παρα¬γοντοποίησης. Πιο συγκεκριμένα η πρώτη έκδοση του αλγόριθμου μπο¬ρούσε μόνο να παραγοντοποιήσει ακέραιους n της μορφής n = re — s με r, s μικρούς θετικούς ακέραιους. Αυτός ο αλγόριθμος είναι το αντικεί-μενο μελέτης του πρώτου κεφαλαίου της εργασίας. Για να έχουμε μια αίσθηση της δύναμης του αλγόριθμου δίνουμε δυο παραδείγματα παρα¬γοντοποίησης που έγιναν με την χρήση του. Η πρώτη του επιτυχία ήταν η πλήρης παραγοντοποίηση του έννατου αριθμού του Fermat F9 = 22 +1 το 1993. Εκτός από αυτό έχει καταφέρει να παραγοντοποιήσει τον αριθμό n = 21061 — 1 ο οποίος έχει 320 ψηφία το 2012. Καθώς μεταγενέ¬στερες παραλλαγές του αλγόριθμου βασίζονται σε αυτήν προσπαθούμε να την περιγράψουμε με κάθε δυνατή λεπτομέρια. Ο κύριος στόχος αυτού του αλγόριθμου είναι η κατασκευή μιας ισοτιμίας τετραγώνων τέτοια ώστε x2 = y2 (mod n) και x ψ ±y (mod n). Για να το καταφέρει αυτό επιχειρεί να βρεί "αρκετά" λεία στοιχεία ως πρός μια βάση παρα-γοντοποίησης και έπειτα να βρεί έναν συνδιασμό τους ο οποίος θα μας δώσει μια ισοτιμία τετραγώνων. Για να περιγράψουμε τον αλγόριθμο χρειαζόμαστε πολλά αποτελέσματα της αλγεβρικής θεωρίας αριθμών, κάποια από την γραμμική άλγεβρα και ακόμα και από την θεωρία γρα¬φημάτων. Στο πρώτο κεφάλαιο αναφέρουμε όλη τη θεωρία που χρεια¬ζόμαστε και αποδεικνύουμε αρκετά αποτελέσματα. Τέλος δίνουμε ένα μικρό παράδειγμα ώστε να γίνουν πιο κατανοητά όσα περιγράψαμε στις πρηγούμενες ενότητες.
Το δεύτερο κεφάλαιο ασχολείται με το Γενικό Κόσκινο Αλγεβρικών Σωμάτων Αριθμών. Αυτό είναι μια παραλλαγή του αλγορίθμου που πε¬ριγράψαμε στο πρώτο κεφάλαιο και μπορεί να παραγοντοποιήσει τυ¬χαίους ακέραιους. Παρόλο που είναι πιο αργό από τον αλγόριθμο που περιγράψαμε στο κεφάλαιο 1 παραμένει ο πιο γρήγορος αλγόριθμος που έχουμε για ακέραιους με περισσότερα από 110 ψηφία. Επίσης κα¬τέχει το ρεκόρ της πααγοντοποίησης του RSA — 768 το οποίο έχει 232 ψηφία .
RSA — 768 =1230186684530117755130494958384962720772853569595334792197 3224521517264005072636575187452021997864693899564749427740 6384592519255732630345373154826850791702612214291346167042 9214311602221240479274737794080665351419597459856902143413
Η παραγοντοποίηση του RSA — 768 ολοκληρώθηκε στο τέλος του 2009 και διήρκησε περίπου 3 χρόνια.
RSA — 768 =3347807169895689878604416984821269081770479498371376856891 2431388982883793878002287614711652531743087737814467999489
Χ3674604366679959042824463379962795263227915816434308764267
6032283815739666511279233373417143396810270092798736308917
Στο δεύτερο κεφάλαιο περιγράφουμε όλες τις τροποποιήσεις που εμπε¬ριέχονται σε αυτή την παραλλαγή του αλγόριθμου και αποδεικνύουμε το μαθηματικό υπόβαθρο που χρειαζόμαστε. Τέλος δίνουμε ένα μικρό πα¬ράδειγμα παραγοντοποίησης χρησιμοποιώντας το Γενικό Κόσκινο Αλ¬γεβρικών Σωμάτων Αριθμών.
|
| Φυσική περιγραφή |
78 σ. ; : ; 30 εκ. |
| Γλώσσα |
Αγγλικά |
| Θέμα |
Algebraic number theory |
|
Cryptography |
|
Κρυπτογραφία |
| Ημερομηνία έκδοσης |
2017-07-21 |
| Συλλογή
|
Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Μαθηματικών και Εφαρμοσμένων Μαθηματικών--Μεταπτυχιακές εργασίες ειδίκευσης
|
|
|
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
|
| Εμφανίσεις |
444 |
The number field sieve and its applications in factorization
