damianosk2001's blog

απο το http://eisatopon.blogspot.gr/

Απο το eisatopon

Επιλέγετε έξι τυχαίους αγώνες από το κουπόνι του στοιχήματος. Πηγαίνετε σ’ ένα παράνομο γραφείο στοιχημάτων (ιδανική περίπτωση για να παίξετε πάσης φύσεως στοιχήματα). Λέτε στον υπάλληλο ότι επιθυμείτε να παίξετε τους αγώνες 1 και 2 με απόδοση α, όπου 0<α<1. Ο υπάλληλος τρελαίνεται. Καλά, θα παίξετε έναν αγώνα με απόδοση, ας πούμε 0,8; Προσπαθεί να σας εξηγήσει ότι αν βάλετε 100 ευρώ θα πάρετε πίσω μόλις 80, αν παίξετε έναν μόλις αγώνα, ενώ θα πάρετε πίσω μόλις 0,8*0,8*100 = 0,64*100 = 64 ευρώ αν παίξετε δύο μαζί αγώνες. Το αφεντικό του κλείνει το μάτι, οπότε ο υπάλληλος αναγκάζεται να δεχτεί το άδικο (για σας) στοίχημα.
Μάλιστα, μόλις παίξετε το πρώτο δελτίο με τους δύο πρώτους αγώνες (με απόδοση α ο καθένας, θυμίζω με 0<α<1), συμπληρώνετε άλλα δύο δελτία. Στο δεύτερο δελτίο παίζετε τους αγώνες 3 και 4 με απόδοση β για τον καθένα και στο τρίτο δελτίο παίζετε τους αγώνες 5 και 6 με απόδοση γ για τον καθένα. Προσοχή, απαιτείται τα β και γ να είναι μικρότερα του 1. Ο υπάλληλος σε συνεννόηση με το αφεντικό του δεν σας φέρνει αντίρρηση. Γι’ αυτούς (και για το φτωχό τους το μυαλό, το δικό τους, αλλά και των μαθηματικών ανά τους αιώνες) το κέρδος είναι βέβαιο.
Έχετε δώσει ήδη 100 ευρώ Χ 3 δελτία = 300 ευρώ και όλο το μαγαζί σας κοιτάζει χαμογελώντας (οι καλοθελητές έχουν προλάβει και έχουν διαρρεύσει σε όλους τους «παίκτες» το ανόητο ποντάρισμα σας). Εσείς ατάραχος κάθεστε σε μία καρέκλα, παραγγέλνετε έναν γλυκό καφέ και περιμένετε με υπομονή να τελειώσουν και οι 6 αγώνες. Αμέσως μετά πηγαίνετε στον υπάλληλο και ζητάτε να σας πληρώσει. Ο υπάλληλος κάνει τους υπολογισμούς του και βρίσκει ότι σας οφείλει ( )*100 ευρώ και βγάζει από το ταμείο και σας δίνει αρκετά λιγότερα χρήματα από τα αρχικά 300 ευρώ που είχατε δώσει αρχικά (πιστεύει –και υπολογίζει– ότι < 3). Το αφεντικό και όλο το μαγαζί ξεκαρδίζονται στα γέλια.
Όμως εσείς έχετε έναν κρυφό άσο στο μανίκι σας. Βγάζετε τα θέματα των πανελληνίων των εσπερινών λυκείων και με ένα σαρδόνιο χαμόγελο τους δείχνετε το θέμα Δ3: «Αν 0<α<β<γ<1 με = 6…». Ο υπάλληλος δείχνει να ξαφνιάζεται. Παίρνει ελαφρώς θυμωμένα τα θέματα και πηγαίνει στο αφεντικό του. Όμως το big boss είναι πολύ σκληρό για να πεθάνει. Γυρνάει θριαμβευτικά και σας λέει: «Πρόκειται προφανώς για λάθος. Σίγουρα το θέμα ακυρώθηκε.»
Τότε, εσείς παίζετε τον τελευταίο άσο που έχετε στο μανίκι σας. Του δείχνετε μία ανακοίνωση με σφραγίδα του υπουργείου παιδείας που αναφέρει: «Η ασύμβατη υπόθεση που δόθηκε σε αυτό το θέμα, ουδόλως επηρεάζει την επίλυση του θέματος.». Το αφεντικό σας κοιτάζει καταϊδρωμένος. Πρέπει να υπακούσει στην «διαταγή» του υπουργείου. «Μα τον Αρχιμήδη» φωνάζει και βγάζει από την ταμιακή μηχανή 6*100 = 600 ευρώ.
Προσοχή: Μην εφαρμόσετε την παραπάνω μέθοδο σε κανένα πρακτορείο στοιχημάτων εκτός αν συνοδεύεστε από κανέναν φωστήρα του υπουργείου!

Πηγη: http://alikos.blogspot.gr/2013/05/3_2753.html

Έχουμε ένα κέρμα που φέρνει γράμματα με πιθανότητα , σταθερή αλλά άγνωστη. Μπορείτε χρησιμοποιώντας αυτό το κέρμα να κατασκευάσετε έναν αλγόριθμο με δύο δυνατές τελικές καταστάσεις και πιθανότητα 1/2 να καταλήξει σε καθεμιά από αυτές; Μπορείτε δηλαδή να προσομοιώσετε ένα τίμιο κέρμα χρησιμοποιώντας μόνο ένα κέρμα που δεν ξέρετε αν είναι τίμιο;

Πηγη:  http://kolount.wordpress.com/2012/12/07/%CE%AD%CE%BD%CE%B1-%CF%84%CE%AF%CE%BC%CE%B9%CE%BF-%CE%BA%CE%AD%CF%81%CE%BC%CE%B1/#comments

