지난시간 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$에 속한다.
'기타 > 암호학' 카테고리의 다른 글
[암호학] 22. 스테가노그래피 (0) | 2023.06.08 |
---|---|
[암호학] 21. Massey-Omura (0) | 2023.02.07 |
[암호학] 19. RSA 암호 (0) | 2023.01.31 |
[암호학] 18. NP-Complete (0) | 2023.01.27 |
[암호학] 17. P, NP (0) | 2023.01.24 |