Αρχή Αλγορίθμου:
Το Miller-Rabin είναι ένας πιθανοτικός έλεγχος πρώτων αριθμών βασισμένος σε επέκταση του μικρού θεωρήματος του Fermat. Για έναν περιττό αριθμό n, γράψτε n-1 ως 2^r × d και στη συνέχεια ελέγξτε αν ικανοποιεί:
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
Αριθμός γύρων ελέγχου και ακρίβεια:
- Πιθανοτικός Έλεγχος:Τυχαία επιλογή μιας βάσης a· κάθε γύρος ελέγχου μειώνει το ποσοστό σφάλματος στο 1/4
- k γύροι ελέγχου:Θεωρητικό ποσοστό σφάλματος ≤ (1/4)^k, το πραγματικό ποσοστό σφάλματος είναι πολύ χαμηλότερο
- Ντετερμινιστικός Έλεγχος:Για n < 3.317.044.064.679.887.385.961.981, χρησιμοποιώντας το σύνολο βάσεων {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} δίνει 100% ακριβή αποτελέσματα
Ειδικές Περιπτώσεις:
- Μικροί Πρώτοι:Αριθμοί όπως 2, 3, 5, 7 αναγνωρίζονται άμεσα
- Ζυγοί Αριθμοί:Όλοι οι ζυγοί αριθμοί εκτός από το 2 είναι σύνθετοι
- Αριθμοί Carmichael:Αριθμοί που περνούν τον έλεγχο Fermat αλλά είναι στην πραγματικότητα σύνθετοι (π.χ., 561) μπορούν να αναγνωριστούν σωστά από το Miller-Rabin