Αναζήτηση

Πλοήγηση

• Κοινότητες
• Συγγραφείς
• Έτος
• Τίτλοι
• Θέματα

Ο Χώρος μου

• Είσοδος

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

Konidakis Ioannis

Πλήρης Εγγραφή

---

Περίληψη

Σε αυτήν την εργασία αποδεικνύουμε κάποιες ιδιότητες των αρχικών ριζών των πρώτων αριθμών και τις χρησιμοποιούμε για να κατασκευάσουμε έναν αλγόριθμο ο οποίος λειτουργεί ως μια γεννήτρια Lehmer ψευδο-τυχαίων αριθμών, καθώς και ως μία μέθοδος επίλυσης του προβλήματος του διακριτού λογαρίθμου. Ειδικότερα, χρησιμοποιούμε διάφορα μοτίβα που εμφανίζονται κατά την έκθεση αρχικών ριζών για να επιτύχουμε τον υπολογισμό ολόκληρης της ακολουθίας δυνάμεων αρχικών ριζών ενός πρώτου αριθμού χρησιμοποιώντας κυρίως προσθέσεις αντί για πολλαπλασιασμούς. Ο νέος αλγόριθμος που αναπτύσσουμε έχει τρεις διαφορετικές μορφές, βασιζόμενες στα τρία διαφορετικά βήματα αρχικοποίησης που έχουν. Χρησιμοποιούμε τον αλγόριθμό μας αρχικά ως μια γεννήτρια Lehmer ψευδο-τυχαίων αριθμών και τον συγκρίνουμε με τον brute-force αλγόριθμο ο οποίος χρησιμοποιεί πολλαπλασιασμούς, επιτυγχάνοντας καλά αποτελέσματα και για τις τρεις μορφές αρχικοποίησης. Τέλος, χρησιμοποιούμε τον αλγόριθμό μας ως μία μέθοδο επίλυσης του διακριτού λογαρίθμου, συγκρίνοντάς τον με τον αλγόριθμο Baby Step - Giant Step. Τα αποτελέσματα δείχνουν ότι καμία μορφή του αλγορίθμου μας δεν μπορεί να είναι ανταγωνιστική σε αυτή την εφαρμογή εναντίον του Baby Step - Giant Step. Όμως, ο αλγόριθμός μας θα μπορούσε να εφαρμοστεί και στον ίδιο τον Baby Step - Giant Step αλγόριθμο ώστε πιθανώς να μειωθεί ακόμα το συνολικό κόστος του.

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

Υπηρεσίες