Υπολογιστική Θεωρία Αριθμών 2019-2020

Ώρες διαλέξεων: Τρίτη 12.15 - 15.00, Αίθουσα Α001 (ΝΚ).
Ώρες γραφείου: Τετάρτη 14.15 - 15.00, Γραφείο 542.
Διδάσκων: Κων/νος Μανές, kmanes@unipi.gr, τηλ. γραφείου 210-4142313.

Τρόπος εξέτασης και αξιολόγησης:
Θα δοθούν απαλλακτικές προγραμματιστικές εργασίες (ατομικές ή ομαδικές).
Παράλληλα, θα δοθούν κατά τη διάρκεια του εξαμήνου 2 ομάδες άλυτων ασκήσεων, η κάθε μια από τις οποίες θα συνεισφέρει μισή μονάδα επιπλέον στον τελικό βαθμό.

Διδακτέα ύλη:
-Διαιρετότητα, πρώτοι αριθμοί, ΜΚΔ, ΕΚΠ, αλγόριθμοι και πολυπλοκότητα αριθμητικών πράξεων.
-Αλγόριθμος Ευκλείδη και εκτεταμένος αλγόριθμος Ευκλείδη.

-Γραμμικές Διοφαντικές Εξισώσεις.
-Πρώτοι αριθμοί: κατανομή των πρώτων αριθμών, επώνυμοι πρώτοι αριθμοί.
-Ισοτιμίες: η συνάρτηση φ του Euler, Θεωρήματα Lagrange, Fermat, Euler, Κινέζικο Θεώρημα Υπολοίπων, ο αλγόριθμος RSA.
-Πρωταρχικές ρίζες, υπόλοιπα δυνάμεων, τετραγωνικά υπόλοιπα, τα σύμβολα Legendre και Jacobi, υπολογισμός του συμβόλου Jacobi.
-Εύρεση τετραγωνικής ρίζας modn (αλγόριθμοι εύρεσης για n πρώτο).
-Πιστοποίηση πρώτων αριθμών: Κριτήριo Fermat, αριθμοί Carmichael, κριτήρια Solovay-Strassen και Miller-Rabin.
Παραγοντοποίηση μεγάλων ακεραίων: αλγόριθμος του Fermat, αλγόριθμοι p-1 και ρ του Pollard, αλγόριθμος του Dixon, αλγόριθμος συνεχών κλασμάτων, quadratic sieve, number field sieve.
-Το πρόβλημα του διακριτού λογαρίθμου (πολυπλοκότητα, αλγόριθμοι εύρεσης).

Σύγγραμα μαθήματος:
V. Shoup, Μια υπολογιστική εισαγωγή στη θεωρία αριθμών και την άλγεβρα, Κλειδάριθμος, 2005.

Προτεινόμενη Βιβλιογραφία:
1) Δ. Πουλάκης, Υπολογιστική θεωρία αριθμών, Κάλλιπος, 2016.
2) Α. Αντωνιάδης και Α. Κοντογεώργης, Θεωρία αριθμών και εφαρμογές, Κάλλιπος, 2015.
3) T. Apostol, Εισαγωγή στην αναλυτική θεωρία αριθμών, Gutenberg, 1986.
4) D. Bressoud and S. Wagon, A course in computational number theory, Wiley, 2008.
5) H. Cohen, Advanced topics and in computational number theory, Springer, 2000.
6) Δ. Δεριζιώτης, Μια εισαγωγή στη θεωρία αριθμών, Σοφία, 2007.
7) M. Lewinter and J. Meyer, Elementary number theory with programming, Wiley, 2016.
8) H. Niederreiter and A. Winterhof, Applied number theory, Springer, 2015.
9) W. Stein, Elementary number theory: primes, congruences, and secrets. A computational approach, Springer, 2010.
10) S. Y. Yan, Computational number theory and modern cryptography, Wiley, 2013.