소수 판정(Primality test)

가장 단순한 방법은 나눠 보는 것입니다. $n = d \cdot e$이면 두 인수 중 하나는 $\sqrt n$ 이하이니 $\sqrt n$까지의 소수로만 나눠 보면 됩니다. 하지만 RSA에 쓰는 300자리 수라면 $\sqrt n$이 150자리입니다. 150자리 이하의 소수만 해도 약 $3 \times 10^{147}$개라 어떤 컴퓨터로도 다 나눠 볼 수 없습니다. 인수를 찾지 않고도 합성수임을 알아낼 방법이 필요합니다.

페르마 소정리는 $n$이 소수이면 $n$의 배수⁠(multiple)⁠가 아닌 모든 $a$에 대해 $a^{n-1} \equiv 1 \pmod n$이라고 말합니다. 그러니 이 식이 깨지는 $a$가 하나라도 있으면 $n$은 틀림없이 합성수이고, 그런 $a$를 증인이라 부릅니다. $n =$ 에 대해 모든 밑 $a = 1, \dots, n-1$을 으로 시험한 결과가 아래 그림입니다.

밑 하나를 골라 보면, $a =$ 에 대해

그런데 $n$과 서로소⁠(coprime)⁠인 모든 밑을 속이는 합성수가 있습니다. 가장 작은 것이 561 = 3·11·17입니다. 1910년 이런 수들을 연구한 미국 수학자 로버트 카마이클의 이름을 따 카마이클 수라 합니다. 561에서 $n-1 = 560$은 $2, 10, 16$(각각 $3-1, 11-1, 17-1$)의 배수입니다. 그래서 중국인의 나머지 정리⁠(Chinese remainder theorem)⁠로 3, 11, 17 각각으로 나눈 나머지⁠(remainder)⁠를 따로 따져 보면, 561과 서로소인 모든 $a$에서 페르마 소정리에 의해 $a^{560} \equiv 1$이 저절로 성립합니다. 카마이클 수⁠(Carmichael number)⁠가 무한히 많다는 것은 1994년 앨퍼드, 그랜빌, 포머런스가 증명했습니다. 반면 카마이클 수가 아닌 합성수라면 서로소인 밑의 절반 이상이 증인입니다. 통과하는 밑끼리 곱해도 통과하므로, 증인이 하나라도 있으면 그 증인에 통과하는 밑을 하나씩 곱한 것은 모두 증인이 되고(서로 다른 밑에 곱하면 결과도 서로 다릅니다), 그래서 증인이 통과하는 밑보다 적을 수 없기 때문입니다. 그래서 무작위로 고른 밑 몇 개만 시험해도 거의 확실히 들킵니다. 341 = 11·31은 밑 2는 속이지만 다른 밑에 들킵니다. 비교용으로 소수 97도 보세요.

1976년 게리 밀러가 내놓고 1980년 마이클 라빈이 무작위 판정법으로 고친 밀러–라빈 판정법⁠(Miller–Rabin test)⁠은 한 가지를 더 봅니다. 소수를 법으로 하면 $x^2 \equiv 1$의 해가 $\pm 1$뿐입니다. 그래서 $n-1 = 2^s d$로 쓰고 $a^d, a^{2d}, a^{4d}, \dots$를 차례로 제곱해 가다가, 처음 값 $a^d$가 1이 아닌데 1이 되기 직전의 값이 $-1$이 아니거나, 끝내 1이 되지 않으면 합성수입니다. 이 판정은 카마이클 수도 잡아내고, 홀수 합성수라면 통과하는 밑이 전체의 4분의 1을 넘지 않는다는 것이 증명되어 있습니다. 합성수가 무작위로 고른 밑 20개를 모두 통과할 확률⁠(probability)⁠은 $4^{-20} \approx 10^{-12}$ 이하입니다. 이처럼 동전 던지기를 계산에 섞고, 되풀이할수록 틀릴 확률이 줄어드는 방법을 무작위 알고리즘⁠(randomized algorithm)⁠이라 합니다.

이어지는 곳. 큰 소수를 찾을 때는 무작위 홀수를 골라 시험하기를 되풀이합니다. 몇 번 만에 나올지는 소수 정리⁠(prime number theorem)⁠와 기댓값⁠(expected value)⁠이 알려 줍니다. $x$ 근처에서 소수의 비율은 약 $1/\ln x$(자연로그⁠, natural logarithm⁠)이고 홀수만 고르면 약 $2/\ln x$이니, 300자리 홀수라면 평균⁠(mean)⁠ 약 $\ln(10^{300})/2 \approx 345$번 만에 소수를 만납니다. 밀러가 처음 내놓은 판정법은 결정적 방법, 곧 무작위를 쓰지 않고 정해진 범위의 밑을 모두 시험하는 방법이었습니다. 그 정확성은 일반화된 리만 가설(제타 함수⁠(zeta function)⁠를 닮은 함수⁠(function)⁠들의 영점⁠(zero)⁠도 한 직선 위에 있다는 추측)이 참이어야 보장됩니다. 2002년에는 인도 공과대학 칸푸르의 아그라왈, 카얄, 삭세나가 세 사람 이름을 딴 AKS 판정법을 발표했습니다. 무작위성도 증명되지 않은 가설도 없이 다항식 시간⁠(polynomial time)⁠, 곧 자릿수 $k$가 늘 때 걸리는 시간이 고정된 지수 $c$에 대해 $k^c$의 상수배를 넘지 않는 방법입니다(점근 표기법⁠, asymptotic notation⁠). 그래도 실제로는 더 빠른 밀러–라빈이 쓰입니다. 합성수라는 것을 알아도 인수를 찾는 소인수분해⁠(prime factorization)⁠는 여전히 어렵습니다. 밑을 거듭제곱할 때 값이 도는 고리 구조는 원시근⁠(primitive root)⁠에서, 판정에 쓰는 나머지 계산은 모듈러 연산⁠(modular arithmetic)⁠에서 이어집니다. 그림의 회색 칸, 곧 $n$과 공약수가 있는 밑을 가려내는 최대공약수⁠(greatest common divisor)⁠ 계산은 유클리드 호제법⁠(Euclidean algorithm)⁠이 맡습니다.