Πρώτος αριθμός

Υπάρχει μια απλή μέθοδος για την εύρεση μιας λίστας πρώτων αριθμών. Τη δημιούργησε ο Ερατοσθένης. Έχει το όνομα κόσκινο του Ερατοσθένη. Πιάνει τους αριθμούς που δεν είναι πρώτοι (όπως ένα κόσκινο) και αφήνει τους πρώτους αριθμούς να περάσουν.

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

Η μέθοδος είναι πάντα η ίδια:

1. Σε ένα φύλλο χαρτί, γράψτε όλους τους ακέραιους αριθμούς από το 2 μέχρι τον αριθμό που εξετάζεται. Μην γράψετε τον αριθμό 1. Προχωρήστε στο επόμενο βήμα.
2. Ξεκινήστε με b ίσο με 2. Πηγαίνετε στο επόμενο βήμα.
3. Βάλτε σε κύκλο το b στη λίστα. Πηγαίνετε στο επόμενο βήμα.
4. Ξεκινώντας από το b, μετρήστε μέχρι το b ακόμα στον κατάλογο και διαγράψτε αυτόν τον αριθμό. Επαναλάβετε την καταμέτρηση b ακόμα και τη διαγραφή αριθμών μέχρι το τέλος της λίστας. Πηγαίνετε στο επόμενο βήμα.
• (Για παράδειγμα: Όταν το b είναι 2, θα κυκλώσετε το 2 και θα διαγράψετε το 4, 6, 8 κ.ο.κ. Όταν το b είναι 3, θα κυκλώσετε το 3 και θα διαγράψετε τα 6, 9, 12 κ.ο.κ. Το 6 και το 12 έχουν ήδη διαγραφεί. Διαγράψτε τα ξανά).
5. Αυξήστε το b κατά 1. Πηγαίνετε στο επόμενο βήμα.
6. Εάν το b έχει διαγραφεί, επιστρέψτε στο προηγούμενο βήμα. Εάν το b είναι ένας αριθμός στη λίστα που δεν έχει διαγραφεί, προχωρήστε στο 3ο βήμα. Αν το b δεν υπάρχει στη λίστα, προχωρήστε στο τελευταίο βήμα.
7. (Αυτό είναι το τελευταίο βήμα.) Τελειώσατε. Όλοι οι πρώτοι αριθμοί είναι κυκλωμένοι και όλοι οι σύνθετοι αριθμοί είναι διαγραμμένοι.

Για παράδειγμα, θα μπορούσατε να εφαρμόσετε αυτή τη μέθοδο σε μια λίστα με τους αριθμούς από το 2 έως το 10. Στο τέλος, οι αριθμοί 2, 3, 5 και 7 θα καταλήξουν κυκλωμένοι. Είναι πρώτοι αριθμοί. Οι 4, 6, 8, 9 και 10 θα διαγραφούν. Είναι σύνθετοι αριθμοί.

Αυτή η μέθοδος ή ο αλγόριθμος χρειάζεται πολύ χρόνο για να βρει πολύ μεγάλους πρώτους αριθμούς. Αλλά είναι λιγότερο περίπλοκη από τις μεθόδους που χρησιμοποιούνται για πολύ μεγάλους πρώτους αριθμούς, όπως το τεστ πρωτογονικότητας του Φερμά (ένα τεστ για να διαπιστωθεί αν ένας αριθμός είναι πρώτος ή όχι) ή το τεστ πρωτογονικότητας των Μίλερ-Ράμπιν.

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

• Οι περισσότεροι άνθρωποι έχουν μια τραπεζική κάρτα, με την οποία μπορούν να πάρουν χρήματα από το λογαριασμό τους, χρησιμοποιώντας ένα ΑΤΜ. Αυτή η κάρτα προστατεύεται από έναν μυστικό κωδικό πρόσβασης. Δεδομένου ότι ο κωδικός πρέπει να παραμείνει μυστικός, δεν μπορεί να αποθηκευτεί σε καθαρό κείμενο στην κάρτα. Η κρυπτογράφηση χρησιμοποιείται για την αποθήκευση του κωδικού με μυστικό τρόπο. Αυτή η κρυπτογράφηση χρησιμοποιεί πολλαπλασιασμούς, διαιρέσεις και εύρεση υπολοίπων μεγάλων πρώτων αριθμών. Στην πράξη χρησιμοποιείται συχνά ένας αλγόριθμος που ονομάζεται RSA. Χρησιμοποιεί το κινεζικό θεώρημα υπολοίπων.

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

• Η εύρεση του μεγαλύτερου γνωστού μέχρι στιγμής prime έχει γίνει ένα είδος αθλήματος. Η εξέταση του αν ένας αριθμός είναι πρώτος μπορεί να είναι δύσκολη αν ο αριθμός είναι μεγάλος. Οι μεγαλύτεροι πρώτοι αριθμοί που είναι γνωστοί ανά πάσα στιγμή είναι συνήθως οι πρώτοι αριθμοί Mersenne, επειδή η ταχύτερη γνωστή δοκιμή για την πρωτεύουσα είναι η δοκιμή Lucas-Lehmer, η οποία βασίζεται στην ειδική μορφή των αριθμών Mersenne. Μια ομάδα που αναζητά τους πρώτους αριθμούς Mersenne βρίσκεται εδώ[1].