Παίρνοντας αφορμή από τις προσεχείς βουλευτικές εκλογές στην Κύπρο, επιστρέφω μετά από περισσότερο από ένα χρόνο απραξίας με ένα καινούργιο άρθρο.

Φυσικά εδώ θα ασχοληθούμε με μαθηματικά και όχι με την πολιτική. Θα παρουσιάσω λοιπόν ένα εκλογικό παράδοξο το οποίο ανακαλύφθηκε από τον οικονομολόγο Kenneth Arrow ο οποίος το 1972 τιμήθηκε και με το βραβείο Νόμπελ.

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

1) Το πρώτο πράγμα που απαιτούν οι βουλευτές είναι να ληφθεί πρόνοια για οποιοδήποτε αριθμό υποψηφίων. Κάθε πολίτης θα δικαιούται να κατατάσσει τους εκάστοτε υποψηφίους με την σειρά προτίμησης του. Η εκλογική διαδικασία πρέπει να είναι τέτοια ώστε λαμβάνοντας υπόψη τις προτιμήσεις των ψηφοφόρων να βγάζει μια τελική σειρά κατάταξης όλων των υποψηφίων.

Ο μαθηματικός τους λέει ότι υπάρχει ένας πολύ απλός τρόπος για να γίνει η εκλογική διαδικασία. Να μην λαμβάνουν καθόλου υπόψη τις ψήφους και να γίνεται κλήρωση! Αυτό οδηγεί τους βουλευτές να βάλουν και ένα νέο όρο για την εκλογική διαδικασία.

2) Η διαδικασία πρέπει να είναι ντετερμινιστική. Αν επαναληφθεί η ψηφοφορία και όλοι δώσουν τις ίδιες ακριβώς ψήφους τότε η τελική κατάταξη πρέπει να είναι η ίδια.

Και πάλι ο μαθηματικός βρίσκει μια πολύ απλή εκλογική διαδικασία. Να κατατάσσονται οι υποψήφιοι αλφαβητικα! Αφού και αυτή η λύση θεωρείται απαράδεκτη οι βουλευτές θέτουν και ένα καινούργιο όρο.

3) Αν όλοι οι ψηφοφόροι προτιμούν τον υποψήφιο Α από τον υποψήφιο Β τότε πρέπει και στην τελική κατάταξη ο Α να λάβει ψηλότερη θέση από τον Β.

Οι βουλευτές εξακολουθούν να φοβούνται τι θα γίνει αν κάποιοι ψηφοφόροι προσπαθούν να βάζουν σε χαμηλή κατάταξη αντίπαλους υποψηφίους για να ευνοηθούν οι δικοί τους. Ο μαθηματικός προτείνει να μπει ο ακόλουθος όρος

4) Για κάθε δύο υποψηφίους Α και Β, η σχετική τους κατάταξη πρέπει να εξαρτάται μόνο από την σχετική τους κατάταξη στις προτιμήσεις των ψηφοφόρων. Δηλαδή αν επαναληφθεί η ψηφοφορία και κάθε ψηφοφόρος αλλάζει την ψήφο του αλλά προτιμά τον Α από τον Β αν και μόνο αν τον προτιμούσε και στην αρχική ψηφοφορία τότε και στο τελικό αποτέλεσμα ο Α είναι πιο ψηλά από τον Β αν και μόνο αν ήταν πιο ψηλά και στην αρχική ψηφοφορία.

Παρατηρεί επίσης ο μαθηματικός ότι ο όρος (2) δεν χρειάζεται πλέον αφού είναι συνέπεια του όρου (4).

Αφού δεν υπάρχουν ενστάσεις ο μαθηματικός ξεκινάει την προσπάθειά του για να φτιάξει μια εκλογική διαδικασία που να ικανοποιεί τους παραπάνω όρους. Μετά από λίγο καιρό επιστρέφει στην βουλή και τους ανακοινώνει ότι έχει καλά και κακά νέα. Τα καλά νέα είναι ότι έχει φτιάξει μια πολύ απλή εκλογική διαδικασία που ικανοποιεί τους παραπάνω όρους: Η τελική κατάταξη να είναι ότι ψηφίσει ο ίδιος! Μετά από το σχετικό πανδαιμόνιο μπαίνει και ένας πέμπτος όρος

(5) Απαγορεύεται η ύπαρξη δικτάτορα: Απαγορεύεται να υπάρχει συγκεκριμένο άτομο ώστε όπως και αν ψηφίσουν οι υπόλοιποι να λαμβάνεται μόνο η δική του ψήφος υπόψη.

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

Ας δούμε λοιπόν μια απόδειξη αυτού του ισχυρισμού:

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

α) Υπάρχει ένας ημιδικτάτορας.
β) Κάθε ημιδικτάτορας είναι δικτάτορας.

Για να αποδείξουμε το (α), παίρνουμε μια κλίκα με τον μικρότερο αριθμό ατόμων. Θα αποδείξουμε πως η κλίκα αποτελείται από ένα μόνο άτομο. Ας υποθέσουμε πως δεν ισχύει αυτό. Έστω Α,Β υποψήφιοι ώστε όποτε η κλίκα προτιμά τον Α από τον Β, τότε στην τελική κατάταξη ο Α είναι πάνω από τον Β, και έστω Γ ένας τρίτος υποψήφιος. Έστω ένα μέλος της κλίκας. Έστω λοιπόν ότι σε μια εκλογική διαδικασία έχουμε τις εξής προτιμήσεις:

– Ο x προτιμά τον Α από τον Β και τον Γ από τον Α. (Δηλαδή ψηφίζει Β<Α<Γ.)
– Κάθε μέλος του εκτός από τον ψηφίζει Γ<Β<Α.
– Κάθε άλλος ψηφοφόρος ψηφίζει Α<Γ<Β.

