Πρώτος θεωρείται κάθε φυσικός αριθμός, μεγαλύτερος του 1 και έχει ως μοναδικούς διαιρέτες τον εαυτό του και το 1. Οι πρώτοι αριθμοί είναι άπειροι και γίνονται όλο και λιγότερο συχνοί όσο προχωράμε προς μεγαλύτερους αριθμούς (κάντε μεγέθυνση στην προηγούμενη εικόνα για να δείτε τους πρώτους αριθμούς από το 1 μέχρι το 1200 – είναι σημειωμένοι με κόκκινο).
Υπάρχει όμως και κάτι ακόμη σημαντικό που αφορά τους πρώτους αριθμούς. Όπως ορίζει το “θεμελιώδες θεώρημα της αριθμητικής”, κάθε φυσικός αριθμός μεγαλύτερος από το 1 μπορεί να αναλυθεί σε ένα γινόμενο πρώτων αριθμών (παραγόντων) με μοναδικό τρόπο. Έτσι, για παράδειγμα, ο αριθμός 45 μπορεί να γραφτεί ως 3*3*5, με το 3 και το 5 να είναι και οι δύο πρώτοι αριθμοί.
Οι πρώτοι αριθμοί απασχόλησαν από την αρχαιότητα τους Έλληνες και τους Κινέζους μαθηματικούς. Το «κόσκινο» του Ερατοσθένη (240 π.Χ.) είναι η αρχαιότερη μέθοδος ελέγχου αν ένας αριθμός είναι πρώτος. Ωστόσο, ο χρόνος υπολογισμού της μεθόδου την καθιστά απαγορευτική για πολύ μεγάλους αριθμούς.
Οι πρώτοι αριθμοί έχουν κρίσιμο ρόλο στη σύγχρονη κρυπτογραφία. Επομένως, η επινόηση γρήγορων μεθόδων για έλεγχο του κατά πόσον ένας αριθμός είναι πρώτος είναι ιδιαίτερα σημαντική. Ως τώρα οι γνωστές γρήγορες μέθοδοι (αλγόριθμοι) για το πρόβλημα αυτό είχαν την ατέλεια να αποδέχονται μια μικρή πιθανότητα λάθους απαντήσεως (ή μη απαντήσεως).
Επιστήμονες της Πληροφορικής έλυσαν πρόσφατα ένα θεμελιώδες πρόβλημα του κλάδου επινοώντας μια μέθοδο με την οποία ένας υπολογιστής μπορεί, γρήγορα και χωρίς αβεβαιότητα, να διαπιστώσει αν ένας αριθμός είναι πρώτος, δηλαδή αν διαιρείται ακριβώς μόνο από τον εαυτό του και τη μονάδα.
Ας σημειωθεί εδώ ότι ο έλεγχος του αν ένας αριθμός είναι πρώτος είναι απαραίτητο συστατικό μέρος της ευρύτατα χρησιμοποιούμενης μεθόδου κρυπτογραφίας RSA, που χρησιμοποιείται κυρίως για την ασφάλεια ηλεκτρονικών συναλλαγών στο Διαδίκτυο.
Η ασφάλεια της μεθόδου RSA εξαρτάται από τη δυσκολία της εύρεσης πρώτων παραγόντων ενός αριθμού. Η νέα μέθοδος των επιστημόνων, δεν φαίνεται να επιλύει αυτό το πρόβλημα της παραγοντοποίησης μεγάλων αριθμών, και έτσι η αξία της μεθόδου RSA είναι ακόμη αρκετά μεγάλη.
Κατά συνέπεια, ενώ είναι σχετικά εύκολο να βρούμε αν ένας αριθμός είναι πρώτος, παρ’ όλα αυτά είναι αρκετά δύσκολο να αναλύσουμε (παραγοντοποιήσουμε) έναν μεγάλο αριθμό σε γινόμενο πρώτων παραγόντων. Αυτό δυσκολεύει όλο και περισσότερο (ακόμα και για υπολογιστές), όσο μεγαλύτερος γίνεται ο αριθμός μας.
Πάντως είναι γεγονός ότι η εξέλιξη της χρησιμοποίησης της κρυπτογραφίας ολοένα αυξάνεται, καθιστώντας πλέον αξιόπιστη τη μεταφορά της πληροφορίας για διάφορους λειτουργικούς σκοπούς.
Μερικές από τις εφαρμογές της κρυπτογραφίας είναι οι παρακάτω: ασφάλεια συναλλαγών σε τράπεζες και δίκτυα ΑΤΜ, Κινητή και σταθερή τηλεφωνία, Στρατιωτικά και Διπλωματικά δίκτυα, Συστήματα συναγερμών, Δορυφορικές εφαρμογές (δορυφορική τηλεόραση), Word Wide Web (διαδίκτυο – παγκόσμιος ιστός), κλπ.