Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Ιδιότητες αρχικών ριζών πρώτων αριθμών και εφαρμογές

Konidakis Ioannis

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/37AC6B13-2596-4AEE-B751-51D4BADB1933-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.94431-
Γλώσσαen-
Μέγεθος46 pagesen
Μέγεθος1.9 megabytesen
ΤίτλοςProperties of primitive roots of prime numbers and applicationsen
ΤίτλοςΙδιότητες αρχικών ριζών πρώτων αριθμών και εφαρμογέςel
ΔημιουργόςKonidakis Ioannisen
ΔημιουργόςΚονιδακης Ιωαννηςel
Συντελεστής [Επιβλέπων Καθηγητής]Karystinos Georgiosen
Συντελεστής [Επιβλέπων Καθηγητής]Καρυστινος Γεωργιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Bletsas Aggelosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Μπλετσας Αγγελοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Samoladas Vasilisen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Σαμολαδας Βασιληςel
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electrical and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών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 Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2023-01-04-
Ημερομηνία Δημοσίευσης2022-
Θεματική ΚατηγορίαPrimitive roots of prime numbersen
Θεματική ΚατηγορίαLehmer pseudo-random number generatoren
Θεματική ΚατηγορίαDiscrete logarithmen
Βιβλιογραφική Αναφορά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, 2022en
Βιβλιογραφική ΑναφοράΙωάννης Κονιδάκης, "Ιδιότητες αρχικών ριζών πρώτων αριθμών και εφαρμογές", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2022el

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά