소수 판정법¶

이 글에서는 어떤 수가 소수인지 아닌지 판정하는 여러 알고리즘을 설명합니다.

시행 나눗셈¶

정의에 따르면 소수는 $1$과 자기 자신 외에는 약수를 갖지 않습니다. 합성수는 적어도 하나의 약수를 추가로 가지며, 이를 $d$라고 부르겠습니다. 당연히 $\frac{n}{d}$ 역시 $n$의 약수입니다. $d \le \sqrt{n}$ 또는 $\frac{n}{d} \le \sqrt{n}$ 중 하나가 성립한다는 것은 쉽게 알 수 있으므로, 약수 $d$와 $\frac{n}{d}$ 중 하나는 $\le \sqrt{n}$입니다. 이 정보를 이용하여 소수 판정을 할 수 있습니다.

$2$부터 $\sqrt{n}$ 사이의 수 중 $n$의 약수가 있는지 확인하여 자명하지 않은 약수를 찾습니다. 그러한 약수가 있다면 $n$은 확실히 소수가 아니며, 그렇지 않다면 소수입니다.

bool isPrime(int x) {
    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0)
            return false;
    }
    return x >= 2;
}

이것은 가장 단순한 형태의 소수 판정입니다. 이 함수는 상당히 최적화할 수 있습니다. 예를 들어 유일한 짝수 소수는 2이므로 루프에서 홀수만 검사하면 됩니다. 이러한 여러 최적화 방법은 정수 인수분해에 관한 글에 설명되어 있습니다.

페르마 소수 판정법¶

이것은 확률적 판정법입니다.

페르마의 소정리(오일러 피 함수도 참고하십시오)에 따르면, 소수 $p$와 서로소인 정수 $a$에 대해 다음 방정식이 성립합니다:

$$a^{p-1} \equiv 1 \bmod p$$

일반적으로 이 정리는 합성수에 대해서는 성립하지 않습니다.

이를 이용하여 소수 판정법을 만들 수 있습니다. 정수 $2 \le a \le p - 2$를 하나 골라 방정식이 성립하는지 확인합니다. 등식이 성립하지 않는다면, 즉 $a^{p-1} \not\equiv 1 \bmod p$라면, $p$는 소수일 수 없음을 알 수 있습니다. 이 경우 밑 $a$를 $p$가 합성수임을 보이는 페르마 증인(Fermat witness)이라고 부릅니다.

그러나 합성수에 대해서도 방정식이 성립할 수 있습니다. 따라서 방정식이 성립하더라도 소수 판정의 증거가 되지는 않습니다. $p$가 아마도 소수(probably prime)라고만 말할 수 있습니다. 그 수가 실제로는 합성수로 밝혀진다면, 밑 $a$를 페르마 거짓말쟁이(Fermat liar)라고 부릅니다.

가능한 모든 밑 $a$에 대해 판정을 수행하면 어떤 수가 소수임을 실제로 증명할 수 있습니다. 그러나 이는 단순히 시행 나눗셈을 하는 것보다 훨씬 많은 노력이 들기 때문에 실제로는 사용하지 않습니다. 대신 $a$를 무작위로 골라 판정을 여러 번 반복합니다. 합성수임을 보이는 증인을 찾지 못한다면, 그 수는 실제로 소수일 가능성이 매우 높습니다.

bool probablyPrimeFermat(int n, int iter=5) {
    if (n < 4)
        return n == 2 || n == 3;

    for (int i = 0; i < iter; i++) {
        int a = 2 + rand() % (n - 3);
        if (binpower(a, n - 1, n) != 1)
            return false;
    }
    return true;
}

거듭제곱 $a^{p-1}$을 효율적으로 계산하기 위해 이진 거듭제곱을 사용합니다.

그러나 한 가지 나쁜 소식이 있습니다. $n$과 서로소인 모든 $a$에 대해 $a^{n-1} \equiv 1 \bmod n$이 성립하는 합성수가 존재하며, 예를 들어 $561 = 3 \cdot 11 \cdot 17$이 그러한 수입니다. 이러한 수를 Carmichael 수라고 합니다. 페르마 소수 판정법은 엄청난 운이 따라서 $\gcd(a, n) \ne 1$인 밑 $a$를 고른 경우에만 이러한 수를 식별할 수 있습니다.

페르마 판정법은 매우 빠르고 카마이클 수가 매우 드물기 때문에 실제로 여전히 사용되고 있습니다. 예를 들어 $10^9$ 미만에는 그러한 수가 646개밖에 존재하지 않습니다.

밀러-라빈 소수 판정법¶

밀러-라빈 판정법은 페르마 판정법의 아이디어를 확장합니다.

홀수 $n$에 대해 $n-1$은 짝수이므로 2의 거듭제곱을 모두 인수로 뽑아낼 수 있습니다. 다음과 같이 쓸 수 있습니다.

$$n - 1 = 2^s \cdot d,~\text{with}~d~\text{odd}.$$

이를 이용하면 페르마의 소정리의 방정식을 인수분해할 수 있습니다:

$$\begin{array}{rl} a^{n-1} \equiv 1 \bmod n &\Longleftrightarrow a^{2^s d} - 1 \equiv 0 \bmod n \\\\ &\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-1} d} - 1) \equiv 0 \bmod n \\\\ &\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) (a^{2^{s-2} d} - 1) \equiv 0 \bmod n \\\\ &\quad\vdots \\\\ &\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) \cdots (a^{d} + 1) (a^{d} - 1) \equiv 0 \bmod n \\\\ \end{array}$$

$n$이 소수라면 $n$은 이 인수들 중 하나를 나누어야 합니다. 그리고 밀러-라빈 소수 판정법에서는 바로 이 명제를 검사하는데, 이는 페르마 판정법의 명제보다 더 엄격한 버전입니다. 밑 $2 \le a \le n-2$에 대해 다음 식이

