Miller-Rabin Primality Test

밀러-라빈 소수 판별법 (Miller-Rabin Primalirty Test) 은, 주어진 자연수 $n$이 소수인지 판별하는 간단한 방법이다.

 

모든 소수에 대해서 성립하는 페르마의 소정리가 주어진 $n$에 대해서도 성립할 수 있는지 여부를 보고,

$n$이 합성수인지, 아마도 소수일지 판단한다.

 

소수 $p$가 서로소인 $a$에 대해서 다음이 성립한다는 것이 페르마의 소정리이다.

$a^{p-1} \equiv 1 \pmod p$

 

이 정리가 주어진 $n$에 대해서 위배되는지를 다음과 같이 판단한다.

이 때, $a=1$인 경우는 항상 성립하므로, $a$는 $2 \leq p$에서 적당히 샘플링하여 진행한다.

 

먼저 $n$이 2의 배수인 경우, $n=2$인 경우에만 소수인 것은 자명하다.

 

다음은 $n$이 홀수인 경우이다.

홀수인 $n$은 항상 $n-1=2^sd$를 만족하는 음이 아닌 정수 $s$와 홀수 $d$가 존재하는 것 역시 자명하다.

따라서 $n$이 소수라면, 페르마의 소정리에 의해 다음을 만족한다.

$a^{2^sd} \equiv 1 \pmod{n}$        (1)

 

Lemma 1.

$a^2 \equiv 1 \pmod n \iff a \equiv 1 \pmod n \text{ or } a \equiv -1 \pmod n$

 

증명은 간단하다. 합차공식에 의해서 $a^2-1 \equiv (a+1)(a-1) \equiv 0 \pmod n$ 이므로 우로 가는 것이 성립하고,

좌로 가는 것은 자명하다.

 

식 (1)을 다시 쓰면, 다음과 같고,

$a^{2^sd} \equiv a^{(2^{(s-1)}d)^2} \equiv 1 \pmod n$

 

Lemma 1에 의해서 다음 중 하나가 성립하면 식 (1)도 성립하고, 둘 다 성립하지 않으면 식(1)도 성립하지 않는다.

$a^{2^{(s-1)}d} \equiv 1 \pmod n$ 또는,

$a^{2^{(s-1)}d} \equiv -1 \pmod n$.

 

만약 후자가 만족된다면, 식 (1)이 성립하는 것이므로, $n$은 아마도 소수일 것 이다.

 

만일 후자가 성립하지 않는다면,  재귀적으로 $a^{2^{(s-2)}d}$인 경우에 대해서 다시 Lemma 1를 적용해본다.

$a^{2^{(s-2)}d} \equiv 1 \pmod n$ 또는 $a^{2^{(s-2)}d} \equiv -1 \pmod n$ 가 성립하는가?

 

이를 반복하여 최종적으로 $a^d$인 경우에 다다르면, 

$a^d \equiv 1 \pmod n$ 또는 $a^d \equiv -1 \pmod n$ 가 성립하는가?

 

앞선 식들이 모두 만족되지 않는다면 $n$이 소수가 아님은 확실하다.

그 중 하나라도 만족되면, $n$은 소수일 수도 있다.

 

위의 판별은 다음과 정리할 수 있다.

$n$이 소수이려면, (식 (1)이 성립하려면)

$a^{2^rd} \equiv -1 \pmod n$를 만족하는 $0 \leq r \lt s$인 $r$이 존재하거나

$a^d \equiv 1 \pmod n$ 이어야한다.

 

 

밀러-라빈 판별은 $n$이 합성수인 경우, 소수임을 기각하는 것이므로,

기각하지 못한 경우, 이는 false positive를 포함하므로 "아마도 소수" (probably prime) 라고도 한다.

따라서 기각에 실패했다면, 또 다른 $a$를 샘플링하여 시행을 반복하여 false positive rate를 낮출 수 있다.

 

이렇게 밀러-라빈 테스트는 false positive의 발생가능성이 있지만, machine word 크기의 작은 $n$에 대해서는 100% 정확한 결과를 보장할 수 있음이 알려져 있다.

위키피디아에 따르면, 

• if n < 18,446,744,073,709,551,616 = $2^{64}$, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.

 

Ref. en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test