알고리즘 원리:
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으로 올바르게 식별 가능