$$a^d \equiv 1 \bmod n$$

성립하거나, 다음 식이

$$a^{2^r d} \equiv -1 \bmod n$$

어떤 $0 \le r \le s - 1$에 대해 성립하는지 확인합니다.

위의 등식 중 어느 것도 만족하지 않는 밑 $a$를 찾았다면, $n$이 합성수라는 증거를 찾은 것입니다. 이 경우 $n$이 소수가 아님을 증명한 것입니다.

페르마 판정법과 마찬가지로, 합성수에 대해서도 이 연립방정식이 만족될 수 있습니다. 그 경우 밑 $a$를 강한 거짓말쟁이라고 합니다. 밑 $a$가 방정식(그중 하나)을 만족하면, $n$은 단지 강한 확률적 소수일 뿐입니다. 그러나 Carmichael 수처럼 자명하지 않은 모든 밑이 거짓말을 하는 수는 존재하지 않습니다. 실제로 밑 중 많아야 $\frac{1}{4}$만이 강한 거짓말쟁이가 될 수 있음을 보일 수 있습니다. $n$이 합성수라면 무작위로 고른 밑이 합성수임을 알려 줄 확률이 $\ge 75\%$이므로, 무작위 밑으로 판별을 반복하면 오류 확률을 원하는 만큼 작게 만들 수 있습니다.

제한된 범위에서는 무작위성을 아예 피할 수 있습니다. 완전 탐색으로 찾은 몇 개의 고정된 밑으로 이루어진 작은 집합이 그 범위의 모든 수를 확정적으로 판정합니다. Miller는 $\le O((\ln n)^2)$인 모든 밑을 확인하면 판별법이 결정론적이 됨을 보였고, Bach는 구체적인 한계 $a \le 2\ln(n)^2$를 제시했습니다. 이는 여전히 많은 수의 밑이므로, 더 작은 집합을 찾기 위해 상당한 계산이 이루어졌습니다. 64비트 정수의 경우 일곱 개의 밑으로 충분합니다: 2, 325, 9375, 28178, 450775, 9780504, 1795265022.

다음은 64비트 정수에 대한 구현입니다.

using u64 = uint64_t;
using u128 = __uint128_t;

u64 binpower(u64 base, u64 e, u64 mod) {
    u64 result = 1;
    base %= mod;
    while (e) {
        if (e & 1)
            result = (u128)result * base % mod;
        base = (u128)base * base % mod;
        e >>= 1;
    }
    return result;
}

bool check_composite(u64 n, u64 a, u64 d, int s) {
    a %= n;
    if (a == 0) // n divides the base, so this base can say nothing about n
        return false;
    u64 x = binpower(a, d, n);
    if (x == 1 || x == n - 1)
        return false;
    for (int r = 1; r < s; r++) {
        x = (u128)x * x % n;
        if (x == n - 1)
            return false;
    }
    return true;
};

bool MillerRabin(u64 n) { // returns true if n is prime, else returns false.
    if (n < 2)
        return false;

    int s = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }

    for (u64 a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022})
        if (check_composite(n, a, d, s))
            return false;
    return true;
}

$2$를 제외하면 일곱 개의 밑 중 소수인 것은 없으므로, 밑이 판별 중인 바로 그 $n$의 배수일 수 있습니다. 예를 들어 $5$는 $9375$를 나누고 $13$은 $325$를 나눕니다. 이러한 밑은 $0$으로 환원되어 $n$에 대해 아무것도 알려 줄 수 없으므로, check_composite는 이를 건너뛰고 나머지 밑들이 판정하도록 합니다.

이는 나머지가 0인 경우를 모두 건너뛰는 것보다 범위가 좁으며, 의도적으로 그렇게 한 것입니다. $n$이 $a$를 나누지는 않지만 $a^d$를 나눈다면 $n$은 소수일 수 없습니다. $a^d$를 나누는 소수는 반드시 $a$도 나누기 때문입니다. 이 경우 0은 답이 누락된 것이 아니라 합성수임을 증명하는 것이며, 함수는 이를 그대로 보고합니다. 정보를 버리는 것은 첫 번째 분기뿐이며, 이 고정된 집합 대신 무작위 밑을 넣어도 같은 check_composite가 여전히 올바르게 동작하는 이유도 여기에 있습니다.

처음 12개의 소수, 즉 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37을 밑으로 사용해도 64비트 정수에 대해 동작하지만, 그 대가로 라운드를 다섯 번 더 수행해야 합니다. 32비트 정수의 경우 처음 네 개의 소수 밑 2, 3, 5, 7로 충분합니다. 이들을 모두 통과하는 가장 작은 합성수는 $3\,215\,031\,751 = 151 \cdot 751 \cdot 28351$입니다.

$n$의 해시로 인덱싱되는 작은 테이블에서 밑을 고르면 라운드 수를 더 줄일 수 있으며, 이렇게 하면 어떤 64비트 수든 세 번의 테스트만으로 판정할 수 있습니다. cp-algo/number_theory/primality.hpp를 참고하십시오. 이 구현은 기본적으로 위의 일곱 개 밑을 사용하고, 해시 테이블을 사용할 수 있을 때는 그쪽으로 전환하며, $2^{32}$ 미만에서는 고전적인 2, 7, 61로 대체합니다. 테이블 자체는 Bradley Berg가 만든 것으로, Steve Worley의 이전 32비트 테스트를 확장한 것입니다.

소수 판정법¶

시행 나눗셈¶

페르마 소수 판정법¶

밀러-라빈 소수 판정법¶

연습 문제¶