Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/37AC6B13-2596-4AEE-B751-51D4BADB1933 | - |
| Αναγνωριστικό | https://doi.org/10.26233/heallink.tuc.94431 | - |
| Γλώσσα | en | - |
| Μέγεθος | 46 pages | en |
| Μέγεθος | 1.9 megabytes | en |
| Τίτλος | Properties of primitive roots of prime numbers and applications | en |
| Τίτλος | Ιδιότητες αρχικών ριζών πρώτων αριθμών και εφαρμογές | el |
| Δημιουργός | Konidakis Ioannis | en |
| Δημιουργός | Κονιδακης Ιωαννης | el |
| Συντελεστής [Επιβλέπων Καθηγητής] | Karystinos Georgios | en |
| Συντελεστής [Επιβλέπων Καθηγητής] | Καρυστινος Γεωργιος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Bletsas Aggelos | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Μπλετσας Αγγελος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Samoladas Vasilis | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Σαμολαδας Βασιλης | el |
| Εκδότης | Πολυτεχνείο Κρήτης | el |
| Εκδότης | Technical University of Crete | en |
| Ακαδημαϊκή Μονάδα | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Ακαδημαϊκή Μονάδα | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Περίληψη | 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. | en |
| Περίληψη | Σε αυτήν την εργασία αποδεικνύουμε κάποιες ιδιότητες των αρχικών ριζών των πρώτων αριθμών και τις χρησιμοποιούμε για να κατασκευάσουμε έναν αλγόριθμο ο οποίος λειτουργεί ως μια γεννήτρια Lehmer ψευδο-τυχαίων αριθμών, καθώς και ως μία μέθοδος επίλυσης του προβλήματος του διακριτού λογαρίθμου. Ειδικότερα, χρησιμοποιούμε διάφορα μοτίβα που εμφανίζονται κατά την έκθεση αρχικών ριζών για να επιτύχουμε τον υπολογισμό ολόκληρης της ακολουθίας δυνάμεων αρχικών ριζών ενός πρώτου αριθμού χρησιμοποιώντας κυρίως προσθέσεις αντί για πολλαπλασιασμούς. Ο νέος αλγόριθμος που αναπτύσσουμε έχει τρεις διαφορετικές μορφές, βασιζόμενες στα τρία διαφορετικά βήματα αρχικοποίησης που έχουν. Χρησιμοποιούμε τον αλγόριθμό μας αρχικά ως μια γεννήτρια Lehmer ψευδο-τυχαίων αριθμών και τον συγκρίνουμε με τον brute-force αλγόριθμο ο οποίος χρησιμοποιεί πολλαπλασιασμούς, επιτυγχάνοντας καλά αποτελέσματα και για τις τρεις μορφές αρχικοποίησης. Τέλος, χρησιμοποιούμε τον αλγόριθμό μας ως μία μέθοδο επίλυσης του διακριτού λογαρίθμου, συγκρίνοντάς τον με τον αλγόριθμο Baby Step - Giant Step. Τα αποτελέσματα δείχνουν ότι καμία μορφή του αλγορίθμου μας δεν μπορεί να είναι ανταγωνιστική σε αυτή την εφαρμογή εναντίον του Baby Step - Giant Step. Όμως, ο αλγόριθμός μας θα μπορούσε να εφαρμοστεί και στον ίδιο τον Baby Step - Giant Step αλγόριθμο ώστε πιθανώς να μειωθεί ακόμα το συνολικό κόστος του. | el |
| Τύπος | Διπλωματική Εργασία | el |
| Τύπος | Diploma Work | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2023-01-04 | - |
| Ημερομηνία Δημοσίευσης | 2022 | - |
| Θεματική Κατηγορία | Primitive roots of prime numbers | en |
| Θεματική Κατηγορία | Lehmer pseudo-random number generator | en |
| Θεματική Κατηγορία | Discrete logarithm | en |
| Βιβλιογραφική Αναφορά | Ioannis Konidakis, "Properties of primitive roots of prime numbers and applications", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2022 | en |
| Βιβλιογραφική Αναφορά | Ιωάννης Κονιδάκης, "Ιδιότητες αρχικών ριζών πρώτων αριθμών και εφαρμογές", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2022 | el |
Copyright © DIAS 2013