(Από την υπόθεση (4), αν έχουμε ακόμη περισσότερους υποψηφίους, η τελική κατάταξη των Α,Β,Γ δεν επηρεάζεται.)

Ποια είναι λοιπόν η σχετική κατάταξη των Α,Β,Γ; Σίγουρα θα έχουμε Β<Α αφού κάθε μέλος του προτιμά τον Α από τον Β. Αν Β<Γ τότε ο είναι ημιδικτάτορας αφού όλοι οι άλλοι προτιμάνε τον Β από τον Γ. Άρα μπορούμε να υποθέσουμε ότι στην τελική κατάταξη έχουμε Γ<Β<Α και άρα Γ<Α. Αλλά τότε το αποτελεί κλίκα αφού όποτε προτιμάει τον Α από τον Γ τότε στην τελική κατάταξη ο Α είναι πιο πάνω από τον Γ. Αυτό όμως είναι άτοπο αφού ήδη βρήκαμε κλίκα με λιγότερα άτομα από την .

Μένει να δείξουμε το (β). Έστω λοιπόν ένας ημιδικτάτορας και δυο υποψήφιοι Α και Β ώστε όταν ο προτιμάει τον Α από τον Β τότε και στην τελική κατάταξη ο Α είναι πάνω από τον Β. Θα γράφουμε ότι ο είναι (Α,Β)-δικτάτορας. Αρκεί (από το (4)) να δείξουμε ότι για κάθε δυο υποψηφίους Γ και Δ ο είναι (Γ,Δ)-δικτάτορας.

(β1) Για κάθε υποψήφιο Γ (διαφορετικό από τον Α), ο είναι (Α,Γ)-δικτάτορας: Πράγματι αν ο ψηφίσει Α>Β>Γ και όλοι οι άλλοι ψηφοφόροι ψηφίσουν Β>Γ>Α στην τελική κατάταξη πρέπει να έχουμε Α>Β (αφού ο είναι (Α,Β)-δικτάτορας) και Β>Γ (από το (3)) άρα και Α>Γ.

(β2) Για κάθε δυο υποψηφίους Γ και Δ (διαφορετικούς από τον Α), ο είναι (Γ,Δ)-δικτάτορας: Πράγματι αν ο ψηφίσει Γ>Α>Δ και όλοι οι άλλοι ψηφοφόροι ψηφίσουν Δ>Γ>Α στην τελική κατάταξη πρέπει να έχουμε Α>Δ (αφού ο είναι (Α,Δ)-δικτάτορας) και Γ>Α (από το (3)) άρα και Γ>Δ.

(β3) Δουλεύοντας με παρόμοιο τρόπο, βρίσκουμε ότι για κάθε δυο υποψηφίους Γ και Δ (διαφορετικούς από τον Β), ο είναι (Γ,Δ)-δικτάτορας.

(β4) Μένει να δείξουμε ότι ο είναι (Β,Α)-δικτάτορας. Πράγματι αν Γ ένας άλλος υποψήφιος, ο ψηφίσει Β>Γ>Α και όλοι οι άλλοι ψηφίσουν Γ>Α>Β τότε αφού ο είναι (Β,Γ)-δικτάτορας η τελική κατάταξη θα είναι Β>Γ>Α και άρα ο είναι (Β,Α)-δικτάτορας.

Πηγη:   http://christofides.wordpress.com/2011/05/17/%CE%B4%CE%B7%CE%BC%CE%BF%CE%BA%CF%81%CE%B1%CF%84%CE%AF%CE%B1-%CE%AE-%CE%B4%CE%B9%CE%BA%CF%84%CE%B1%CF%84%CE%BF%CF%81%CE%AF%CE%B1/

Χρήμα: Αγαθό, που δεν μας προσφέρει κάτι της

προκοπής , παρά μόνο όταν το αποχωριζόμαστε.

Αποτελεί σημάδι πολιτισμού και διαβατήριο

για τον «καλό κόσμο».Μια περιουσία που απλά την

ανεχόμαστε»

Αμβρόσιος Πηρς

Η αφορμή ήταν ένα email το οποίο με «ενημέρωνε» για κάποια πολυεθνική εταιρεία που πουλάει διάφορα προϊόντα μέσω καταλόγων με κέρδος κάποιο ποσοστό ανάλογα με τον αριθμό των ατόμων που προσηλυτίζεις στο δίκτυο πωλήσεων .Υποσχόμενοι εξωφρενικά ποσά.…Διοργανώνουν κάθε βδομάδα σεμινάρια για τα νέα μέλη και αφού μπεις μετά προσπαθείς να προσελκύσεις νέους «πελάτες» πλασάροντας την ιδέα. Αλήθεια τα πιστεύει κάνεις ; Ε λοιπόν είναι εκπληκτικό , σε τυχαία κουβέντα στον περίγυρο μου βρήκα 3 άτομα που είχαν δοκιμάσει την τύχη τους σε παρόμοιε συστήματα. Επειδή οι καιροί είναι πονηροί ας δούμε πόσο παλιά είναι η μηχανή και πως εμπλέκονται τα μαθηματικά σε αυτή .

Όλα ξεκίνησαν στην Ρωσία την δεκαετία τού 1910 .Κάποιες επιχειρήσεις κατέφευγαν σε μια έξυπνη μέθοδο για να κατορθώσουν να πουλήσουν τα μετρίας ποιότητας προϊόντα τους .Δημοσίευαν στις εφημερίδες και σε περιοδικά ευρείας κυκλοφορίας την εξής απλή διαφήμιση:

ΔΕΚΑ ΡΟΥΒΛΙΑ ΓΙΑ ΕΝΑ ΠΟΔΗΛΑΤΟ

