Γιατί είναι τόσο σημαντικοί οι πρώτοι αριθμοί;

Ας ξεκινήσουμε από τα μαθηματικά των "σχολικών" μας χρόνων. "Πρώτος" θεωρείται κάθε φυσικός αριθμός, μεγαλύτερος του 1, του οποίου μόνοι φυσικοί διαιρέτες είναι ο εαυτός του και το 1. Αυτό, όπως καταλαβαίνετε, αποκλείει αυτόματα όλους τους ζυγούς αριθμούς
(που είναι μεγαλύτεροι του 2) από το να είναι πρώτοι αριθμοί, όπως και κάθε πολλαπλάσιο του 3, του 4, του 5 κ.ο.κ. Παρ' όλα αυτά, οι πρώτοι αριθμοί είναι πρακτικά ατελείωτοι και, παρόλο που γίνονται λιγότερο συχνοί όσο προχωρούμε στην κλίμακα, συνεχίζουν να υπάρχουν έως και το... άπειρο.

Υπάρχει όμως και κάτι ακόμη σημαντικό που αφορά τους πρώτους αριθμούς. Όπως ορίζει το"θεμελιώδες θεώρημα της αριθμητικής", κάθε φυσικός αριθμός μεγαλύτερος από το 1μπορεί να αναλυθεί σε ένα γινόμενο πρώτων αριθμών (παραγόντων) με μοναδικό τρόπο. Έτσι, για παράδειγμα, ο αριθμός 12 μπορεί να γραφτεί ως 2*3*3, με το 2 και το 3 να είναι και οι δύο πρώτοι αριθμοί.

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

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

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

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

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

[via]