Принцип на алгоритъма:
Miller-Rabin е вероятностен тест за простота, базиран на разширение на малката теорема на Ферма. За нечетно число 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 са съставни
- Числа на Кармайкъл:Числа, които преминават теста на Ферма, но всъщност са съставни (напр. 561) могат да бъдат правилно идентифицирани от Miller-Rabin