ΜΠΟΡΕΙ ΝΑ ΓΙΝΕΙ ΔΙΚΟ ΣΟΥ ΕΝΑ ΠΟΔΗΛΑΤΟ ΜΟΝΟ ΜΕ 10 ΡΟΥΒΛΙΑ.

ΜΟΝΑΔΙΚΗΣ ΕΥΚΑΙΡΙΑ!!!!

ΔΕΚΑ ΡΟΥΒΛΙΑ ΑΝΤΙ ΓΙΑ ΠΕΝΗΝΤΑ!

ΓΡΑΨΤΕ ΜΑΣ ΓΙΑ ΔΩΡΕΑΝ ΠΛΗΡΟΦΟΡΙΕΣ

Υπήρχαν πολλοί που τσιμπούσαν και έγραφαν για να ζητήσουν πληροφορίες .Έπαιρναν ως απάντηση έναν λεπτομερή κατάλογο.

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

Τι ακριβώς ήταν τα κουπόνια; Τι πλεονεκτήματα αποκτούσε ο κάθε αγοραστής με τα 10 ρούβλια του: Αγόραζε το δικαίωμα να ανταλλάξει το κουπόνι με πέντε ίδια .Μ άλλα λόγια , πλήρωνε την ευκαιρία να συγκεντρώσει 50 ρούβλια για την αγορά ενός ποδηλάτου, το οποίο, στην πραγματικότητα, τους στοίχιζε μόνο 10 ρούβλια, δηλαδή όσα χρήματα είχε πληρώσει για το κουπόνι. Οι νέοι κάτοχοι των κουπονιών τα αντάλλαζαν, με την σειρά τους .Κι όμως η υπόθεση –που χαρακτηρίστηκε ως χιονοστιβάδα- αποτελούσε μια προφανή άπατη, διότι πολλοί άνθρωποι έχαναν τα χρήματα τους καθώς δεν κατάφερναν να πουλήσουν τα κουπόνια που είχαν αγοράσει. Σε αυτούς στηριζόταν η επιχείρηση για να καλύψει την διαφορά. Αργά η γρήγορα , ερχόταν η στιγμή που οι κάτοχοι τους αντιλαμβάνονταν ότι τους ήταν αδύνατο να τα διαθέσουν. Πάρτε μολύβι και χαρτί και δείτε πόσο γρήγορα αυξάνει το πλήθος των κατόχων κουπονιών. Η πρώτη ομάδα αγοραστών , οι όποιοι προμηθεύονταν τα κουπόνια τους απευθείας από την επιχείρηση, δεν συναντούσε δυσκολία στο να βρει άλλους αγοραστές .Κάθε μέλος της ομάδας έφερνε στην «πυραμίδα» τέσσερεις νέους μετόχους .Αυτοί υποχρεούνταν να διαθέσουν τα κουπόνια τους σε είκοσι άλλους (4Χ5) και για να το ατυχούν έπρεπε να τους πείσουν ως προς τα πλεονεκτήματα της συγκεκριμένης αγοράς .Ας υποθέσουμε ότι όντως επιτύγχαναν να στρατολογήσουν άλλους είκοσι μετόχους. Η ορμή της χιονοστιβάδας αυξανόταν, και οι είκοσι νέοι κάτοχοι κουπονιών όφειλαν να τα μοιράσουν σε εκατό (20Χ5=100) άλλους .

Μέχρι στιγμής , ο καθένας από τους αρχικούς αγοραστές είχε παρασύρει στο παιχνίδι 1+4+20+100=125 άλλους , από τους οποίους οι 25 είχαν αποκτήσει ποδήλατα, ενώ στους υπόλοιπους 100 δινόταν η ελπίδα ότι θα αποκτήσουν – μια ελπίδα που την είχαν πληρώσει 10 ρούβλια ο καθένας

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

Οι τελευταίοι εκατό αγοραστές έπρεπε να πουλήσουν τα κουπόνια τους σε 500 νέα θύματα , τα οποία με την σειρά τους έπρεπε να στρατολογήσουν 2500 νέα. Η πόλη πλημμύριζε από κουπόνια, και κατέληγε εξαιρετικά δύσκολο να βρεθεί κάποιος που να επιθυμεί να αγοράσει. Θα διαπιστώσετε ότι το πλήθος των ανθρώπων που παρασύρονταν στην «ευκαιρία» αυξάνει με τον ίδιο ρυθμό που διαδίδεται μια φήμη.

Η πυραμίδα των αριθμών που προκύπτει λοιπόν έχει την μορφή:

1

4

20

100

500

2500

12500

62500

Αν η πόλη ήταν αρκετά μεγάλη και υποθέσουμε ότι το πλήθος των κατοίκων που ήθελαν να αγοράσουν ποδήλατο έφτανε τους 62500 τότε η χιονοστιβάδα θα εξαντλούνταν στον όγδοο γύρο. Έως τότε όλοι θα είχαν παρασυρθεί στην άπατη. Όμως , μονό το ένα πέμπτο θα αποκτούσε ποδήλατο. Οι υπόλοιποι θα είχαν στην ιδιοκτησία τους κουπόνια τα οποία δεν υπήρχε η ελαχίστη ελπίδα να διαθέσουν σε οποιονδήποτε άλλο.

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

Μετά τον ένατο γύρο έχει την μορφή

312500

1562500

7812500

39062500

Στον δωδέκατο γύρο , η πλεκτάνη θα εμπλέξει ολόκληρο τον πληθυσμό, και τα τέσσερα πέμπτα του θα έχουν εξαπατηθεί από τους εμπνευστές της. Και ποια είναι τα κέρδη: Απλώς τα 4/5 του πληθυσμού πληρώνουν τα ποδήλατα που αγόρασε το υπόλοιπο 1/5 , δηλαδή οι πρώτοι γίνονται ευεργέτες των δεύτερων. Ταυτόχρονα όμως , η εταιρεία αποκτά μια ολόκληρη στρατιά εθελοντών και πολύ δραστήριων πωλητών. Όλα αυτά συνέβαιναν εν ετει 1910 , στις μέρες τα μέσα είναι πολύ πιο σύγχρονα , το διαδίκτυο επιτρέπει επικοινωνία χωρίς καν προσωπική επαφή. Προσοχή λοιπόν σε κάθε πρόταση εύκολου πλουτισμού!

