Υπολογιστικη Θεωρια Αριθμων Με Εφαρμογες

Abstract

Ο σκοπός αυτής της διπλωματικής εργασίας είναι μια συνοπτική παρουσίαση της Στοιχειώδους και Αναλυτικής Θεωρίας Αριθμών με εφαρμογές στην Κρυπτογραφία.Ειδικότερα, στην Θεωρία Αριθμών, έμφαση δίνεται: στο θεμελιώδες θεώρημα της Αριθμητικής, στις βασικότερες αριθμητικές συναρτήσεις (συνάρτηση Mobius μ(n), συνάρτηση Euler φ(n), συνάρτηση σ(n) και συνάρτηση τ(n)), σε ιδιότητές τους καθώς και σε θεωρήματα τα οποία σχετίζονται με αυτές, στους τέλειους αριθμούς, στους αριθμούς Fermat, στις ισοτιμίες, στα τετραγωνικά υπόλοιπα (όπου παρουσιάζουμε βασικά θεωρήματα με κυριότερο αυτό της τετραγωνικής αντιστροφής του Gauss), στις συναρτήσεις π(x), li(x) και στη συνάρτηση ζ(s) του Riemann. Τέλος, παρουσιάζονται παραδείγματα και εφαρμογές της θεωρίας στην επίλυση προβλημάτων.Ακολούθως στην Κρυπτογραφία, παρουσιάζουμε θεμελιώδεις μεθόδους και βασικούς αλγορίθμους που αφορούν την Πιστοποίηση Πρώτων Αριθμών (όπως τους αλγορίθμους Fermat, Miller-Rabin και Solovay-Strassen), την Παραγοντοποίηση Ακεραίων σε Πρώτους Παράγοντες (όπως την μέθοδο p-1 του Pollard) και το πρόβλημα του Διακριτού Λογαρίθμου (όπως την μέθοδο ανταλλαγής κλειδιού Diffie-Hellman, τους αλγορίθμους Shanks, Pohlig-Hellman, Index Calculus και τις μεθόδους ρ και λ του Pollard.