All posts by lykeio

Σας προσκαλούμε στη θεατρική μας παράσταση με θέμα : Προσφυγικό ένα διαχρονικά επίκαιρο ζήτημα, την Τετάρτη 15 Μαΐου στις 20.00

Ο Ιούλιος Καίσαρας , ο Riemann και οι πρώτοι αριθμοί

Ο Ιούλιος Καίσαρας , ο Riemann και οι πρώτοι αριθμοί

Παρίσι 1900

Στην κατάμεστη αίθουσα διαλέξεων της Σορβόννης επικράτησε ησυχία όταν ανέβηκε να μιλήσει ο David Hilbert στο διεθνές συνέδριο των Μαθηματικών.

Είχε προετοιμάσει μία τολμηρή ομιλία.

Θα αναφερόταν όχι σε αυτά που είχαν ήδη αποδειχθεί αλλά στα άγνωστα τα οποία κατά τη γνώμη του θα απασχολούσαν τη Μαθηματική κοινότητα τους επόμενους αιώνες.

Πράγματι η ομιλία του ήταν προφητική γιατί τα 23 θέματα που ανέφερε απασχόλησαν και απασχολούν τους ερευνητές ακόμα και σήμερα. Πολλά από αυτά έχουν απαντηθεί αλλά το όγδοο – η υπόθεση του Riemann- εξακολουθεί να αντιστέκεται μέχρι σήμερα.

Η περίφημη αυτή υπόθεση έχει να κάνει με την τεράστια και αέναη προσπάθεια των Μαθηματικών να βρουν μία κανονικότητα , ένα τύπο , ένα κριτήριο που να που να παράγει πρώτους , να προβλέπει τον επόμενο.Η απόδειξή της θα καλύψει τα κενά σε χιλιάδες θεωρήματα που η απόδειξή τους εξαρτάται από αυτήν.Πολλοί μαθηματικοί χρειάστηκε να την θεωρήσουν δεδομένη για να καταλήξουν στα αποτελέσματα που επεδίωκαν. Γι αυτό και δόθηκε ο όρος «υπόθεση» και όχι «εικασία»

Υπόθεση Riemann

Πράγματι από την ανάλυση πολύ μεγάλου πλήθους πρώτων δεν φαίνεται καμία (ακριβής) κανονικότητα. ’Η αν υπάρχει είναι αναπόδεικτη και απλώς εικασία

H κατανομή των πρώτων μέσα στους ακεραίους είναι ασυμπτωτική έτσι όπως υποδεικνύει το θεώρημα  lim[π(x)/(χ/logx)]=1  του x τείνοντος στο άπειρο όπου π(x) to πλήθος των πρώτων του μικρότεροι ή ίσοι του ακεραίου x από όπου μπορούμε να συμπεράνουμε ότι π(x)=χ/logx περίπου.  . Την σχέση με τον λογάριθμο πρώτος την είχε συλλάβει ο μεγάλος πρωτοπόρος των Μαθηματικών Gauss  

Ο τύπος αυτός παράγει όμως σφάλματα και ο Riemann τον βελτίωσε παράγοντας τον τύπο R(x) με λιγότερα σφάλματα.

Τέλος , ισχυρίστηκε , εισάγοντας μία μιγαδική συνάρτηση (την συνάρτηση ζ στο παράρτημα) ότι θα μπορούσε να εκμηδενίσει τα σφάλματα του R(x) χρησιμοποιώντας τα μη τετριμμένα σημεία μηδενισμού της συνάρτησης

Η υπόθεση λέει ότι οι μη τετριμμένες ρίζες της ζ-συνάρτησης έχουν κοινό πραγματικό μέρος (το ½).

Ας αρχίσουμε με τους πρώτους

Να θυμίσουμε σ’αυτό το σημείο ότι πρώτοι λέγονται οι ακέραιοι που δεν έχουν διαιρέτες (πλην το 1 και του εαυτού τους βέβαια). Μερικοί αρχικοί 2 , 3 , 5 , 7 , 11 , 13 . 17 , 19 , 23 , ….., , 2017 ,…,2027 , ……

Οι πρώτοι αποτελούν τους θεμέλιους λίθους της θεωρίας αριθμών μιας από τις πρώτες θεωρίες των Μαθηματικών από τα αρχαία ακόμα χρόνια με πολλά δυσεπίλυτα προβλήματα και δύσκολες τεχνικές.

Κάθε ακέραιος μπορεί να «χτιστεί» από πρώτους με μοναδικό πολλαπλασιασμό αυτών.