Εισαγωγή

Από την πρώτη στιγμή που άρχισαν οι άνθρωποι να επικοινωνούν μεταξύ τους δημιουργήθηκε και η ανάγκη να μεταφέρουν πληροφορίες που δεν θα ήθελαν να μάθουν κάποιοι άλλοι. Παρά πολλοί ευφάνταστοι τρόποι υπήρξαν κατά το παρελθόν ώστε να μεταφέρονται γραπτά μηνύματα καμουφλαρισμένα ή κωδικοποιημένα έτσι ώστε ακόμη και με την σύλληψη του αγγελιοφόρου να μην μπορούσε ο εχθρός να μάθει το μήνυμα.. Ήδη από την εποχή των Περσικών πολέμων έχουμε πηγές που αναφέρονται στην Λακεδαιμονική κρυπτεία (σκυτάλη). ¨Η ακόμη, ξύριζαν το κεφάλι του αγγελιοφόρου, έγραφαν το μήνυμα στο κεφάλι του και περίμεναν να μεγαλώσουν τα μαλλιά του πριν τον στείλουν να το μεταφέρει!! Μέχρι τα χρόνια των Ρωμαίων παρατηρούμε ότι στόχευαν κυρίως στην απόκρυψη του μηνύματος (όπως κάνουν και στις μέρες μας πολλοί μαθητές με τα σκονάκια σε σμίκρυνση, με αόρατο μελάνι κτλ.) Επομένως μέχρι τον 2^ο αιώνα π.Χ περίπου μιλάμε κυρίως για απόκρυψη και όχι για κρυπτογράφηση. Τον 1^ο αιώνα π.Χ.εχουμε την κρυπτογράφηση του Καίσαρα η οποία αντιστοιχεί σε κάθε γράμμα του αλφάβητου ένα διαφορετικό γράμμα του ίδιου αλφαβήτου και με βάση αυτήν την αντιστοίχιση (η οποία φυσικά είναι γνωστή στον παραλήπτη) γράφεται το μήνυμα. Σε όλη αυτή την ιστορική εξέλιξη της κρυπτογραφίας πρωταγωνιστικό ρόλο έπαιξαν τα μαθηματικά. Για παράδειγμα χάρη στη στατιστική αποκρυπτογράφησαν οι κρυπταναλυτές τα μηνύματα που κρυπτογραφούνταν με την παραπάνω μέθοδο αφού σε κάθε αλφάβητο η σχετική συχνότητα εμφάνισης κάθε γράμματος είναι περίπου σταθερή! Παρόμοιο αλλά πολύ πιο περίπλοκο ήταν και το σύστημα κρυπτογράφησης που χρησιμοποιούσαν οι Γερμανοί στον Β Παγκόσμιο πόλεμου με την μηχανή “Enigma”. Ευτυχώς μια ομάδα κρυπταναλυτών μαθηματικών μεταξύ των οποίων ήταν και ο Alan Turing κατά την διάρκεια του Β΄παγκοσμιου πολέμου κατάφερε να σπάσει και αυτόν τον τρόπο κρυπτογράφησης και έτσι πολλά πολύτιμα μηνύματα των Γερμανών έπεσαν στα χέρια των συμμάχων .

Σίγουρα όλοι μας έχουμε ακούσει για τους πρώτους αριθμούς και για το πως στη σημερινή εποχή χρησιμοποιούμε πανίσχυρους υπολογιστές για να μεγαλώσουμε το “κατάλογο” με τους ήδη γνωστούς πρώτους αριθμούς. Επίσης σίγουρα αρκετοί από εμάς θα σκεφτήκαμε ότι αν και αυτή η αναζήτηση είναι ενδιαφέρουσα δεν έχει καμία πρακτική εφαρμογή.(Δεν το σκεφτήκαμε μόνο εμείς αλλά και διαπρεπέστατοι μαθηματικοί του προηγούμενου αιώνα όπως ο G.H.Hardy!!) ’Όμως τα πράγματα δεν είναι έτσι. Η αναζήτηση πρώτων αριθμών (και η ανάλυση ενός αριθμού σε γινόμενο πρώτων παραγόντων) έχει εφαρμογή και στην κρυπτογραφία. Πολύ συχνά το ακούμε αυτό αλλά δεν γνωρίζουμε το πώς ακριβώς γίνεται! Η ακριβής παρουσίαση αυτής της μεθόδου είναι το αντικείμενο του άρθρου αυτού.

Το κρυπτοσύστημα RSA

Από τους πολλούς τρόπους κρυπτογράφησης θα εστιάσουμε στο σύστημα RSA το οποίο δημιουργήθηκε το 1977, και είναι το πλέον διαδεδομένο (με διάφορες παραλλαγές) και στηρίζεται καθαρά και μόνο στη θεωρία αριθμών.

Η λογική βασίζεται στο εξής απλή (αλλά τόσο όμορφη!!!) ιδέα:

Πώς θα παίξουμε κορώνα-γράμματα με έναν απομακρυσμένο αντίπαλο μέσω Η/Υ;

