Έλεγχος Πρώτων Αριθμών

Οι πρώτοι αριθμοί έχουν ακριβώς δύο διαιρέτες: το 1 και τον εαυτό τους.

Οι πρώτοι πρώτοι αριθμοί είναι οι 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Οι πρώτοι αριθμοί αποτελούν τους δομικούς λίθους όλων των ακεραίων.

Κάθε ακέραιος > 1 μπορεί να εκφραστεί μοναδικά ως γινόμενο πρώτων παραγόντων.

Για παράδειγμα, 60 = 2² × 3 × 5.

Αυτό είναι θεμελιώδες στα μαθηματικά και την κρυπτογραφία.

Για να ελέγξετε αν ένας αριθμός n είναι πρώτος, εξετάστε αν διαιρείται ακριβώς από οποιονδήποτε ακέραιο μεταξύ του 2 και της τετραγωνικής ρίζας του n. Αν δεν υπάρχει τέτοιος αριθμός, τότε ο n είναι πρώτος.

Αρχικά, διαχειριστείτε τις μικρές περιπτώσεις:

• οι αριθμοί κάτω από το 2 δεν είναι πρώτοι
• το 2 και το 3 είναι πρώτοι
• οποιοσδήποτε άρτιος αριθμός μεγαλύτερος από το 2 είναι σύνθετος

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

Για παράδειγμα, ο έλεγχος του 97 απαιτεί μόνο τη δοκιμή των 3, 5 και 7 (αφού √97 ≈ 9,85) και κανένας δεν τον διαιρεί, επομένως ο 97 είναι πρώτος. Το Wolfram MathWorld περιγράφει αυτή τη μέθοδο ως δοκιμαστική διαίρεση (trial division), η οποία αποτελεί τον πιο άμεσο έλεγχο πρώτων αριθμών.

Η μέθοδος της τετραγωνικής ρίζας σημαίνει ότι χρειάζεται να δοκιμάσετε πιθανούς διαιρέτες μόνο μέχρι το √n, αντί για όλη τη διαδρομή μέχρι το n.

Ο λόγος είναι ότι αν n = a × b, τότε τουλάχιστον ένας από τους παράγοντες a ή b πρέπει να είναι μικρότερος ή ίσος με το √n. Διαφορετικά, το γινόμενό τους θα ξεπερνούσε το n. Επομένως, αν δεν βρεθεί κανένας παράγοντας κάτω από το √n, δεν υπάρχει ούτε μεγαλύτερος παράγοντας.

Αυτό μειώνει δραματικά την απαιτούμενη εργασία: ο έλεγχος για το αν ο 9.973 είναι πρώτος απαιτεί τη δοκιμή διαιρετών μόνο μέχρι το 99 περίπου, και όχι μέχρι το 10.000.

Το Khan Academy χρησιμοποιεί αυτό το επιχείρημα των ζευγών για να εξηγήσει γιατί η δοκιμαστική διαίρεση σταματά στην τετραγωνική ρίζα, καθιστώντας τον χειροκίνητο έλεγχο πρώτων αριθμών εφικτό στην πράξη.

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

Ξεκινήστε με μια λίστα ακεραίων από το 2 έως το N. Πάρτε το 2, σημειώστε τα 4, 6, 8, ... ως σύνθετα. Μεταβείτε στον επόμενο μη σημειωμένο αριθμό, το 3, και σημειώστε τα 6, 9, 12, ... Συνεχίστε με το 5, το 7 και ούτω καθεξής. Οι αριθμοί που παραμένουν χωρίς σήμανση είναι πρώτοι.

Αν εφαρμοστεί μέχρι το 30, το κόσκινο αφήνει τους αριθμούς 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Ο αλγόριθμος αυτός, που πήρε το όνομά του από τον Έλληνα μαθηματικό Ερατοσθένη τον Κυρηναίο (και τεκμηριώνεται από την Encyclopaedia Britannica), είναι ένας από τους παλαιότερους και πιο αποτελεσματικούς τρόπους για την καταγραφή πρώτων αριθμών σε ένα εύρος.

Το Θεμελιώδες Θεώρημα της Αριθμητικής ορίζει ότι κάθε ακέραιος μεγαλύτερος από το 1 είναι είτε πρώτος είτε μπορεί να γραφτεί ως γινόμενο πρώτων αριθμών με έναν ακριβώς μοναδικό τρόπο, ανεξάρτητα από τη σειρά των παραγόντων.

Για παράδειγμα, 360 = 2³ × 3² × 5, και κανένας άλλος συνδυασμός πρώτων αριθμών δεν δίνει γινόμενο 360. Αυτή η μοναδικότητα είναι ο λόγος για τον οποίο οι πρώτοι αριθμοί αποκαλούνται οι δομικοί λίθοι των ακεραίων.

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

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

Οι δίδυμοι πρώτοι είναι ζεύγη πρώτων αριθμών που διαφέρουν ακριβώς κατά 2, όπως οι (3, 5), (5, 7), (11, 13), (17, 19) και (29, 31).

Το κενό μεταξύ διαδοχικών πρώτων αριθμών γενικά μεγαλώνει όσο οι αριθμοί αυξάνονται, αν και οι δίδυμοι πρώτοι συνεχίζουν να εμφανίζονται. Το αν υπάρχουν άπειροι δίδυμοι πρώτοι είναι η περίφημη Εικασία των Διδύμων Πρώτων, η οποία παραμένει αναπόδεικτη.

