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