Έλεγχος πρωταρχικότητας

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

Για αριθμούς κάτω από 10¹² (ένα τρισεκατομμύριο), εκτελεί γνήσια δοκιμαστική διαίρεση: ξεκινώντας από το 2, δοκιμάζει κάθε ακέραιο υποψήφιο μέχρι το κατώτατο όριο του √n ως πιθανό διαιρέτη, σταματώντας τη στιγμή που διαιρείται ομοιόμορφα (σύνθετο) ή επιβεβαιώνοντας ότι δεν διαιρείται κανείς αφού έχει ελεγχθεί κάθε υποψήφιος μέχρι το √n (prime). Για τεράστιες μετρήσεις υποψηφίων, το ίχνος που εμφανίζεται περιορίζεται στο πρώτο ~18 που δοκιμάστηκε συν το τελευταίο, με μια ειλικρινή σημείωση σχετικά με τον αριθμό των υποψηφίων που παραλείφθηκαν στην οθόνη — αλλά κάθε υποψήφιος εξακολουθεί να ελέγχεται πραγματικά από τον κωδικό, κανένας δεν παραλείπεται στον υπολογισμό.

For numbers at or above that threshold — the size range used in cryptography — trial division would take too long, so the tool switches to the Miller–Rabin primality test with a fixed, deterministic set of 13 prime witnesses (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²4), ένα όριο που καθορίζεται από την υπολογιστική επαλήθευση (βλ. ανήκει). Πάνω από αυτό το όριο, το ίδιο τεστ εξακολουθεί να εκτελείται, αλλά το εργαλείο σας λέει ειλικρινά ότι η εγγύηση γίνεται μια εξαιρετικά ισχυρή πιθανολογική παρά μια μαθηματική βεβαιότητα.

Το ίχνος Miller–Rabin γράφει n − 1 = 2ˢ × d με d μονό, και στη συνέχεια περπατά μέσω της πραγματικής αρθρωτής εκθέσεως BigInt — τετράγωνο-και-πολλαπλασιάζοντας, μειώνοντας το modulo n σε κάθε βήμα, ώστε οι αριθμοί να μην εκραγούν ποτέ — σπιθαμή προς σπιθαμή για τον πρώτο μάρτυρα, και αναφέρει τον αριθμό των μαρτύρων, συμπεριλαμβανομένου του αριθμού των μαρτύρων. πρωταρχικός. Όλα εκτελούνται τοπικά στο πρόγραμμα περιήγησής σας: κανένας διακομιστής, κανένα εξωτερικό API, κανένα στοιχείο δεν φεύγει ποτέ από τη συσκευή σας.