Πεπερασμένα Σώματα και Κρυπτογραφία 639


Ακαδημαϊκό έτος 2011-2012



Ώρες διδασκαλίας: Δευτέρα 9-11 Τετάρτη 9-11 Γ23

Βαθμολογία:

Έτσω Τ o βαθμός της τελικής εξέτασης, Π ο βαθμός της προόδου και Α ο βαθμός των ασκήσεων. Ο τελικός βαθμός TB θα προκύψει από τον τύπο:
TB=max(T,0.7 T_0.3Π)+0.1Α

Αξιολόγηση:

Παρακαλώ κάντε τον κόπο να αξιολογήσετε (ανώνυμα) το μάθημα εδώ . Η αξιολόγηση λήγει στις 16 Ιουνίου.

Φυλλάδια Ασκήσεων

  • 1ο Φυλλάδιο Παράδοση 3 Απριλίου 2012 Λύσεις
  • 2ο Φυλλάδιο Παράδοση 30 Απριλίου 2012 Λύσεις
  • 3ο Φυλλάδιο Παράδοση 21 Μαΐου 2012 Λύσεις

    • Ηλεκτρονικές σημειώσεις Μαθήματος

    Στην e-class έχουν αναρτηθεί σημειώσεις από φοιτητές. Τις διαβάζουμε με επιφύλαξη γιατί δεν έχουν επεξεργαστεί.
    Επίσης μετά από προσφορά συμφοιτητή σας το παραπάνω κείμενο θα δίνεται και σε μορφή pdf γραμμένο σε latex . To παραπάνω pdf θα το βλέπω προσεκτικά για λάθη και εγώ και μάλλον θα γράφω και έγω. Το αρχείο θα ανανεώνεται κάθε εβδομάδα.

    Περιεχόμενο Μαθήματος

  • Στοιχειώδης αριθμοθεωρία, ύπαρξη και μοναδικότητα πεπερασμένων σωμάτων.
  • Τετραγωνικά υπόλοιπα και ο νόμος αντιστροφής του Gauss.
  • Απλά κρυπτοσυστήματα (του Καίσαρα, με πίνακες, με ομοπαραλληλικούς μετασχηματισμούς, εκθετικά).
  • Κρυπτοσυστήματα ανοικτού κλειδιού (public key), RSA. Knapsack.
  • Μέθοδοι παραγοντοποίησης ακεραίων.
  • Ελλειπτικές καμπύλες και σχετικά κρυπτοσυστήματα.

    • Διδακτικά Βιβλία

  • Δ. Βάρσος: Στοιχεία Αλγεβρικής Θεωρίας Κωδίκων, Εκδόσεις Σοφία.
  • W. Stein Elementary Number Theory: Primes, Congruences, and Secrets Springer Verlag (Νομίμως ελεύθερο στον προηγούμενο σύνδεσμο).
    • Το κομμάτι της θεωρίας που σχετίζεται με τα πεπερασμένα σώματα μπορεί να μελετηθεί από το παράρτημα του βιβλίου του κ. Βάρσου. Υπάρχει και σε βασικά βιβλία Άλγεβρας.

    Ημερολόγιο Μαθήματος:

    Δευτέρα 12 Μαρτίου 2012 Εισαγωγή στο αντικείμενο του μαθήματος. Ορισμοί δακτυλίου, ακεραίας περιοχής, ιδεώδους, σώματος. Οι πεπερασμένες ακ. περιοχές είναι σώματα. Οι ακέραιοι mod N.
    Τεταρτη 14 Μαρτίου 2012 Ιδεώδη του Ζ. Ο μέγιστος κοινός διαιρέτης ως γεννήτορας ιδεώδους. Μονάδες του δακτυλίου Ζ/ΝΖ. Η συνάρτηση φ του Euler.
    Ομομορφισμοί δακτυλίων, πυρήνας. Χαρακτηρισμός 1-1 ομομορφισμών μέσω του πυρήνα. 1ο θεώρημα ισομορφισμών για δακτυλίους.
    Η χαρακτηριστική ακέραιας περιοχής R ως γεννήτορας του πυρήνα του ομομορφισμού Z->R, 1_Ζ-> 1_R. Οι ακέραιες περιοχές έχουν χαρακτηριστική πρώτο αριθμό.
    Χαρακτηριστική πεπερασμένων σωμάτων. Επεκτάσεις σωμάτων, πλήθος στοιχείων σε πεπερασμένου βαθμού επεκτάσεις. Κάθε πεπερασμένο σώμα έχει δύναμη πρώτου πλήθος στοιχεία.
    Δευτέρα 19 Μαρτίου 2012 Υπενθύμιση βασικών εννοιών στον δακτύλιο πολυωνύμων μίας μεταβλητής πάνω από σώμα.
    Διαφοροποίηση της ισότητας πολυωνύμων και της ισότητας των αντιστοίχων συναρτήσεων σε σώματα πεπερασμένης χαρακτηριστικής.
    Διαίρεση με πηλίκο και υπόλοιπο, τα ιδεώδη είναι κύρια.
    Ανάγωγα στοιχεία, ορισμός μεγίστου κοινού διαιρέτη, αλγόριθμος του Ευκλείδη.
    Τετάρτη 21 Μαρτίου 2010 Το ελάχιστο κοινό πολλαπλάσιο ως γεννήτορας τομής ιδεωδών.
    Ορισμός αλγεβρικού, υπερβατικού στοιχείου. Αλγεβρικές επεκτάσεις. Οι πεπερασμένου βαθμού επεκτάσεις είναι αλγεβρικές αλλά όχι αντίστροφα.
    Το "όνειρο του πρωτοετούς" στην πεπερασμένη χαρακτηριστική. Το μικρό Θεώρημα του Fermat σε πεπερασμένα σώματα.
    Δευτέρα 26 Μαρτίου 2012 Το σώμα ριζών ενός πολυωνύμου. Η πολ/κή ομάδα των αντιστρεψίμων στοιχείων ενός σώματος είναι κυκλική. Πρωταρχικές ρίζες, πρωταρχικά πολυώνυμα. Το πρόβλημα του αντιστρόφου λογαρίθμου. Παραδείγματα.
    Τετάρτη 28 Μαρτίου 2012 Υπάρξη των πεπερασμένων σωμάτων με p^n ως σώματα ριζών των πολυωνύμων x^{p^n}-x. Χαρακτηρισμός και πλήθος υποσωμάτων πεπερασμένων σωμάτων.
    Δευτέρα 2 Απριλίου 2012 Ανάγωγα πολυώνυμα σε πεπερασμένα σώματα. Ο αυτομορφισμός του Frobeniuus δρα πάνω στις ρίζες. Πρωταρχικά στοιχεία.
    Τετάρτη 4 Απριλίου 2012 Πλήθος αναγώγων πολυωνύμων συγκεκριμένου βαθμού. Ο τύπος αντιστροφής του Moebius.
    Δευτέρα 23 Απριλίου 2012 Ρίζες της μονάδας πάνω σε πεπερασμένα σώματα.
    Τετάρτη 25 Απριλίου 2012 Λύση ασκήσεων
    Δευτέρα 30 Απριλίου 2012 Το σύμβολο του Legendre και ο τετραγωνικός νόμος αντιστροφής. Απόδειξη με αθροίσματα Gauss.
    Τετάρτη 2 Μαΐου 2012 Αλγόριθμος ύψωσης σε δύναμη mod p. Ένα κριτήριο για το αν ένας αριθμός είναι πρώτος βασισμένο στo μικρό θεώρημα του Fermat.
    Τετάρτη 9 Μαΐου 2012 Κριτήριο ψευδοπρώτων, αριθμοί του Carmichael. Ανταλλαγή κλειδιών κατά Diffie-Hellman. Η επίθεση του ενδιάμεσου. Το πρόβλημα του διακριτού λογαρίθμου.
    Δευτέρα 14 Μαΐου 2012 Σύστημα δημόσιου κλειδιού RSA. Αλγόριθμοι παραγοντοποίησης όταν οι δύο πρώτοι διαιρέτες του n είναι κοντά, όταν το φ(n) είναι γνωστό και όταν είναι γνωστοί οι εκθέτες κρυπτογράφησης και αποκρυπτογράφησης.
    Δευτέρα 21 Μαΐου 2012 Εισαγωγή στην Θεωρία των Ελλειπτικών καμπυλών. Ιστορική αναδρομή. Ελλειπτικές καμπύλες πάνω από διάφορα σώματα. Ο νόμος ομάδας σε ελλειπτικές καμπύλες.
    Τετάρτη 23 Μαΐου 2012 Λύση Ασκήσεων