밀러-라빈(Miller-Rabin) 소수성 테스트란?
밀러-라빈 소수성 테스트는 페르마 테스트(Fermat test)와 제곱근 테스트(square root test)를 결합하여 강한 의사소수(strong pseudoprime)를 판별하는 고전적인 방법입니다. 이 테스트에서는 먼저 n − 1을 홀수 m과 2의 거듭제곱의 곱 형태로 나타냅니다.
$$n - 1 = m \times 2^{k}$$
밑(base) a에 대한 페르마 테스트는 다음과 같이 분해할 수 있습니다.
$$a^{n-1} = a^{m \times 2^{k}} = \left[a^{m}\right]^{2^{k}} = \left[\cdots\left[\left[a^{m}\right]^{2}\right]^{2}\cdots\right]^{2}$$
즉, an−1 (mod n)을 한 번에 계산하는 대신 k+1단계에 걸쳐 계산할 수 있습니다. 이렇게 나누어 계산하면 각 단계마다 제곱근 검사를 수행할 수 있다는 큰 장점이 있습니다. 제곱근 검사에서 실패하면 즉시 중단하고 n을 합성수(composite number)로 선언할 수 있기 때문입니다.
각 단계에서는 페르마 테스트의 통과 여부와 함께, 인접한 두 단계 사이에서 제곱근 조건(결괏값이 1이 되기 직전의 값이 ±1인지)이 만족되는지를 확인합니다.
이 검사의 원리는 다음과 같습니다. n이 소수일 때 x² ≡ 1 (mod n)을 만족하는 해는 x ≡ ±1 (mod n)뿐입니다. 따라서 어느 중간 단계에서 제곱한 결과가 1이 되었는데 그 값 자체가 ±1이 아니었다면, n은 반드시 합성수입니다.
초기화(Initialization)
밑 a를 선택하고 T = am을 계산합니다. 여기서 m = (n−1)/2k입니다.
T가 +1 또는 −1이면 n을 강한 의사소수로 선언하고 중단합니다. T가 ±1이면 다음 단계에서 T는 1이 되고 이후 모든 단계에서 1로 유지되므로 페르마 테스트를 통과합니다. 또한 다음 단계에서 T가 1이 되고, 1의 제곱근은 ±1이므로 제곱근 검사도 통과합니다.
T가 그 외의 값이라면 n이 소수인지 합성수인지 아직 확실하지 않으므로 다음 단계로 진행합니다.
1단계
T를 제곱합니다.
결과가 +1이면, 이후 단계에서도 T는 계속 1로 유지되므로 페르마 테스트는 통과한다는 것을 알 수 있습니다. 그러나 이 단계에서 T가 1인데 바로 앞 단계의 T가 ±1이 아니었으므로 제곱근 검사는 실패합니다. 따라서 n을 합성수로 선언하고 중단합니다.
결과가 −1이면, 다음 단계에서 T가 1이 되어 이후 계속 1로 유지되므로 최종적으로 페르마 테스트를 통과합니다. 또한 이 단계에서 T가 −1이고 다음 단계에서 1이 되므로 제곱근 검사도 통과합니다. 따라서 n을 강한 의사소수로 선언하고 중단합니다.
결과가 그 외의 값이면 소수 여부를 판단할 수 없으므로 다음 단계로 진행합니다.
2단계 ~ K−1단계
2단계부터 K−1단계까지는 1단계와 동일한 과정을 반복합니다. 매 단계마다 위와 같은 기준으로 판정을 내리고, 판정이 불가능하면 다음 단계로 넘어갑니다.
K단계
이 단계는 실제로 필요하지 않습니다. 여기까지 진행했는데도 아무런 결론을 내리지 못했다면, 설령 이 단계의 결과가 1이더라도(페르마 테스트는 통과) 바로 앞 단계의 결과가 ±1이 아니므로 제곱근 검사는 실패하게 됩니다. 따라서 K−1단계까지 수행했음에도 중단되지 않았다면 n을 합성수로 선언하면 됩니다. 요컨대 밀러-라빈 테스트는 0단계(초기화)부터 K−1단계까지만 수행하면 충분합니다.