선행지식

• 페르마의 소정리/오일러 정리

설명

밀러-라빈 소수 판정법은 확률적 소수 판정법의 한 종류이다. 이 알고리즘은 합성수를 소수로 판정할 확률이 매우 낮으며, 실행 시간이 빠르다는 장점이 있다.

기본 개념

주어진 홀수 n이 소수인지 판정하기 위해, n-1을 $2^s * d$ (d는 홀수)로 표현한다. 이때 임의의 수 a(밀러-라빈 기저)에 대해 다음 조건들 중 하나를 만족하면 n은 '아마도 소수'이다:

• $a^d$ ≡ 1 (mod n)
• $a^{2^r * d}$ ≡ -1 (mod n), 0 ≤ r < s

이는 페르마의 소정리/오일러 정리 를 바탕으로 한다.

밀러 - 라빈 동작

필요한 정리

<aside> 💡

페르마의 소정리/오일러 정리

p가 소수이고 p,a가 서로소이면, $a^{p-1} \equiv 1\ \pmod p$다

</aside>

<aside> 💡

보조 정리

$a^{n-1} \equiv (a^{(n-1)/2})^2 \equiv 1\ or\ -1 \pmod n$

</aside>

동작

1. n은 우선 홀수여야 한다(짝수면 2의 배수이므로 소수가 아님)

2. 페르마의 소정리에 의해 n이 소수라면 다음 식이 성립한다. n-1은 짝수이므로 $2^s*d$의 형태로 표현할 수 있다.

   $$ a^{n-1} = a^{2^sd} \equiv 1 \pmod n $$

   1. 예: n = 13일 때 → $2^2 * 3$, s = 2, d = 3

3. 보조정리에 의해 다음과 같이 표현할 수 있다.

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

1. 이때 결과가 -1이면 밀러-라빈 테스트에 의해 소수일 가능성이 있으며, 1이면 다시 보조정리를 적용한다.
2. 계속해서 1이 나오는 경우에는 결국 $a^{2d} \equiv 1(mod\ n)$까지 도달하여, 마지막으로 $a^d \equiv 1(mod\ n)\ or\ a^d \equiv -1(mod\ n)$의 값을 갖게 된다.