BREAKING

7

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

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

prime

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

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

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

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

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

7 Comments

  • 11 Νοεμβρίου 2013 at 10:23

    Όπως λέει και ο Θανάσης , ο αριθμός 12 γράφεται ως 2*2*3 :)

  • akis
    28 Οκτωβρίου 2013 at 06:34

    Δεν ξέρω αν είναι σωστό η λάθος το άρθρο. Δεν καταλαβαινω όμως, τι σχέση έχουν αυτά τα άρθρα με το περιεχόμενο
    του σάιτ.

  • TGM
    28 Οκτωβρίου 2013 at 03:37

    Abraham +1

  • TGM
    28 Οκτωβρίου 2013 at 03:37

    αντιφατικό γιατί…?

  • Abraham
    27 Οκτωβρίου 2013 at 23:31

    Άσχετο σχόλιο θα έλεγα εγώ γιατί το άρθρο μια χαρά ενδιαφέρον το βρήκα και έμαθα και κάτι που δεν ήξερα.

  • Θανάσης
    26 Οκτωβρίου 2013 at 10:57

    ο αριθμός 12 μπορεί να γραφτεί ως 2*2*3… :)

  • dimiko
    26 Οκτωβρίου 2013 at 02:55

    Άσχετο άρθρο,ακατάλυπτο και αντιφατικό.