Υπολογιστής Ελέγχου Πρώτων Miller-Rabin

Σχετικά με αυτόν τον υπολογιστή

Ο έλεγχος Miller-Rabin ελέγχει την πρωτότητα γράφοντας το n − 1 ως 2ˢ·d με d περιττό και στη συνέχεια εξετάζοντας αν μια βάση-μάρτυρας a ικανοποιεί την aᵈ ≡ 1 (mod n) ή την a^(2ʳ·d) ≡ −1 (mod n) για κάποιο r < s. Ένας μόνο μάρτυρας δίνει μόνο πιθανοκρατικό αποτέλεσμα, αλλά ο έλεγχος με ένα μικρό, αποδεδειγμένο σύνολο σταθερών βάσεων-μαρτύρων (για παράδειγμα 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) κάνει τον έλεγχο ντετερμινιστικό για κάθε ακέραιο κάτω από περίπου 3,18 × 10²³ — πολύ πέρα από όσα χρειάζονται οι περισσότερες εφαρμογές.

Οι κρυπτογράφοι και οι προγραμματιστές λογισμικού χρησιμοποιούν ακριβώς αυτό το είδος ελέγχου όταν δημιουργούν μεγάλους υποψήφιους πρώτους για κλειδιά RSA ή Diffie-Hellman, και οι φοιτητές της επιστήμης υπολογιστών τον χρησιμοποιούν για να δουν, σε πραγματικούς αριθμούς, γιατί ο Miller-Rabin κλιμακώνεται πολύ καλύτερα από τη δοκιμαστική διαίρεση για να ελεγχθεί αν ένας μεγάλος ακέραιος είναι πρώτος.