Όπως περιγράφει και ο Marcus du Sautoy στο βιβλίο του «τα mustηρια των αριθμών» όλοι οι πρώτοι αριθμοί (εκτός του 2) αν διαιρεθούν με το 4 αφήνουν υπόλοιπο 3 ή 1. Έχει αποδειχθεί ότι υπάρχουν άπειροι πρώτοι που αφήνουν υπόλοιπο 3 και άπειροι που αφήνουν υπόλοιπο 1 και μάλιστα, όπως απέδειξε ο Dirichlet, αυτοί είναι άπειροι αλλά ίσοι σε πλήθος μεταξύ τους!!! Με άλλα λόγια, αν επιλέξουμε στην τύχη έναν πρώτο αριθμό, τον διαιρέσουμε με το 4 και πάρουμε το υπόλοιπό του οι πιθανότητες να είναι 3 είναι 50% όσο ακριβώς και οι πιθανότητες να είναι 1.

Αν πάρω επομένως δυο πρώτους αριθμούς από αυτούς που αφήνουν υπόλοιπο 1 όταν διαιρούνται με το 4 (π.χ. το 17 και το 41) τότε και το γινόμενο τους αφήνει υπόλοιπο 1 αν διαιρεθεί με το 4. Αν επιλέξω δυο αριθμούς από το σύνολο αυτών που αφήνουν υπόλοιπο 3 όταν διαιρεθούν με το 4 τότε το γινόμενο τους πάλι αφήνει υπόλοιπο 1 όταν διαιρεθεί με το 4!!! Άρα αν γνωρίζω ότι το υπόλοιπο δια του 4 του γινόμενο δυο πρώτων αριθμών είναι ένα δεν μπορώ να ξέρω από ποιο σύνολο προέρχονται οι αριθμοί αυτοί!! Επομένως λέω στον αντίπαλο μου να επιλέξει το σύνολο 1=κορωνα ή το σύνολο 3=γραμματα και του ανακοινώνω το γινόμενο δυο μεγάλων πρώτων αριθμών. Αφού μου απαντήσει ποιο σύνολο επέλεξε πρέπει να του ανακοινώσω τους πρώτους που διάλεξα για να φανεί σε ποιο σύνολο ανήκουν. Του δίνω δηλαδή αρκετή πληροφορία για να δει ότι δεν τον «κλέβω» αλλά όχι τόση ώστε να μπορεί να με «κλέψει» αυτός!!!!

Με πιο απλά λόγια η ιδέα είναι ότι ενώ μας είναι πολύ εύκολο να υπολογίσουμε το γινόμενο δυο πρώτων αριθμών σε κλάσματα του δευτερόλεπτου, η αντίστροφη διαδικασία δηλαδή η παραγοντοποιηση ενός αριθμού σε γινόμενο δυο πρώτων είναι απείρως πιο χρονοβόρα αν όχι αδύνατη ακόμη και με την χρήση των πιο προηγμένων Η/Υ. Συγκεκριμένα το πρόγραμμα mathematica έχει την εντολή factorize αλλά ο χρόνος που απαιτείται για μεγάλους αριθμούς (με περισσότερα από 300 ψηφία) είναι απαγορευτικός! Ευτυχώς όπως απέδειξε ο Ευκλείδης πριν από 2400 χρόνια οι πρώτοι αριθμοί είναι άπειροι και με την βοήθεια της τεχνολογίας μπορούμε πλέον να ανακαλύπτουμε αστρονομικά μεγάλους πρώτους αριθμούς. Για παράδειγμα τον Ιανουάριο του 2013 ανακαλύφθηκε πρώτος αριθμός με περίπου 14.000.000 ψηφία!!!

Τη μέθοδο RSA επινόησαν οι Ronald L.Rivest,Adi Shamir,Leonard Adleman ( από τα αρχικά των ονομάτων τους προέκυψε και η ονομασία RSA) και παρουσιάστηκε στην καταπληκτική εργασία τους το 1977 στο Massachusetts Institute of Technology. Μάλιστα οι δημιουργοί του RSA όταν παρουσίασαν την μέθοδο είχαν κρυπτογραφήσει ένα μήνυμα χρησιμοποιώντας πρώτους με 65 ψηφία ο καθένας (και άρα το γινόμενο τους είχε 129 ψηφία) και ζήτησαν να προσπαθήσουν να το αποκρυπτογραφήσουν οι κρυπταναλυτες της εποχής τους. Το πρόβλημα λύθηκε το 1994 (17 χρόνια μετά) από 1600 συνδεδεμένους υπολογιστές μέσω ιντερνετ! Σήμερα χρησιμοποιούνται πρώτοι με 300 ψηφία ο καθένας.

Η Βασική πρόταση στην οποία στηρίζεται το κρυπτοσύστημα RSA είναι η εξής:

Αν p, q διακεκριμένοι πρώτοι και de≡1mod[(p-1)(q-1)]

Τότε (m^e)^d≡m mod(pq)

Για την απόδειξη βλ. Παράρτημα.

Παράδειγμα 1ο

• Το αρχικό βήμα αυτής της μεθόδου είναι να αντιστοιχίσουμε τα γράμματα μιας λέξης (ή πρότασης) σε αριθμούς. Πολλές φορές αντιστοιχούμε ομάδες δυο ή περισσότερων γραμμάτων (block) σε αριθμούς.
• Επιλέγουμε 2 πρώτους αριθμούς p,q και υπολογίζουμε το γινόμενό τους n=pq
• Μετά βρίσκουμε δυο αριθμούς e & d τέτοιους ώστε το γινόμενο τους να αφήνει υπόλοιπο 1 όταν διαιρεθεί με τον (p-1)(q-1)

Έστω η Ανθή και Νίκος θέλουν να επικοινωνήσουν με χρήση του RSA. H Ανθή θέλει να στείλει το m=65 στον Νίκο. Ο δε Νίκος έχει δημοσιεύσει το δημόσιο κλειδί του (n,e)=(427187,11) σε ένα δημόσιο χώρο (π.χ. στην ιστοσελίδα του). Ο Νίκος έχει διαλέξει p=677,q=631. Ισχύει μκδ(e,(p-1)(q-1))=1. Η Ανθή εκτελεί την παρακάτω ενέργεια.

