Θεωρία Αριθμών

         Εαρινό Εξάμηνο 2012

                  Η πορεία του μαθήματος μετά τις 4-4-2012 και σχετικές οδηγίες

             Τα βασικά της Θεωρίας Αριθμών, όπως διδάχθηκαν από τον κ. Αντωνιάδη μέχρι το τέλος Μαρτίου. Για τα επόμενα θα γίνει μερική χρήση των Σημειώσεων (τελευταία ενημέρωση: 13-5-2012) στις οποίες και θα παραπέμπω.
             Για τη βασική θεωρία των ισοτιμιών μελετήστε τις παραγράφους 2.1 και 2.2 (σελ. 25 και εξής). Στις σημειώσεις, συνήθως, γίνεται χρήση της λέξης “μέτρω” αντί του mod, ή modulo. Π.χ. “a ισότιμο b μέτρω m” αντί “a ισότιμο b modulo m”.

• Συνάρτηση φ του Euler (σελ. 29), η Πρόταση 2.2.2 και το θεώρημα 2.2.3 (με διαφορετική απόδειξη).

• Θεώρημα 2.2.4 (Euler και Fermat). Δόθηκαν εφαρμογές σχετικές με τον υπολογισμό του υπολοίπου της διαίρεσης μιας μεγάλης δύναμης δια ενός ακεραίου. Δείτε το παράδειγμα στη σελίδα 31. Λύθηκε η άσκηση 22, σελ. 39.
  
  Προτεινόμενες ασκήσεις: 1. Να υπολογίσετε το υπόλοιπο της διαίρεσης του 3702¹⁵⁵²² δια 37. (Απάντηση: 27)
  
  2. Να υπολογίσετε το υπόλοιπο της διαίρεσης του 55060⁵⁵⁴⁴⁴ δια 11011. (Απάντηση: 625)

• Ύψωση σε δύναμη. Εδάφιο 2.3, σελίδες 32-34.
  
  Προτεινόμενες ασκήσεις: 1. Κατασκευάσετε πίνακα για τον υπολογισμό της δύναμης a⁴⁹¹, ανάλογο με τον πίνακα της σελίδας 34.
  
  2. Κατασκευάσετε πίνακα για τον υπολογισμό της δύναμης a⁴⁵, ανάλογο με τον πίνακα της σελίδας 34.
  Επαναλάβετε τον πίνακα όταν a είναι η κλάση του 10 (mod 240) και υπολογίστε έτσι την κλάση 5⁴⁵ (mod 240).

• Κρυπτογραφική μέθοδος RSA. Εδάφιο 2.4, σελίδες 35-37.
  
  Προτεινόμενες ασκήσεις: 1. Έστω (n,e) = (527, 11) το δημόσιο κλειδί της Α. Ποιο είναι το μυστικό κλειδί d της Α;
  Υποθέστε ότι τα υπό κρυπτογράφηση μηνύματα είναι φυσικοί αριθμοί < 15. Ο Β κρυπτογραφεί τα μηνύματα 5, 7, 13 και τα στέλνει στην Α. Ποια μηνύματα θα λάβει τότε η Ακαι πώς θα τα αποκρυπτογραφήσει;
  
  Πηγαίνετε στο magma calculator και εισάγετε τον εξής κώδικα (ό,τι ακολουθεί μετά τα // είναι σχόλιο και δεν εκτελείται). Τα (n,e) είναι αυτά που εμφανίζονται στο εδάφιο 2.4 των σημειώσεων “Η κρυπτογραφική μέθοδος RSA”:

                                   Z:=Integers();
                                   n:=49144364409017;  //  Μπορείτε να εισαγάγετε οποιοδήποτε άλλο n (π.χ. Γινόμενο δύο πρώτων p,q)
                                   phin:=EulerPhi(n);  //  Υπολογίζει το φ(n) 
                                   e:=1365911;         //  Μπορείτε να εισαγάγετε οποιοδήποτε άλλο e, αρκεί να είναι πρώτο προς φ(n). Πάρετε τυχαίο e και ελέγξτε.
                                   “gcd=”,Gcd(e,n);    //  Πρέπει να σας βγάλει gcd=1 για να είναι δεκτό το e, διαφορετικά, αλλάξτε το e. 
                                   Zn:=quo< Z | n >;   //  Εδώ ορίζεται ο δακτύλιος των κλάσεων mod n.
                                   Zphin:=quo<Z|phin>; //  Εδώ ορίζεται ο δακτύλιος των κλάσεων mod φ(n).
                                   d:=1/(Zphin!e);     //  Υπολογίζεται d, τέτοιο ώστε d*e = 1 (mod φ(n))
                                   d:=Z!d;             //  Επειδή το magma βλέπει το d ως κλάση, εδώ λέμε στο magma να δει το d ως ακέραιο.
                                   crypt:=map< Z -> Z | x :-> Z!((Zn!x)^e) >; // Η συνάρτηση “κρυπτογράφησης”: Για κάθε ακέραιο x, είναι crypt(x)=x^e (mod n).
                                   apocrypt:=map< Z -> Z | x:-> Z!((Zn!x)^d)>; // Η συνάρτηση “αποκρυπτογράφησης”: Για κάθε ακέραιο y, είναι apocrypt(y)=y^d (mod n).

Φτιάξτε και δικά σας παραδείγματα παίρνοντας n=p*q με p,q πρώτους που θα διαλέξετε τυχαία με τη βοήθεια του magma. Αν δώσετε π.χ. την εντολή NthPrime(1000); (προσοχή, στο τέλος κάθε εντολής του magma το ; είναι απαραίτητο) θα σας επιστρέψει τον 1000-στό πρώτο αριθμό, που είναι ο 7919.

• Τετραγωνικά ισοϋπόλοιπα. Εδάφια 4.1, 4.2 και 4.3.
  
  Προτεινόμενες ασκήσεις: Οι ασκήσεις 1, 2, 4, 5, 6 της σελ. 66 και η άσκηση 7 της σελ. 67. Υπόδειξη για τις ασκήσεις 4, 5 και 6: Στις ασκήσεις αυτές ο N είναι της μορφής N = x² + ay². Αν p|N, τότε x² + ay² = 0 (mod p) (*). Αποδείξτε πρώτα ότι (p,y)=1 και συμπεράνατε ότι υπάρχει y' τέτοιο ώστε yy' = 1 (mod p). Πολλαπλασιάστε κατά μέλη την ισοτιμία (*) κια θα καταλήξετε σε ισοτιμία της μορφής X² = -a (mod p).
  
  
  

            Τελευταία ενημέρωση: 13-5-2012