Randomized Algorithm - Primality Test (Monte Carlo)

Primality Test (Monte Carlo)

• n이 소수인가?

페르마 정리

1. 8377이 소수라면, 모든 a에 대하여 a^8376 = 1 mod 8377 이다.
2. 8377이 소수가 아니라면, 어떤 a에 대하여 a^8376 ≠1mod8377 이다.

이때 1<a<n 이다.

* a^8376 = 1 mod 8377 == (a^8376)%8377 = 1

즉, a를 바꿔가며 계속 나머지 구했더니 1이 계속 나오면 소수.
1이 나오지 않는다면 그때의 a를 witness라고 부르고 n은 소수가 아니다.

Carmichael Number는 witness가 없지만 소수가 아니다. ⇒ 따로 처리하자.

witness의 개수가 적다면? ⇒ 소수 판정을 놓칠 확률이 생긴다.
하지만 witness가 있다면 n개중 절반 이상이 witness이기 때문에(증명된 사실.)
소수 판정을 놓칠 확률은 매우 낮다.

---

알고리즘

1. 랜덤하게 n을 고른다.
2. n이 Carmichael Number라면 따로 처리한다.
3. 랜덤하게 a를 고른다. (1<a<n)
4. a^(n-1) = 1 mod n 을 체크한다.
    1이라면 아직까지는 소수다. 따라서 다시 3.으로 돌아가서 반복한다.
    1이 아니라면 소수가 아니다.
5. 일정 시간이 지나면 알고리즘을 끝낸다.

만약 n이 소수가 아니라면 한 번의 소수 판정에서 살아남을 확률은 약 (1/2) 이다.
왜냐하면 witness의 개수가 n개중 절반 이상이기 때문이다.
그리고 n이 커질수록 확률은 점점 줄어든다.
ex) n = 1000 이라면 살아남을 확률 = (1/2)^1000

따라서 알고리즘이 소수 판정에 실패할 확률은 매우 적다.