Κρυπτογράφηση : m^{e} διαιρούμενο με το n δίνει υπόλοιπο c=178975 (m^{e}c mod n)

Η Ανθή στέλνει το c στον Νίκο.O Νίκος για να το αποκρυπτογραφήσει κάνει χρήση του μυστικού κλειδιού d που έχει την ιδιότητα de διαιρούμενο με το (p-1)(q-1) να δίνει υπόλοιπο 1. Eπομένως εύκολα υπολογίζει d=309731 (με Ευκλείδειο αλγόριθμο στο e και το (p-1)(q-1) βλ. παράρτημα). Tώρα ο Νίκος εκτελεί την εξής ενέργεια:

Αποκρυπτογράφηση : c^{d} διαιρούμενο με το n δίνει υπόλοιπο 65 (c^{d}65 mod n).

Παράδειγμα 2^ο (Συνοπτικό)

1. Ο χρήστης διαλέγει δυο τυχαίους πρώτους αριθμούς p, q. Έστω p=47, q=59. Τότε Ν=pq=2773.
2. Υπολογίζει την ποσότητα φ(Ν)=46*58=2668 και διαλέγει έναν τυχαίο αριθμό e μικρότερο του 2668 και πρώτο ως προς αυτόν. Έστω e=17
3. Με τον επεκταμένο αλγόριθμο του Ευκλείδη υπολογίζει τα x & y τέτοια ώστε 2668x+17y=1. (Επειδή ΜΚΔ(2668,17)=1 υπάρχουν σίγουρα τέτοιοι ακέραιοι). Εφαρμόζοντας τον αλγόριθμο του Ευκλείδη βρίσκουμε y=157. Άρα d=157.
4. Ο χρήσης κοινοποιεί σε όλους τα N και e, αλλά κρατάει μυστικό το d. Αν κάποιος ξέρει τα Ν και e δεν μπορεί να βρει το d γιατί δεν ξέρει τα p,q τα οποία κρατάει επίσης μυστικά ο χρήστης.
5. Αν κάποιος θέλει να στείλει το μήνυμα m=31, τότε κάνει τα εξής:

Κρυπτογράφηση:

c≡m^e (modN) δηλ. 587≡31^17 (mod2773)

Ο χρήστης αποκρυπτογραφεί το 587 που λαμβάνει κάνοντας χρήση του d που μόνο αυτός γνωρίζει:

Αποκρυπτογράφηση:

m≡c^d (modN) δηλαδή 31≡587^1157 (mod 2773)

Πρακτικά, μπορώ εγώ να δώσω στον συνομιλητή μου τα n και e (Τα οποία δεν με νοιάζει και αν υποκλαπούν γι αυτό άλλωστε ονομάζονται και δημόσια κλειδιά) ενώ κρατάω κρυφό για τον εαυτό μου το d. Έτσι όποτε θέλει κάποιος να μου στείλει ένα μήνυμα θα πρέπει να το υψώνει στην e και να υπολογίζει το υπόλοιπο του ως προς n ενώ εγώ για να το αποκωδικοποιήσω θα πρέπει να υψώνω το μήνυμα που λαμβάνω στην d και να υπολογίζω το υπόλοιπο του ως προς n .

Το σημαντικό στην παραπάνω διαδικασία είναι ότι αν τα p,q είναι μεγάλα τότε είναι πολύ δύσκολο να βρεθούν αν γνωρίζουμε μόνο το n και επομένως είναι πολύ δύσκολο να υπολογιστεί και ο αριθμός d που είναι απαραίτητος για την αποκωδικοποίηση. Ο Rivest υπολόγισε ότι αν ο n είναι ένας αριθμός με 125 ή 126 ψηφία ο οποίος προέκυψε από 2 πρώτους με 63 ψηφία τότε για να αναλυθεί ο n σε γινόμενο πρώτων παραγόντων θα χρειαζόντουσαν περίπου 10 τετράκις εκατομμύρια χρόνια με τις δυνατότητες της τεχνολογίας εκείνης της εποχής. Επειδή όμως η τεχνολογία συνεχώς εξελίσσεται ο χρόνος αυτός μειώνεται εκθετικά !! Μικροί αριθμοί οδηγούν σε ταχύτερους υπολογισμούς αλλά και σε πιο αδύνατη ασφάλεια. Αυτό οδηγεί στην χρήση ακόμη μεγαλύτερων αριθμών ή σε βελτιωμένες εκδόσεις του κρυπτοσυστήματος RSA.

Βέβαια κανένα κρυπτοσύστημα δεν είναι απαραβίαστο κάτι που συντηρεί τον ανταγωνισμό μεταξύ των κρυπτογράφων και των κρυπταναλυτών με τα μαθηματικά να αποτελούν το βασικό όπλο αμφοτέρων!! .

Παράρτημα

1) Ορισμός: γράφοντας a b modn εννοούμε ότι ο a όταν διαιρεθεί με το n αφήνει το ίδιο υπόλοιπο με τον b

2) Ισχύει ότι αν Μ.Κ.Δ.(r,n)=1 δηλαδή είναι σχετικά πρώτοι τότε υπάρχει k που ανήκει στο Z : rk1 modn

Άρα αν a είναι ένας αριθμός που αντιστοιχεί σ’ ένα γράμμα μιας λέξης για να τον κρυπτογραφήσουμε τον πολλαπλασιάζουμε μ’ έναν αριθμό r τέτοιο ώστε (r,n)=1. Για να κάνουμε την αποκρυπτογράφηση αρκεί να πολλαπλασιάσουμε με τον αντίστοιχο αριθμό k έτσι έχουμε:

(ar) ka(rk)a1amodn

3) Επίσης από το θ.Fermat έχουμε ότι αν (a,n)=1 τότε a^φ(n)1modn, όπου φ(n) η συνάρτηση του Euler (αν n=p*q όπου p,q πρώτοι τότε φ(n)= (p-1)(q-1))

Επομένως αν n=pq και ed=λφ(n)+1 τότε για να κρυπτογραφήσουμε τον όρο a τον υψώνουμε στην e και παίρνουμε b=a^emod, ενώ για να τον αποκρυπτογραφήσουμε υψώνουμε τον b στην d:

b^d(a^e)^d a^ed a^λφ(n)+1a^λφ(n) a(a^φ(n))^λa1^λa1aamodn

4) Απόδειξη της βασικής πρότασης:

Αφού de≡1mod(p-1)(q-1), υπάρχει k τέτοιος ώστε de≡k(p-1)(q-1)+1 δηλ. m^de=m^k(p-1)(q-1)m. Αυτό που πρέπει να δείξουμε είναι ότι m^k(p-1)(q-1)m≡m mod pq. Υπάρχουν τρεις περιπτώσεις:

α) Αν ο m διαιρείται και από το p και από το q τότε προφανώς ισχύει.

β) Ο m διαιρείται με έναν μόνο από τους p,q. Έστω ότι διαιρείται από το q και όχι από το p. Από το μικρό θεώρημα του Fermat έχουμε ότι (m^k(q-1))^p-1≡1 mod p και πολλαπλασιάζοντας με q παίρνουμε (m^k(q-1))^p-1q≡q mod pq. Όμως το m είναι πολλαπλάσιο του q και άρα m=qr για κάποιον ακέραιο r. Πολλαπλασιάζοντας την τελευταία σχέση με r έχουμε:

(m^k(q-1))^p-1qr≡qr mod pq ή m^k(p-1)(q-1)m≡m mod pq, δηλαδή το ζητούμενο.

γ) Ο m δε διαιρείται ούτε από το p ούτε από το q. Από το μικρό θεώρημα του Fermat έχουμε (m^k(q-1))^p-1≡1 mod p και επίσης (m^k(p-1))^q-1≡1 mod q, αφού και ο q είναι πρώτος. Από τις δυο τελευταίες σχέσεις συνάγεται ότι αφού το m^k(p-1)(q-1)-1 είναι πολλαπλάσιο τόσο του p όσο και του q (με p≠q) άρα θα είναι και πολλαπλάσιο του γινόμενου τους. Με άλλα λόγια m^k(p-1)(q-1)-1≡0 mod pq και πολλαπλασιάζοντας με m έχουμε

m(m^k(p-1)(q-1)-1)≡0 mod pq ή ισοδύναμα

ή m^k(p-1)(q-1)m≡m mod pq.

5) Επεκταμένος αλγόριθμος του Ευκλείδη μέσα από παραδείγματα:

Παράδειγμα 1^ο

Εστω p=3, q=5, pq=15, (p-1)(q-1)=8 και c=7

Τότε θα πρεπει να βρουμε τους ακέραιους α και d από την εξίσωση : α(p-1)(q-1)+ cd=1

8α+7d=1

8=1*7+1

7=1*7+0 Αρα ΜΚΔ=1 και πηγαίνοντας αντίστροφα έχουμε:

1=8-1*7 δηλ. α=1 και d=-1. Επειδή το d πρέπει να είναι μεταξύ του 1 και του (p-1)(q-1) παίρνουμε το ισοδύναμο του -17mod8 και άρα πρέπει να πάρουμε d=7.

Παράδειγμα 2^ο

Έστω ότι p=7, q=17 pq=119, (p-1)(q-1)=96 και c=13. Τότε:

96α+13d=1

96=7*13+5

13=2*5+3

5=1*3+2

3=1*2+1

2=1*2 Άρα ΜΚΔ(96,13)=1 και έχουμε:

1=3-1*2=3-(5-1*3)=2*3-5=2*(13-2*5)-5=2*13-5*5=2*13-5*(96-7*13)=37*13-5*96 και επομένως α=-5 και d=37.

Πράγματι 37*131mod96

Βιβλιογραφία:

1) Ιστοσελίδα του κ.Παναγοπουλου Δημήτρη (προσπέλαση: Ιανουάριος 2013)

http://www.math.uoa.gr/web/activ/magaz/teyxos2/thema5.htm

2) Ιστοσελίδα του κ.Λιμνιωτη Κωνσταντίνου (προσπέλαση Ιανουάριος 2013)

http://users.teilam.gr/~klimn/

3) Wikipedia (προσπέλαση Ιανουάριος 2013)

http://el.wikipedia.org/wiki/Κρυπτογραφια

4) Marcus du Sautoy (2010). «Τα mustηρια των αριθμών» . Εκδοτικός οίκος ΤΡΑΥΛΟΣ

5) Andrew Hodges (2007). “One to nine”. Εκδοτικός οίκος ΤΡΑΥΛΟΣ

6) Software “Wolfram Mathematica 7.0”

7)Πετρίδης Σαράντος. Διπλωματική εργασία με τίτλο: «Πρώτοι Αριθμοί: Μια ιστορική παρουσίαση από τα Αρχαία Ελληνικά Μαθηματικά μέχρι τις σύγχρονες εφαρμογές τους» Αθήνα 2011.

Η παρουσιαση μου βρισκεται εδω: https://www.dropbox.com/s/bqfdzr4l0upuhoi/%CE%A0%CE%B1%CF%81%CE%BF%CF%85%CF%83%CE%B9%CE%B1%CF%83%CE%B7%20%CE%BC%CE%BF%CF%85.ppt