Ελεγκτής Πρώτων Αριθμών
Ελέγξτε αν ένας αριθμός είναι πρώτος και δείτε ακριβώς το γιατί: πραγματική δοκιμαστική διαίρεση έως √n για μικρούς και μεσαίους αριθμούς και μια αυθεντική αναλυτική περιγραφή Miller–Rabin για αριθμούς κρυπτογραφικού μεγέθους.
🔒 Επεξεργάζεται εξ ολοκλήρου στο πρόγραμμα περιήγησής σας — τίποτα που εισάγετε εδώ δεν μεταφορτώνεται ποτέ.
Αποτέλεσμα
Ο ελεγκτής πρώτων αριθμών σας λέει αν ένας ακέραιος είναι πρώτος και — σε αντίθεση με τους περισσότερους υπολογιστές στο διαδίκτυο — σας δείχνει τον πραγματικό αλγόριθμο που τον απέδειξε, όχι έναν αποθηκευμένο πίνακα αναζήτησης. Πληκτρολογήστε οποιονδήποτε ακέραιο, θετικό ή αρνητικό, μικρό ή τεράστιο, και το εργαλείο αποφασίζει ποιον πραγματικό αλγόριθμο θα εκτελέσει με βάση το μέγεθός του.
Για αριθμούς κάτω από 10¹² (ένα τρισεκατομμύριο), εκτελεί γνήσια δοκιμαστική διαίρεση: ξεκινώντας από το 2, δοκιμάζει κάθε ακέραιο υποψήφιο έως το ακέραιο μέρος του √n ως πιθανό διαιρέτη, σταματώντας τη στιγμή που κάποιος διαιρεί ακριβώς (σύνθετος) ή επιβεβαιώνοντας ότι κανένας δεν το κάνει μόλις εξεταστούν όλοι οι υποψήφιοι έως το √n (πρώτος). Για τεράστιο πλήθος υποψηφίων, το ίχνος που εμφανίζεται περιορίζεται στους πρώτους ~18 που δοκιμάστηκαν συν τον τελευταίο, με μια ειλικρινή σημείωση για το πόσοι παραλείφθηκαν στην προβολή — αλλά κάθε υποψήφιος εξακολουθεί να ελέγχεται πραγματικά από τον κώδικα, κανένας δεν παραλείπεται στον υπολογισμό.
Για αριθμούς ίσους ή μεγαλύτερους από αυτό το όριο — το εύρος μεγέθους που χρησιμοποιείται στην κρυπτογραφία — η δοκιμαστική διαίρεση θα διαρκούσε πολύ, οπότε το εργαλείο μεταβαίνει στον έλεγχο πρώτων αριθμών Miller–Rabin με ένα σταθερό, ντετερμινιστικό σύνολο 13 πρώτων μαρτύρων (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Αυτό το ακριβές σύνολο μαρτύρων είναι ένα γνωστό αποτέλεσμα: δεν έχει ψευδώς θετικά για κανένα n κάτω από 3.317.044.064.679.887.385.961.981 (περίπου 3,3×10²⁴), ένα όριο που έχει τεκμηριωθεί με υπολογιστική επαλήθευση (βλ. Sorenson & Webster, 2015, και τον ευρέως αναπαραγόμενο πίνακα ντετερμινιστικών μαρτύρων στον οποίο ανήκει). Πάνω από αυτό το όριο, ο ίδιος έλεγχος εξακολουθεί να εκτελείται, αλλά το εργαλείο σας ενημερώνει με ειλικρίνεια ότι η εγγύηση γίνεται μια εξαιρετικά ισχυρή πιθανοτική και όχι μαθηματική βεβαιότητα.
Το ίχνος Miller–Rabin γράφει το n − 1 = 2ˢ × d με το d περιττό, στη συνέχεια εκτελεί πραγματική modular ύψωση σε δύναμη BigInt — τετραγωνισμός-και-πολλαπλασιασμός, με αναγωγή modulo n σε κάθε βήμα ώστε οι αριθμοί να μην εκρήγνυνται ποτέ — bit προς bit για τον πρώτο μάρτυρα και αναφέρει την ετυμηγορία κάθε μάρτυρα, συμπεριλαμβανομένου του ποιος μάρτυρας αποδεικνύει τη συνθετότητα αν ο αριθμός αποδειχθεί ότι δεν είναι πρώτος. Όλα εκτελούνται τοπικά στον browser σας: κανένας server, κανένα εξωτερικό API, κανένα δεδομένο δεν φεύγει ποτέ από τη συσκευή σας.