[암호학] 20. 소수 판정 (Primality Test)

지난시간 RSA를 위해 두 가지 문제점이 남아있었는데 빠른 거듭제곱은 해결했고 큰 소수 생성 문제가 남아있었다.

이를 해결해보자.

기본적인 소수 판정

$N$이 소수인지 판정한다고 하자.

$1$~$\sqrt{N}$까지만 판별했을 때 나누어떨어지는 수 $d \le \sqrt{N}$가 있다면 $\frac{N}{d} \ge \sqrt{N}$ 역시 나누어 떨어지므로 $\sqrt{N}$까지 확인해보면 충분하다.

$\sqrt{N}$은 이분탐색 등으로 $P$ 시간에 구할 수 있지만 위 로직은 시간복잡도가 $O(\sqrt{N})$이 나오므로 $\log N$의 입장으로 보면 $EXP$이다.

 

다항시간 판정법이 있어야 그나마 쓸만하니 그런 방법이 있는지 알아보자.

 

페르마의 소정리

$p$가 소수라면 $a^{p-1} \equiv 1 \mod p$ $(1<a<p)$

$p$가 소수가 아니라면 $a^{p-1} \not\equiv 1 \mod p$인 $a$가 존재할 수 있다. (반드시 존재한다는 것은 아니다!)

이를 편의상 CFT(Custom Fermat Test)라고 하자. (그냥 지은 이름이다.)

그러한 $a$가 존재한다면 이를 witness라고 정의하자.

그렇다면 $a$를 바꿔가며 CFT를 하다가 witness인 $a$가 발견된다면 $p$는 소수가 아닌게 된다.

 

하지만 위에서 말했듯 $p$가 합성수이면서 CFT를 통과하는 수가 있다.

그러한 수를 카마이클 수(Carmichael Number)라고 한다.

 

카마이클 수

합성수 $m$과 $\gcd(a,m) = 1$인 모든 $a$에 대해 $a^{m-1} \equiv 1 \mod m$인 $m$을 카마이클 수라고 한다.

따라서 $p$를 정할 때 카마이클 수는 고르면 안된다.

다행히도 카마이클 수는 무한하긴 하지만 검사하는 규칙이 있고 그 수가 상당히 적다고 한다.

 

Witness

카마이클 수를 제거하고 나면 CFT만으로 소수인지 빠르게 확인할 수 있다.

 

Theorem) 카마이클 수를 제거하면 어떤 수 $n$에 대한 witness $a$는 non-witness보다 많다.

proof)

$A$를 $n$의 witness들의 집합, $B$를 $n$의 non-witness들의 집합이라고 하자.

$|A| \ge |B|$임을 증명할 것이다.

$a \in A, b \in B$를 생각해보자.

$a^{n-1} \not\equiv 1 \mod n$, $b^{n-1} \equiv 1 \mod m$이다.

$x = ab (<n)$을 생각해보자.

$x^{n-1} = (ab)^{n-1}= a^{n-1}b^{n-1} \not\equiv 1 \mod n$이 된다.

즉 $x \in A$가 된다.

따라서 $B$의 원소는 $A$의 원소 하나 이상에 대응이 되고 $|A| \ge |B|$가 성립한다. $\Box$

 

Primality Test

최종적으로 소수판정 과정을 살펴보자.

1. 랜덤 홀수 $N$을 고른다.

2. $N$이 카마이클 수인지 판정한다.

3. 랜덤한 $a$를 고른다. $(1<a<N)$

4. $\gcd(a,N) = 1$인지 확인한다.

5. $a^{N-1} \equiv 1 \mod N$을 확인한다.

 

2,4,5에서 한번이라도 실패하면 1로 돌아간다.

5번과정은 시도할 때마다 틀릴 확률이 $\frac{1}{2^k}$가 된다. ($k$는 시도 횟수)

한 30번정도만 시도하면 정확도 높은 판정이 가능하다.

 

1~5번과정은 모두 다항시간에 가능하지만 랜덤성이 있으므로 $NP$에 속한다.