Τι είναι λοιπόν οι πρώτοι αριθμοί; Είναι πολύ απλό! Πρώτος αριθμός είναι ένας φυσικός αριθμός μεγαλύτερος του 1 που δεν έχει θετικούς διαιρέτες άλλους πέρα από τον εαυτό του και το 1. Το 8 είναι πρώτος αριθμός; Όχι γιατί οι διαιρέτες του είναι το 1, το 2, το 4 και το 8. Μήπως είναι το 7; Ναι γιατί το 7 διαιρείται μόνο με το 1 και με τον εαυτό του. Τόσο απλά! Οι αριθμοί που δεν είναι πρώτοι, λέγονται σύνθετοι αριθμοί.
Υπάρχουν κάποιες ενδείξεις ότι υπήρχε μια μικρή γνώση περί πρώτων αριθμών στην αρχαία Αίγυπτο αλλά οι πρώτες ουσιαστικές μελέτες έχουν βρεθεί σε κείμενα από την Αρχαία Ελλάδα με πρωτεργάτες τον Ευκλείδη και τον Ερατοσθένη. Μάλλον όμως παρά-ήταν μπροστά οι τύποι κι έτσι δεν ασχολήθηκε κανείς με τους πρώτους αριθμούς μέχρι τον 17ο αιώνα όπου ο Pierre de Fermat διατύπωσε το γνωστό σήμερα ως «μικρό θεώρημα του Φερμά» το οποίο κλασσικά, δεν αξιώθηκε να αποδείξει κι έβγαλαν το φίδι από την τρύπα ο Leibniz με τον Euler. Anyway… θα τον κράξω άλλη στιγμή τον Φερμά.
Σύμφωνα με το θεμελιώδες θεώρημα αριθμητικής, ένα από τα πιο σημαντικά θεωρήματα της θεωρίας αριθμών, κάθε θετικός ακέραιος μεγαλύτερος του 1, μπορεί να αναλυθεί ως προϊόν του γινομένου πρώτων παραγόντων με τρόπο μοναδικό. Π.χ αν αναλύσουμε σε γινόμενο πρώτων παραγόντων (παραγοντοποίηση) τον αριθμό 78, παίρνουμε \(2\cdot 3\cdot 13\). Κανένα άλλο γινόμενο πρώτων αριθμών δεν μπορεί να δώσει τον αριθμό 78, γι’ αυτό και είναι μοναδικό. Το μόνο που μπορεί να αλλάξει είναι η σειρά τον αριθμών στον πολλαπλασιασμό όπως είναι φυσικό. Το θεώρημα όμως δεν δίνει καμία πληροφορία για το πώς μπορούμε να παραγοντοποιήσουμε σε πρώτους αριθμούς. Το μόνο που κάνει είναι ότι μας λέει με σιγουριά πως η παραγοντοποίηση σε πρώτους αριθμούς είναι εφικτή.
Πώς λοιπόν μπορούμε εύκολα να παραγοντοποιήσουμε αριθμούς; Η πιο χρονοβόρα αλλά εύκολη στην κατανόηση μέθοδος, είναι αυτή των δοκιμαστικών διαιρέσεων. Η μέθοδος αυτή, δοκιμάζει να δει αν ένας ακέραιος \(n\) (δηλαδή ο αριθμός που θέλουμε να παραγοντοποιήσουμε), μπορεί να διαιρεθεί με οποιονδήποτε αριθμό. Προφανώς, δεν αξίζει να δοκιμάσουμε να διαιρέσουμε με αριθμούς μεγαλύτερους του \(n\) όπως επίσης δεν υπάρχει λόγος να διαιρέσουμε με πολλαπλάσια αριθμών που έχουν αποκλειστεί ήδη. Αν π.χ δούμε ότι ο αριθμός μας δεν διαιρείται με το 2, δεν υπάρχει λόγος να δοκιμάσουμε να διαιρέσουμε με το 4 και το ίδιο κάνουμε με το 3 και τα πολλαπλάσιά του κ.ο.κ. Έτσι, μπορούμε να μειώσουμε την προσπάθειά μας διαιρώντας μόνο με πρώτους αριθμούς. Οι υποψήφιοι παράγοντες του \(n\) δεν χρειάζεται να είναι μεγαλύτεροι του \(\sqrt{n}\) διότι αν το \(n\) διαιρείται με έναν αριθμό \(p\), τότε \(n=p\cdot q\) και αν το \(q\) είναι μικρότερο του \(p\) τότε θα έπρεπε να έχουμε εντοπίσει νωρίτερα ότι το \(q\) διαιρεί το \(n\) ή κάποιον πρώτο παράγοντα του \(q\). Τέλος, μπορούμε να υπολογίσουμε ένα όριο για τους πρώτους παράγοντες. Υποθέτουμε ότι \(P\left ( i \right )\) είναι ο \(i\)ος πρώτος αριθμός έτσι ώστε \( P\left ( 1 \right )=2\), \( P\left ( 2 \right )=3\), \( P\left ( 3 \right )=5\) κ.ο.κ. Τότε ο τελευταίος πρώτος αριθμός που αξίζει να δοκιμάσουμε αν διαιρεί το \(n\) είναι ο \(P\left ( i \right )\) όπου \(P\left ( i+1 \right )^{2}> n\). Εδώ, η ισότητα θα σήμαινε ότι το \(P\left ( i+1 \right )\) είναι παράγοντας. Έτσι, οι αριθμοί 2, 3 και 5 είναι αρκετοί για δοκιμές μέχρι \(n=48\). «Μα το τετράγωνο του 5 μας κάνει 25! Πώς γίνεται να είναι αρκετό μέχρι το 48;!» σε ακούω να λες. Τα καλά νέα είναι το κατάλαβες τα μαθηματικά. Σκέψου όμως λίγο παραπάνω! Ο επόμενος πρώτος αριθμός, είναι το 7 και το τετράγωνό του μας κάνει 49. Άρα τους αριθμούς από το 26 μέχρι το 48 ποιος τους καλύπτει; Αφού το τετράγωνο του 7 μας κάνει 49, τότε οι προηγούμενοι πρώτοι αριθμοί είναι αρκετοί για να μας καλύψουν μέχρι το 48. Το ίδιο ισχύει και για \(n=25\) όπου οι αριθμοί 2 και 3 είναι αρκετοί.
Είδαμε λοιπόν πώς μπορούμε να αποκλείσουμε αρκετούς αριθμούς από τι δοκιμές μας αλλά παρ’ όλ’ αυτά, η διαδικασία παραμένει χρονοβόρα γιατί οι πρώτοι αριθμοί που χρησιμοποιούνται στην κρυπτογραφία, δεν είναι διψήφιοι και τριψήφιοι αλλά μερικών εκατοντάδων ψηφίων. Φαντάσου πόσες δοκιμές θα πρέπει να κάνουμε! Ας σκεφτούμε όμως την διαδικασία των δοκιμαστικών διαιρέσεων και γενικά την παραγοντοποίηση που μόλις αναλύσαμε. Τι κάναμε στην ουσία; Πήραμε έναν τυχαίο αριθμό και προσπαθήσαμε να βρούμε πόσοι και ποιοι αριθμοί τον διαιρούν. Ακριβώς τον ίδιο τρόπο δεν θα μπορούσε να χρησιμοποιήσουμε ώστε να βρούμε αν ένας αριθμός είναι πρώτος; Αν η παραγοντοποίηση δεν έβγαζε αποτέλεσμα, θα σήμαινε αυτόματα ότι έχουμε πρώτο αριθμό. Έχουμε κοινώς ένα απλό Primality Test, δηλαδή ένα τεστ που εξετάζει κατά πόσο ένας αριθμός είναι πρώτος ή όχι. Δεν ξέρω την ελληνική ορολογία οπότε βολέψουμε την αγγλική!
Τα πιο δημοφιλή Primality Tests ονομάζονται Probabilistic Tests τα οποία, πέρα από τον αριθμό \(n\) που δοκιμάζεται, χρησιμοποιούν και κάποιους άλλους αριθμούς \(a\) οι οποίοι επιλέγονται τυχαία από κάποιον δειγματικό χώρο. Τα tests που χρησιμοποιούν τυχαίους αριθμούς, δεν πρόκειται ποτέ να δείξουν έναν πρώτο αριθμό ως σύνθετο αλλά είναι πιθανό να δείξουν έναν σύνθετο αριθμό ως πρώτο. Μπορούμε να μειώσουμε την πιθανότητα αυτού του λάθους επαναλαμβάνοντας το τεστ με διάφορες ανεξάρτητες τιμές για το \(a\). Το πιο απλό Probabilistic Test είναι το μικρό θεώρημα του Φερμά, το οποίο λειτουργεί ως εξής: Παίρνουμε έναν ακέραιο \(n\), επιλέγουμε έναν ακέραιο \(a\) ώστε το \(n\) και το \(a\) να είναι πρώτοι προς αλλήλους και υπολογίζουμε το \(a^{n-1}\equiv n\). Αν το αποτέλεσμα είναι διάφορο του 1, τότε ο \(n\) είναι σύνθετος. Αν είναι 1 τότε το \(n\) πιθανόν να είναι πρώτος αριθμός. Το Primality Test όμως του Φερμά είναι απλά ένα ευρετικό τεστ. Κάποιοι σύνθετοι αριθμοί, όπως οι αριθμοί του Carmichael, θα εμφανίζονται πάντα ως «πιθανόν πρώτος» άσχετα με το \(a\) που θα επιλέξουμε. Όπως και να ‘χει όμως, είναι ένα πολύ καλό τεστ για όταν χρειάζεται να εξετάσουμε αριθμούς πολύ γρήγορα, όπως στην περίπτωση του αλγόριθμου RSA. Ένα λίγο πιο σύνθετο τεστ είναι το Miller-Rabin Primality Test το οποίο λειτουργεί ως εξής: Παίρνουμε έναν ακέραιο \(n\) και επιλέγουμε έναν ακέραιο \(a\) τέτοιο ώστε \(a\)<\(n\). Έστω \(2^{s}d=n-1\) όπου \(s\) θετικός ακέραιος και \(d\) περιττός θετικός ακέραιος. Αν:
\(a^{d}\not\equiv 1 \left ( mod \hspace{2 mm} n \right )\)
και
\(a^{2^{r}d}\not\equiv -1 \left ( mod \hspace{2 mm}n \right )\) για όλα τα \(0\leq r\leq s-1\)
τότε το \(n\) είναι σύνθετος και το \(a\) είναι «μάρτυρας» της συνθετότητας. Αλλίως, το \(n\) μπορεί να είναι πρώτος αλλά μπορεί και όχι.
Με όλα αυτά που έχουμε μάθει μέχρι τώρα, πόσο δύσκολη είναι τελικά η παραγοντοποίηση σε πρώτους αριθμούς; Καλές οι δοκιμές και τα τέστ αλλά αν έχουμε έναν αριθμό 200 ψηφίων, πόσο χρόνο θέλουμε για να τον παραγοντοποιήσουμε σε πρώτους αριθμούς; Για να το απαντήσουμε αυτό, πρέπει πρώτα να εξετάσουμε τον αριθμό που θέλουμε να παραγοντοποιήσουμε. Το μέγεθός του σίγουρα παίζει ρόλο αλλά υπάρχουν περιπτώσεις που π.χ το 100 να παραγοντοποιείται εύκολα ενώ το 101 να θέλει πάρα πολύ χρόνο. Οι «χειρότεροι» αριθμοί είναι αυτοί που προέρχονται από το γινόμενο δύο πρώτων αριθμών. Αν ένας μεγάλος αριθμός μεγέθους \(b\)-bit είναι το γινόμενο δύο πρώτων αριθμών περίπου ίσου μεγέθους, τότε δεν υπάρχει μέχρι στιγμής κανένας αλγόριθμος που να μπορεί να τον παραγοντοποιήσει σε πολυωνυμικό χρόνο. Ο καλύτερος αλγόριθμος μέχρι στιγμής είναι ο General Number Field Sieve (GNFS) ο οποίος για να παραγοντοποιήσει έναν αριθμό \(n\) ο οποίος αποτελείται από \(\left [ log_{2}n \right ]+1\) bits χρειάζεται:
\[exp\left ( \left ( \sqrt[3]{\frac{64}{9}}+o\left ( 1 \right ) \right ) \left ( ln \hspace{2 mm}n \right )^{\frac{1}{3}}\left ( ln \hspace{2 mm}ln \hspace{2 mm}n \right )^{\frac{2}{3}} \right )=L_{n}\left [ \frac{1}{3},\sqrt[3]{\frac{64}{9}} \right ]\]
(σε L-notation) όπου ln είναι ο λογάριθμος με βάση \(e\). Ο αλγόριθμος αυτός κατάφερε να παραγοντοποιήσει στα τέλη του 2009 τον μεγαλύτερο (μέχρι στιγμής) ήμι-πρώτο αριθμό, τον RSA-768 ο οποίος είναι ένας αριθμός μεγέθους 768-bit με 232 δεκαδικά ψηφία. Για να γίνει αυτή η παραγοντοποίηση, συνεργάστηκαν πολλά ινστιτούτα και τους πήρε 2 χρόνια για να τα καταφέρουν. Αν προσπαθούσαμε να τον παραγοντοποιήσουμε σε έναν καθημερινό υπολογιστή, θα χρειαζόμασταν 2.000 χρόνια! Υπάρχει πάντως ένα τυπάκι, ο Peter Shor ο οποίος το 1994 ανακάλυψε έναν αλγόριθμο που θα μπορούσε να παραγοντοποιήσει σε πολυωνυμικό χρόνο αλλά μόνο σε κβαντικούς υπολογιστές. Που να βρει όμως κβαντικό υπολογιστή για να τρέξει τον αλγόριθμό του το ’94; Εδώ με δυσκολία βρίσκαμε κανονικούς! Έπρεπε να περιμένει μέχρι το 2001 όπου ο πρώτος 7-qubit υπολογιστής παραγοντοποίησε τον εξωφρενικό αριθμό 15 με τον αλγόριθμό του.
Aaanyway. Απ’ όλ’ αυτά, καταλαβαίνουμε ότι βρίσκουμε εύκολα πρώτους αριθμούς αλλά δύσκολα τους παραγοντοποιούμε! Εκεί ακριβώς λοιπόν πατάει και ο αλγόριθμος RSA ο οποίος χρησιμοποιείται σχεδόν απ’ όλα τα βαρβάτα συστήματα κρυπτογράφησης και που θέλω να καταλήξω από την αρχή του άρθρου αλλά σε πάω μέσω Λαμίας. Επειδή όμως μου βγήκε λίγο μεγάλο το άρθρο, θα γράψω για το RSA αλλού! ΧΑ!
Recent Comments