Συντάχθηκε 21-12-2022 08:14
Ενημερώθηκε:
21-12-2022 10:17
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 2041
Έναρξη: 22/12/2022 15:00
Λήξη: 22/12/2022 16:00
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΚΟΝΙΔΑΚΗ ΙΩΑΝΝΗ
με θέμα
Ιδιότητες Αρχικών Ριζών Πρώτων Αριθμών και Εφαρμογές
Properties of Primitive Roots of Prime Numbers and Applications
Εξεταστική Επιτροπή
Καθηγητής Καρυστινός Γεώργιος (επιβλέπων)
Καθηγητής Μπλέτσας Άγγελος
Αναπληρωτής Καθηγητής Σαμολαδάς Βασίλειος
Περίληψη
Σε αυτήν την εργασία αποδεικνύουμε κάποιες ιδιότητες των αρχικών ριζών των πρώτων αριθμών και τις χρησιμοποιούμε για να κατασκευάσουμε έναν αλγόριθμο ο οποίος λειτουργεί ως μια γεννήτρια Lehmer ψευδο-τυχαίων αριθμών, καθώς και ως μία μέθοδος επίλυσης του προβλήματος του διακριτού λογαρίθμου. Ειδικότερα, χρησιμοποιούμε διάφορα μοτίβα που εμφανίζονται κατά την έκθεση αρχικών ριζών για να επιτύχουμε τον υπολογισμό ολόκληρης της ακολουθίας δυνάμεων αρχικών ριζών ενός πρώτου αριθμού χρησιμοποιώντας κυρίως προσθέσεις αντί για πολλαπλασιασμούς. Ο νέος αλγόριθμος που αναπτύσσουμε έχει τρεις διαφορετικές μορφές, βασιζόμενες στα τρία διαφορετικά βήματα αρχικοποίησης που έχουν. Χρησιμοποιούμε τον αλγόριθμό μας αρχικά ως μια γεννήτρια Lehmer ψευδο-τυχαίων αριθμών και τον συγκρίνουμε με τον brute-force αλγόριθμο ο οποίος χρησιμοποιεί πολλαπλασιασμούς, επιτυγχάνοντας καλά αποτελέσματα και για τις τρεις μορφές αρχικοποίησης. Τέλος, χρησιμοποιούμε τον αλγόριθμό μας ως μία μέθοδο επίλυσης του διακριτού λογαρίθμου, συγκρίνοντάς τον με τον αλγόριθμο Baby Step - Giant Step. Τα αποτελέσματα δείχνουν ότι καμία μορφή του αλγορίθμου μας δεν μπορεί να είναι ανταγωνιστική σε αυτή την εφαρμογή εναντίον του Baby Step - Giant Step. Όμως, ο αλγόριθμός μας θα μπορούσε να εφαρμοστεί και στον ίδιο τον Baby Step - Giant Step αλγόριθμο ώστε πιθανώς να μειωθεί ακόμα το συνολικό κόστος του.
Abstract
In this work we derive a few properties of primitive roots of prime numbers and use them to generate an algorithm that functions as a Lehmer pseudo-random number generator, as well as a solution to the discrete logarithm problem. Specifically, we capitalize patterns in the exponentiation of primitive roots to achieve the calculation of the primitive root's power sequence by mainly using additions instead of multiplications. Our new generated algorithm has three different forms, their difference lying on their initialization step. We test
our algorithm as a Lehmer pseudo-random number generator against a multiplication-based brute-force algorithm, achieving satisfying results for all three initialization forms. Finally, we use our algorithm to solve the discrete logarithm problem, testing it against Shanks' Baby Step - Giant Step algorithm. The results show that Shanks' algorithm, even for small numbers, achieves a lower cost than all forms of our algorithm. However, our algorithm could be implemented in Baby Step - Giant Step to potentially reduce its total cost.
Η χρήση προστατευτικής μάσκας είναι υποχρεωτική.
