밀러-라빈 소수 판별법

1976년, Gray Miller은 박사 학위 논문1을 통해 주어진 수의 소수 여부를 판별하는 알고리즘을 소개했다. 원래 알고리즘은 확장 리만 가설(Extended Riemann Hypothesis) 아래에서 결정론적(deterministic)으로 동작했다. 하지만 이 가설은 아직 증명되지 않은 상태다. 4년 후, Michael O. Rabin은 이 알고리즘을 개선하여2 확률적 접근 방식을 도입했고, 더 이상 증명되지 않은 가설에 의존하지 않게 되었다.

확률적 알고리즘

테스트 결과는 단순히 불리언 값이다. 그러나 true가 반드시 _소수_를 의미하지는 않는다. 실제로는 _아마도 소수일 가능성이 높다_는 뜻이다. 반면 false는 확실히 _합성수_임을 나타낸다.

테스트의 정확도를 높이려면 여러 번 반복해야 한다. 모든 반복에서 true가 반환되면, _아마도 소수일 가능성이 매우 높다_고 자신 있게 말할 수 있다.

알고리즘

주어진 숫자를 n이라고 하자. n-1을 2^s·d로 표현할 수 있다. 여기서 d는 홀수다. 그리고 2부터 n - 1 사이의 임의의 숫자 a를 선택한다.

이제 모듈로 n에서 다음과 같은 수열을 만든다:

a^d, a^(2·d), a^(4·d), ... , a^((2^(s-1))·d), a^((2^s)·d) = a^(n-1)

숫자 n이 테스트를 통과하면, 즉 _소수일 가능성이 높다_고 판단하는 조건은 다음과 같다: 1) a^d가 모듈로 n에서 1과 합동이거나, 2) a^((2^k)·d)가 모듈로 n에서 -1과 합동인 k = 1, 2, ..., s-1이 존재하는 경우다.

의사 코드

다음 의사 코드는 위키백과3에서 발췌한 내용이다:

사용법

checkWithMillerRabin(7)                      // 7이 소수인지 테스트. (기본 반복 횟수 = 1)
checkWithMillerRabin(7, accuracy: 10)       // 7이 소수인지 테스트하고 10번 반복.

참고 자료

1. G. L. Miller, "Riemann's Hypothesis and Tests for Primality". J. Comput. System Sci. 13 (1976), 300-317.
2. M. O. Rabin, "Probabilistic algorithm for testing primality". Journal of Number Theory. 12 (1980), 128-138.
3. Miller–Rabin primality test - Wikipedia, the free encyclopedia

Swift Algorithm Club을 위해 Sahn Cha(@scha00)가 작성
코드는 Simon C. Krüger가 업데이트