Υπολογιστική Θεωρία Αριθμών Εξάμηνο 4ο Μαθήματα Επιλογής
  • Περιγραφή

    Εκκρεμεί

  • Διδάσκοντες

    Μανές Κ.

  • Υπολογισμός Βαθμού

    Απαλλακτικές Εργασίες 100%

  • Βιβλίο/-α

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

  • Ύλη

    • Διαιρετότητα, πρώτοι αριθμοί, ΜΚΔ, ΕΚΠ, αλγόριθμοι και πολυπλοκότητα αριθμητικών πράξεων.
    • Αλγόριθμος Ευκλείδη και εκτεταμένος αλγόριθμος Ευκλείδη.
    • Γραμμικές Διοφαντικές Εξισώσεις.
    • Πρώτοι αριθμοί: κατανομή των πρώτων αριθμών, επώνυμοι πρώτοι αριθμοί.
    • Ισοτιμίες: η συνάρτηση φ του 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.
    • Το πρόβλημα του διακριτού λογαρίθμου (πολυπλοκότητα, αλγόριθμοι εύρεσης).

  • Εξέταση

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

  • Σημειώσεις

  • Φροντιστήριο

  • Χρήσιμοι Σύνδεσμοι