Πολλά τα ερωτήματα που μπορούν να τεθούν σχετικά και είναι σημαντικά -θα δείτε γιατί – όπως αν έχουν κάποια μορφή ή ποιοι από τους αριθμούς της μορφής 2p-1 (αριθμοί του Mersenne)

 είναι πρώτοι , οι δίδυμοι πρώτοι όπως 11 ,13 οι 17 ,19 κλπ ή  αν είναι άπειροι. Σχετικά με το τελευταίο ο Ευκλείδης απέδειξε το άπειρο πλήθος τους με ένα ωραιότατο παράδειγμα απαγωγής στο άτοπο (3η «κομψότερη» απόδειξη θεωρείται)

Σήμερα (Ιανουάριος 2019) ο μεγαλύτερος γνωστός πρώτος αριθμός είναι ο 282,589,933-1, 24,862,048 ψηφία. Βρέθηκε τον Δεκέμβριο του 2018 από το Great Internet Mersenne Prime Search (GIMPS)

Το πιο κεντρικό ίσως ερώτημα είναι πως ελέγχουμε- δοκιμάζουμε αν ένας αριθμός είναι πρώτος το οποίο είναι ισοδύναμο με το να βρούμε ένα πρώτο αριθμό.

Εχουν αναπτυχθεί διάφορα κριτήρια ελέγχου τα οποία με πιθανότητες μας λένε αν ένας αριθμός είναι πρώτος (κυριότερο το κριτήριο Miller 1975 πάλι με «συνεισφορά» του Riemann)