Η On-Line Encyclopedia of Integer Sequences (OEIS) καταγράφει τα μικρότερα μέλη των ζευγών διδύμων πρώτων στην ακολουθία A001359.

Η κατανόηση των κενών μεταξύ των πρώτων αριθμών βοηθά να εξηγηθεί γιατί οι πρώτοι αριθμοί γίνονται πιο αραιοί: κοντά στο ένα εκατομμύριο, οι πρώτοι αριθμοί απέχουν κατά μέσο όρο περίπου 14 μονάδες μεταξύ τους, μια τάση που περιγράφεται από το Θεώρημα των Πρώτων Αριθμών στη NIST Digital Library of Mathematical Functions.

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

Πέρα από την ασφάλεια, οι πρώτοι αριθμοί εμφανίζονται σε:

• μέγεθος πινάκων κατακερματισμού (hash tables) (οι πίνακες με μήκος πρώτου αριθμού μειώνουν τις συγκρούσεις)
• δημιουργία ψευδοτυχαίων αριθμών
• κώδικες διόρθωσης σφαλμάτων
• κύκλους ζωής των τζιτζικιών που εξελίχθηκαν γύρω από έτη που είναι πρώτοι αριθμοί για να αποφεύγουν τους θηρευτές

Η Britannica σημειώνει ότι η ανάλυση σε πρώτους παράγοντες απλοποιεί επίσης τα κλάσματα και υπολογίζει τα ελάχιστα κοινά πολλαπλάσια. Αυτός ο υπολογιστής υποστηρίζει αυτές τις εργασίες αναλύοντας αριθμούς σε παράγοντες και παράγοντας πρώτους αριθμούς τόσο για τον σχεδιασμό αλγορίθμων όσο και για τις σχολικές εργασίες μαθηματικών.

Ένας πρώτος αριθμός έχει ακριβώς δύο διαφορετικούς θετικούς διαιρέτες, το 1 και τον εαυτό του, ενώ ένας σύνθετος αριθμός έχει περισσότερους από δύο διαιρέτες.

Για παράδειγμα, ο 13 είναι πρώτος (διαιρέτες 1 και 13) και ο 12 είναι σύνθετος (διαιρέτες 1, 2, 3, 4, 6, 12). Ο αριθμός 1 δεν είναι ούτε πρώτος ούτε σύνθετος, επειδή έχει μόνο έναν διαιρέτη.

Αυτή η σύμβαση διατηρεί το Θεμελιώδες Θεώρημα της Αριθμητικής ξεκάθαρο: αν το 1 θεωρούνταν πρώτος, οι αναλύσεις σε παράγοντες δεν θα ήταν πλέον μοναδικές, καθώς θα μπορούσατε να εισαγάγετε οποιονδήποτε αριθμό από άσσους (1).

Η Encyclopaedia Britannica και το Khan Academy τονίζουν και τα δύο αυτή τη διάκριση, γι' αυτό και το εργαλείο μας επισημαίνει το 1 ξεχωριστά από τους πρώτους και τους σύνθετους αριθμούς.

Οι πρώτοι αριθμοί Mersenne είναι πρώτοι της μορφής 2^p − 1, όπου ο εκθέτης p είναι και ο ίδιος πρώτος. Παραδείγματα περιλαμβάνουν τους 3 (2² − 1), 7 (2³ − 1), 31 (2⁵ − 1) και 127 (2⁷ − 1).

Ωστόσο, δεν δίνει κάθε πρώτος εκθέτης έναν πρώτο αριθμό: ο 2¹¹ − 1 = 2047 = 23 × 89 είναι σύνθετος.

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

Το Great Internet Mersenne Prime Search (GIMPS) συντονίζει εθελοντές για την ανακάλυψή τους. Η ακολουθία OEIS A000668 καταγράφει τους γνωστούς πρώτους αριθμούς Mersenne.

• Το πιο συνηθισμένο λάθος είναι να θεωρείται το 1 ως πρώτος. Δεν είναι, επειδή ένας πρώτος αριθμός πρέπει να έχει ακριβώς δύο διαιρέτες.
• Ένα άλλο σφάλμα είναι να ξεχνάμε ότι το 2 είναι ο μόνος άρτιος πρώτος, με αποτέλεσμα οι άνθρωποι να τον παραλείπουν λανθασμένα ή να υποθέτουν εσφαλμένα ότι άλλοι άρτιοι αριθμοί μπορεί να είναι πρώτοι.
• Ένα τρίτο λάθος είναι η διακοπή της δοκιμαστικής διαίρεσης πολύ νωρίς ή πολύ αργά: πρέπει να δοκιμάσετε όλους τους διαιρέτες μέχρι το √n, όχι μόνο μερικούς μικρούς.
• Οι άνθρωποι επίσης μπερδεύουν την ανάλυση σε πρώτους παράγοντες με την καταγραφή όλων των παραγόντων. Ο 12 έχει παράγοντες τους 1, 2, 3, 4, 6, 12 αλλά ανάλυση σε πρώτους παράγοντες μόνο 2² × 3.
• Τέλος, η υπόθεση ότι κάθε αριθμός της μορφής 6k ± 1 είναι πρώτος είναι ψευδής. Ο 25 = 6(4) + 1 είναι σύνθετος.