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

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

Παράδειγμα

Η συνταγή τοποθετεί το σχετικό πρόβλημα ως εξής: Θέλεις να βρεις τους δύο πρώτους αριθμούς που το γινόμενό τους είναι ο τεράστιος περιττός Ν (διότι αν ήταν άρτιος θα τον είχαμε διαιρέσει ήδη διά του 2); Ξεκίνησε παίρνοντας στην τύχη έναν θετικό ακέραιο μικρότερο από τον Ν. Να ξέρεις ότι εδώ μπορείς να χρησιμοποιήσεις μια ήδη κατακτημένη γνώση. Τη δίνουμε κατ’ αρχάς με ένα παράδειγμα. Ας πούμε ότι έχουμε τον αριθμό 13. Διαλέγουμε έναν μικρότερό του, π.χ. τον 5. Αρχίζουμε και παίρνουμε τις δυνάμεις του 5 και συγκρίνουμε πόσο κοντά πηγαίνουν σε καθεμία από αυτές τα πολλαπλάσια του 13. Π.χ. 5¹=5 και 5=13×0+5. Εμείς ψάχνουμε για έναν συνδυασμό των 5 και 13 που θα μας έδινε υπόλοιπο 1. Αυξάνουμε τη δύναμη που υψώνουμε τον 5. Τότε είναι η σειρά του 5²=25 με 25=1×13+12. Συνεχίζουμε: 5³=125 και 125=13×9+8. Επόμενο: 5⁴=625 και 625=13×48+1. Μόλις φθάνουμε σε υπόλοιπο 1, σταματάμε και μετράμε πόσες δοκιμές έγιναν. Εδώ είναι 4. Επειδή το 4 είναι άρτιος, μας κάνει. Αν ήταν περιττός, έπρεπε να ξεκινήσουμε από την αρχή με άλλον μικρότερο του 13 και να φθάσουμε σε άρτιο αριθμό δοκιμών.

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

Πνευματική γυμναστική

1. Ζητούμε τον πεντηκοστό όρο της εξής ακολουθίας: 5, 6x, 72 x, 83 x, 94 x,…

2. Ενα ζάρι με τους αριθμούς 1, 2, 3, 4, 5, 6 στις πλευρές του, ρίχνεται διαδοχικές φορές μέχρις ότου το άθροισμα των αποτελεσμάτων που ερχόταν με κάθε ζαριά να υπερβαίνει το 12. Ζητούμε να βρεθεί αν υποθέσουμε ότι επαναλαμβάνουμε κάποιες φορές τη διαδικασία ποιο άθροισμα πάνω από το 12 έχει τις περισσότερες πιθανότητες να εμφανίζεται. Για την απάντηση δεν χρειάζεται κάποιος να έχει γνώσεις από τη θεωρία των πιθανοτήτων.

Οι λύσεις των προηγούμενων κουίζ

1. Επάνω σε μια ευθεία βρίσκονται πέντε σημεία. Μας δίδονται 10 αποστάσεις αυτών των σημείων μεταξύ τους ανά δύο, και μάλιστα με σειρά μεγέθους: 2, 4, 5, 7, 8, k, 13, 15, 17, 19. Πόσο είναι το k; Τοποθετούμε 5 σημεία (Σ1, Σ2, Σ3, Σ4, Σ5) επάνω στην ευθεία των πραγματικών αριθμών αλλά όχι εντελώς τυχαία. Το πρώτο με το τελευταίο, δηλαδή το ζευγάρι (Σ1,Σ5), θα απέχουν 19 μονάδες, τη μεγαλύτερη απόσταση που δίδεται. Στη συνέχεια κάνουμε την παρατήρηση ότι την απόσταση από το Σ1 μέχρι το Σ5 που είναι ίση με 19 έχουμε τη δυνατότητα να την έχουμε ως τρία διαφορετικά αθροίσματα. [(Σ1,Σ2)+(Σ2,Σ5)], [(Σ1,Σ3)+(Σ3,Σ5)], [(Σ1,Σ4),(Σ4,Σ5)]. Από τις δεδομένες αποστάσεις φαίνεται πως δύο από τα παραπάνω αθροίσματα που δίνουν τελικά το 19 θα είναι τα (2,17) και (4,15). Το τρίτο, επειδή δεν υπάρχει άλλο ζευγάρι να δίνει 19, καταλαβαίνουμε ότι θα είναι ή το (k,7) ή το (k,8). Δεν μπορεί να είναι το (5,k) ή το (k,13) διότι έχει δοθεί πως η τιμή του k βρίσκεται μεταξύ 8 και 13 και δεν βγαίνουν τα αθροίσματα μέχρι το 19. Οπότε η τιμή του k θα είναι ή 11(11+8=19) ή 12(12+7=19). Στη συνέχεια ξεκινούμε αντίθετα. Από το πώς έχουμε τοποθετήσει έως τώρα τα σημεία στην ευθεία προκύπτει ότι ξεκινώντας από το Σ5 μέχρι το Σ2 η απόσταση είναι 17. Αυτή μπορεί να αποτελείται από τα [(Σ5,Σ4)+(Σ4,Σ2)] ή από τα [(Σ5,Σ3)+(Σ3,Σ2)]. Το ένα άθροισμα μπορεί να αντιστοιχεί στο (4,13) αλλά το άλλο θα είναι ένα από τα (5,k), (7,k), (8,k). Αυτά για να δίνουν άθροισμα 17 απαιτούν τιμές για το k αντίστοιχα 12, 10, 9. Πριν είχε βρεθεί ότι το k θα είναι ή 12 ή 11, άρα τελικά θα πρέπει να k=12.

2. Δύο τρένα ξεκινούν στις 7 το πρωί το ένα από τον σταθμό Α για να φθάσει στον σταθμό Β και το άλλο από τον σταθμό Β για να φθάσει στον Α. Οι σταθμοί είναι σε ευθεία γραμμή και τα τρένα κινούνται με σταθερές ταχύτητες. Το πρώτο τρένο φθάνει στον προορισμό του σε 8 ώρες και το δεύτερο σε 12 ώρες. Ποια χρονική στιγμή συναντά το ένα το άλλο; Υπάρχουν διάφοροι τρόποι για τη λύση, ένας από τους πλέον κατανοητούς κατά τη γνώμη μας είναι ο εξής: Αφού έχουν σταθερή ταχύτητα, το πρώτο τρένο κάθε ώρα καλύπτει το (1/8) της διαδρομής και το δεύτερο το (1/12). Επομένως κάθε ώρα η απόσταση μεταξύ τους μειώνεται κατά (1/8)+(1/12)=(5/24). Εδώ αν θέλουμε να είμαστε ακόμα πιο αναλυτικοί, εξηγώντας ίσως το πρόβλημα σε μικρούς μαθητές, το απλούστερο είναι να καταφύγουμε στη μέθοδο των τριών. Λέμε ότι σε 1 ώρα καλύπτονται τα (5/24) της απόστασής τους, σε πόση ώρα θα καλυφθούν τα (24/24); Και προκύπτει ότι αυτό θα γίνει σε (24/5) ώρες, δηλαδή σε 4 ώρες και 48 λεπτά (συμμιγείς αριθμοί).

Έντυπη έκδοση Το Βήμα