소수 판별법(Primality Test)이란?
소수 판별법은 입력으로 주어진 수가 소수(prime number)인지 아닌지를 판단하는 알고리즘입니다. 소수 판별 알고리즘 중에는 결정론적(deterministic) 방식도 있는데, 이러한 방식은 해당 수가 소수인지 합성수(composite)인지를 항상 정확하게 판별해 줍니다.
AKS 소수 판별법
현재까지 알려진 가장 빠른 결정론적 소수 판별법은 2004년에 발표되었습니다. 세 명의 컴퓨터 과학자인 아그라왈(Agrawal), 카얄(Kayal), 색세나(Saxena)가 개발한 AKS 소수 판별법은 O~(log(n)6) 시간에 동작하며, 여기서 O~(f(n))은 어떤 정수 k에 대해 O(f(n)·log(f(n))k)로 표현됩니다. 이는 획기적인 돌파구였지만, 정보 보안 분야의 요구 수준에 비하면 여전히 속도가 느린 편입니다.
암호학에서 소수가 중요한 이유
소수가 각광받는 이유는 암호학에서 폭넓게 활용되기 때문입니다. 대표적인 암호 시스템인 RSA 알고리즘은 키로 소수를 필요로 하며, 일반적으로 더 높은 보안성을 확보하기 위해 1024비트를 초과하는 매우 큰 소수를 사용합니다.
그러나 이처럼 큰 수를 다루는 일은 결코 쉽지 않습니다. 특히 소수 판별 과정에서 수행되는 나눗셈(/)과 나머지 연산(%)은 매우 큰 수에 대해서는 상당한 연산 부담이 됩니다.
따라서 현재 개발된 최고 수준의 소수 판별 알고리즘조차 주어진 수가 '확률적 소수(probable prime)'인지 합성수인지만 판별할 수 있는 경우가 많습니다.
소수 판별법의 종류
1. 결정론적 알고리즘(Deterministic Algorithm)
결정론적 소수 판별 알고리즘은 정수를 입력받아 항상 '소수' 또는 '합성수'라는 올바른 답을 출력합니다. 즉, 이 알고리즘은 언제나 정확한 결과를 제공한다는 것이 가장 큰 특징입니다.
2. 나눗셈 기반 알고리즘(Divisibility Algorithm)
가장 단순한 소수 판별법은 다음과 같습니다.
입력 수 n에 대해 2부터 n-1까지의 모든 정수 m이 n을 나눌 수 있는지 검사합니다. 만약 어떤 m으로 n이 나누어 떨어지면 n은 합성수이고, 그렇지 않으면 소수입니다.
다만 모든 m을 n-1까지 검사할 필요는 없으며, √n까지만 검사해도 충분합니다. n이 합성수라면 두 개의 값으로 인수분해할 수 있고, 그중 적어도 하나는 반드시 √n보다 작거나 같기 때문입니다.
3. 확률적 알고리즘(Probabilistic Algorithm)
확률적 알고리즘은 대부분의 경우 올바른 답을 제공하지만, 항상 그런 것은 아닙니다. 이러한 검사는 n이 모든 소수가 만족해야 하는 하나 이상의 조건을 충족하는지 확인합니다.
확률적 알고리즘은 다음 규칙에 따라 '소수' 또는 '합성수'를 반환합니다.
- 검사 대상 정수가 실제로 소수라면, 알고리즘은 반드시 '소수'를 반환합니다.
- 검사 대상 정수가 실제로 합성수라면, 확률 1−ε로 '합성수'를 반환하지만, 확률 ε로 '소수'라고 잘못 반환할 수도 있습니다. 오류 확률은 알고리즘을 'm'번 반복 실행함으로써 줄일 수 있으며, 오류 확률은 Σm으로 감소합니다.
페르마 소수 판별법(Fermat Primality Test)
페르마 소수 판별법은 페르마의 소정리(Fermat's Little Theorem)에 기반합니다. 소정리에 따르면, n이 소수라면 an−1 ≡ 1 (mod n)이 성립합니다. 입력 n과 a < n이 주어졌을 때, an−1 ≡ 1 (mod n)이 성립하는지 검사할 수 있습니다. 이 식이 성립하지 않으면 n은 합성수이며, 성립하면 n은 아마도 소수일 가능성이 높습니다.
안타깝게도 페르마 소수 판별법은 오류 비용이 상당히 높습니다. 많은 합성수가 '아마도 소수'로 잘못 판별될 수 있기 때문입니다. 이러한 한계를 보완하기 위해 실무에서는 밀러-라빈(Miller-Rabin) 검증처럼 더 강력한 확률적 판별법이 함께 사용되곤 합니다.