Computational Number Theory

Abstract

The last thirty years, Number Theory has been applied in many areas of Science and Technology, as Cryptography, Coding Theory, etc. This book is an introduction to Number Theory with emphasis in its computational aspect. Its aim is to give the necessary tools for the understanding of the contemporary applications of Number Theory. The necessary knowledge for the study of the book is that of secondary education. In the first chapter, the divisibility of integers is studied and an elementary introduction to the algorithms of integers is given. Further, the Euclidian algorithm is analysed. The second chapter is devoted to continuous fractions and their properties.<br/>In the third chapter, the prime numbers are studied, some classical theorems on their distributions are proved and some special classes of prime numbers are presented. The basic properties of algebraic structures, monoids, groups, rings and fields, as well as polynomials are given in the fourth chapter. The fifth chapter, is devoted to the congruence relations of integers and their properties. Further, <br/>the linear congruences, the primitive roots, the symbols of Legendre and Jacobi are studied. Moreover, the solution of quadratic congruences is studied. Finally, the finite fields are introduced. In the sixth chapter, some classical primality tests are given and the unique deterministe polynomial time algorithm AKS is analysed. The seven chapter deals with the integer factorization and some classical algorithm are presented. Finally, the last chapter is devoted to the discrete logarithm problem and some algorithm for the computatin of discrete algorithm are given.

Η Θεωρία Αριθμών, την τελευταία τριακονταετία, έχει βρεί σημαντικές εφαρμογές σε πολλούς τομείς της επιστήμης και τεχνολογίας, όπως η Κρυπτογραφία, η Θεωρία Κωδίκων, κλπ. Το βιβλίο αυτό αποτελεί μία εισαγωγή στην Θεωρία Αριθμών με έμφαση στην υπολογιστική της πλευρά με σκοπό να δώσει τα απαραίτητα εφόδια για την κατανόηση των σύγχρονων εφαρμογών της. Απαραίτητες γνώσεις για την μελέτη του είναι αυτές της δευτεροβάθμιας εκπαίδευσης. Στο πρώτο κεφάλαιο μελετάται η διαιρετότητα των ακεραίων, δίνεται μία<br/>στοιχειώδη εισαγωγή στους αλγόριθμους ακεραίων και αναλύεται ο εκτεταμένος Ευκλείδειος αλγόριθμος. Το δεύτερο κεφάλαιο είναι αφιερωμένο στο ανάπτυγμα των πραγματικών αριθμών σε συνεχές κλάσμα και στις βασικές του ιδιότητες. Στο τρίτο κεφάλαιο εισάγονται οι πρώτοι αριθμοί. Αποδεικνύεται το θεμελειώδες θεώρημα της αριθμητικής, δίνονται εφαρμογές του, μελετώνται κλασσικά θεωρήματα επί της κατανομής των πρώτων αριθμών και εξετάζονται ειδικές κατηγορίες πρώτων. Μία παρουσίαση των βασικών αλγεβρικών δομών του μονοειδούς, της ομάδας, του δακτυλίου και σώματος, καθώς επίσης και των βασικών ιδιοτήτων των πολυωνύμων δίνεται στο τέταρτο κεφάλαιο. To πέμπτο κεφάλαιο είναι αφιερωμένο στη σχέση ισοτιμίας των ακεραίων αριθμών. Δίνονται οι βασικές ιδιότητες των ισοτιμίων, μελετάται η επίλυση των γραμμικών ισοτιμιών και των συστημάτων τους. Αποδεικνύεται σε ποιές περιπτώσεις υπάρχουν πρωτογενείς ρίζες κατά μέτρο n,<br/>εισάγονται τα σύμβολα των Legendre και Jacobi και μελετάται η επίλυση των τετραγωνικών ισοτιμιών.Τέλος εισάγονται τα πεπερασμένα σώματα. Στο έκτο κεφάλαιο δίνονται μερικοί κλασσικοί μέθοδοι πιστοποίησης πρώτου, καθώς και ο μοναδικός αιτιοκρατικός αλγόριθμος πολυωνυμικού χρόνου AKS. Το έβδομο κεφάλαιο διαπραγματεύεται την παραγοντοποίσηση ακεραίων και περιγράφονται αλγόριθμοι για την αντιμετώπισή του. Τέλος, το όγδοο κεφάλαιο είναι αφιερωμένο στο πρόβλημα του διακριτού λογαρίθμου και δίνονται μερικοί αλγόριθμοι για την επίλυσή του.