Το να μπορούμε λοιπόν να βρούμε (πολύ μεγάλους) πρώτους αριθμούς κυρίως όμως να παραγοντοποιήσουμε έναν μεγάλο τέτοιο είναι σήμερα κομβικής σημασίας και αποτελεί μία πολύ ενεργό ερευνητική περιοχή τόσο στα Πανεπιστήμια όσο και σε Υπηρεσίες Εθνικής Ασφάλειας. Πολλές εταιρείες  (AT&T , hwelett Packard επενδύουν χρήματα στην προσπάθεια κατανόησης των πρώτων αριθμών και της Υπόθεσης του Riemman.

Ας συνεχίσουμε με κρυπτολογία

Η αιτία είναι ότι σε αυτούς τους αριθμούς στηρίζεται σήμερα μεγάλο μέρος της κρυπτογράφησης μηνυμάτων-πακέττων-κωδικών που διακινούνται στο Διαδίκτυο και εξασφαλίζει το  ηλεκτρονικό εμπόριο  που «σέρνει χορό» δισεκατομμυρίων ανά τον κόσμο με τη σειρά του .

‘Ένα από τα κυριώτερα συστήματα κρυπτογράφησης με χρήση πρώτων αριθμών είναι το RSA (Rivest-Shamir-Adleman MIT 1978) και η δημιουργία του στηρίζεται αφενός μεν στην αδυναμία μας να απαντήσουμε σε θεμελιώδη ερωτήματα σχετικά με τους πρώτους με αποτέλεσμα να απαιτείται υπολογιστικά περίπλοκος χρόνος έτσι ώστε να «σπάσουν» οι κώδικες που τους χρησιμοποιούν και προστατεύουν τον αριθμό π.χ. της πιστωτικής μας κάρτας Όσο περισσότερο πλησιάζουμε στην απόδειξη της υπόθεσης Riemman τόσο λιγότερο ασφαλείς γίνονται οι συναλλαγές μας. Επίσης Ο RSA στηρίζεται  στην ανακάλυψη του Fermat ανακάλυψη -πριν από 450 περίπου χρόνια- σχετικά με τους πρώτους την οποία θα παρουσιάσουμε παρακάτω.

Πριν όμως να πούμε ότι κρυπτογραφία είναι η μελέτη μεθόδων κωδικοποίησης μηνυμάτων ώστε αυτά να μπορούν να «διαβαστούν» – αποκωδικοποιηθούν μόνο από τον επιθυμητό παραλήπτη και όχι από άλλους που μπορεί να τα υποκλέψουν.

To αντίθετο δηλ. η μελέτη τρόπων αποκωδικοποίησης ενός υποκλαπέντος μηνύματος λέγεται κρυπτανάλυση.

Η κρυπτογράφηση μηνυμάτων αποτελεί βέβαια αρχαία συνήθεια με την σκυτάλη να αποτελεί ένα από τα μέσα της εποχής. Επρεπε να διπλώσει με ειδικό τρόπο ο παραλήπτης το χαρτί με τα γράμματα που ήταν τυλιγμένο στη σκυτάλη ώστε να διαβάσει το μήνυμα.

Ο Ιούλιος Καίσαρας επίσης αντικαθιστούσε κάθε γράμμα του μηνύματος με το κατά 3 θέσεις δεξιότερο κυκλικά.

Ετσι έχουμε τον τύπο y=x+3 (mod24) όπου y ο κωδικός του γράμματος x με την αρίθμηση να ξεκινά από το 0

H γραφή mod24 σημαίνει το υπόλοιπο της Ευκλείδειας διαίρεσης του y  με το 24

Για παράδειγμα το μήνυμα ΘΑ ΦΟΡΑΩ ΚΑΠΕΛΟ σύμφωνα με τον Καίσαρα αποδίδεται ως ΛΔΩΣΥΔΓΝΔΤΘΞΣ

Τι λέτε; Αν σας τύχαινε θα το βρίσκατε!

Μπορεί φυσικά να επιλεγεί όχι μόνο το 3 αλλά οποιοσδήποτε ακέραιος d  ή να περιλακεί ακόμα περισσότερο κωδικοποιώντας τα γράμματα ανά ζεύγη σύμφωνα π.χ. με το σύστημα

yi=αxi+βxi+1 (mod24)

yi+1=γxi+δxi+1 (mod24) όπου α , β ,γ , δ τέσσερεις συμφωνηθέντες αριθμοί

Αξίζει να μνημονεύσουμε σ’ αυτό το σημείο τον Αγγλο μαθηματικό Alan Turing υπό την καθοδήγηση του οποίου αποκωδικωποιήθηκε ο Γερμανικός κώδικας Enigma κατά τον 2ο Παγκόσμιο με αποφασιστικό ρόλο στην έκβαση της συμμαχικής νίκης. Η δε επιτυχία του αυτή μάλιστα κρατήθηκε -για λόγους μάλλον εθνικής ασφάλειας- μυστική για πολλά χρόνια και έτσι δεν έτυχε ο μεγάλος αυτός επιστήμονας δημόσιας αναγνώρισης ο οποίος σημειωτέον είχε καταλήξει ήδη από το 1936 σε σπουδαία θεωρητικά αποτελέσματα πριν ασχοληθεί με την κρυπτανάλυση και γι αυτό δίκαια ίσως θεωρείται από πολλούς ως ο «πατέρας του υπολογιστή» (μηχανές Turing)

Κεντρική έννοια στην αποκωδικοποίηση μηνύματος αποτελεί η έννοια του κλειδιού.Κλειδί είναι μία συγκεκριμένη πληροφορία (ο τρόπος δηλαδή) που πρέπει να κατέχει ο δέκτης του μηνύματος ώστε να μπορέσει να το αποκωδικοποιήσει . Σε όλες σχεδόν τις μεθόδους η μετάδοσή του είναι το πρόβλημα σχετικά με το πως θα μεταδοθεί με ασφάλεια.

Το πλεονέκτημα του RSA και των συναφών μεθόδων είναι ότι δεν απαιτείται μεταβίβαση κλειδιού. Είναι η λεγόμενη κρυπτογραφία κοινοποιημένου κλειδιού.

Η μέθοδος RSA με παράδειγμα

Θα συμφωνήσουμε ότι τα (26 για το αγγλικό αλφάβητο)γράμματα δηλώνονται με τους αριθμούς 00 , 02 ,……., 25

Εγώ ο παραλήπτης του μηνύματος επιλέγω δύο μυστικούς πρώτους αριθμούς π.χ. p=11 και q=13 με γινόμενο 11×13=143 (εσείς φανταστείτε δύο πρώτους με πενήντα + ψηφία ο καθένας στη πράξη με γινόμενο 100+ ψηφία).

Επιλέγω επίσης έναν αριθμό Ν π.χ. Ν=7. πρώτο προς το γινόμενο (p-1)(q-1) =10×12=120 στο παράδειγμα.  Αυτό σημαίνει ότι ο Ν δεν έχει κοινό παράγοντα ούτε με τον p-1 ούτε με τον q-1.

Υπολογίζω με τον αλγόριθμο του Ευκλείδη τον ελάχιστο θετικό ακέραιο Μ ώστε 7Μ=1(mod120) και βρίσκω Μ=103 (για λόγους οικονομίας ο Αλγόριθμος Ευκλείδειας διαίρεσης παραλείπεται).

Πράγματι 7×103=721=6×120+1 άρα 7Μ=1(mod120)

Κοινοποιώ τώρα το εξής : όποιος επιθυμεί να μου στείλει μήνυμα αντιπροσωπευόμενο από έναν διψήφιο αριθμό x θα πρέπει να μεταβιβάσει το υπόλοιπο του x103(mod143)

Ας πούμε ότι κάποιος θέλει να στείλει το μήνυμα CT που όπως αναφέρθηκε αποτελείται από τους αριθμούς 02 , 19.Θα πρέπει να υπολογίσει το υπόλοιπο της διαίρεσης 2103:143 δηλαδή το 2103 (mod143).Το ίδιο με το 19103

Με το χέρι είναι κοπιαστική εργασία όμως εύκολη σε ένα υπολογιστή. Παρακάτω θα αναφέρουμε πως  με την αριθμητική ισοτιμιών (modulo) μπορούν τα Μαθηματικά να μας το βρουν.

Εχουμε λοιπόν 2103 =63 (mod143) και 19103 =72 (mod143). Το μήνυμα που θα λάβω είναι 63,72.

Υπολογίζω τώρα 637=2 (mod143)  και 727 =19 (mod143).

Αρα καταλήγω να παίρνω το μήνυμα 02,19 δηλαδή CT .

Να σημειωθεί ότι ο καθένας που έχει πρόσβαση στο δημόσιο αυτό ευρετήριο μπορεί να μου στέλνει μηνύματα , αυτός που τα υποκλέπτει όμως δεν μπορεί να τα αποκωδικοποιήσει γιατί αγνοεί το Ν=7 (πως μπορεί να ανιχνευτεί το 7 δεν αναπτύσσεται για λόγους οικονομίας του άρθρου)

Αυτό που κοινοποιείται είναι το γινόμενο pq και αν οι p , q είναι αρκετά μεγάλοι είναι υπολογιστικά εξαιρετικά χρονοβόρο και πολύπλοκο να βρεθούν οι παράγοντες p , q λαμβάνοντας υπόψη ότι οι αριθμοί μεταβάλλονται συχνά.

Το ερώτημα στο οποίο πρέπει να απαντήσει κάποιος είναι γιατί ισχύει αυτή η μέθοδος. Δηλαδή αν ένας αριθμός (x στο παράδειγμα) κωδικοποιείται υψούμενος στη Μ δύναμη , η ύψωση του διαβιβαζόμενου αποτελέσματος σε εκθέτη Ν (modpq) θα μας δώσει τον αρχικό αριθμό.

Η αποκωδικοποίηση σχηματικά μπορεί να γραφτεί : αν y=xM τότε yN=( xM)N=x.Οι πράξεις είναι modpq

Είναι εφαρμογή του ακόλουθου θεωρήματος

Θεώρημα 1

Aν p , q δύο πρώτοι ακέραιοι και ΜΝ=1 (mod(p-1)(q-1)) τότε ( xM)N =x (modpq) του οποίου η απόδειξη στηρίζεται στο μικρό Θεώρημα Fermat (1600) που αναφέρουμε για ιστορικούς λόγους

Θεώρημα 2 (μικρό θ.F.)

Έστω p πρώτος ι. Για κάθε ακέραιο α έχουμε ότι αp=a (modp)

                        ιι. Αν ο α δεν είναι πολλαπλάσιο του p τότε αp-1=1 (modp)

ΠΑΡΑΡΤΗΜΑ

  1. Ο υπολογισμός του 2103(mod143) και του 19103(mod143) με το χέρι

Αρχικά υπολογίζουμε τις πρώτες δυνάμεις «κάτω» από το 143 όπου βέβαια το υπόλοιπο θα είναι το ίδιο το αποτέλεσμα της δύναμης

22=4 , 24=(22)2=42=16 ,

28=….=162=256 =113 (mod143)                               γιατί 256=1×143+113

216=(28)2=1132=12769  =42

232=422=1764 = 48

264= 482=2304=16

Τώρα 2103=26423224222=16x48x16x 4×2=113×98=63                                     αφού 16×16=256=113

                                               και 488=384=98

  1. Η συνάρτηση ζ του Riemann ζ(s)=1/1^s+1/2^s+1/3^s +….. όπου s μιγαδικός

Η παραπάνω συνάρτηση μηδενίζεται για τους αρνητικούς άρτιους -2 , -4 , .. και οι ρίζες αυτές χαρακτηρίζονται ως τετριμμένες

Πηγές

  1. H φύση και η δύναμη των Μαθηματικών Donald M. Davis ΠΑΝ. ΕΚΔ. ΚΡΗΤΗΣ
  2. H μουσική των πρώτων αριθμών Marcus du Sautoy εκδ. ΤΡΑΥΛΟΣ
  3. Η Μαθηματική Εμπειρία P.J.Davis – R. Hersch εκδ. ΤΡΟΧΑΛΙΑ
  4. Wikipedia
  5. https://www.mersenne.org/5.

Λαμπίρης Χρήστος

ΠΕ03