소수 판별법

소수

• 소수는 $1$보다 큰 자연수 중 $1$과 자기 자신만을 약수로 가지는 수다. 예를 들어, $5$는 $1 \times 5$ 또는 $5 \times 1$로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 $5$는 소수이다. $1$과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

판별법

기본적인 방법은 소수의 정의를 이용하여 $1$을 제외한 자연수 중 $1$과 본인을 제외한 수로 나누어 떨어지지 않는 수를 찾는 방법이다. 이외에도 여러가지 방법이 존재한다.

이 글에서는 실제로 소수를 판별하기 위해 사용했던 방법에 대해 설명한다.

정의를 이용한 방법

기본적인 방법으로, $2$부터 판별하는 수까지 직접 나눠가며 나머지가 $0$이 나오지 않는지 검사한다. 본인을 제외한 모든 수에서 나머지가 $0$이 나오지 않는다면 소수라고 판별할 수 있다.

bool isPrime(int x) {
    for (int i = 2; i < x; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

• 시간 복잡도 : $O(N)$

정의를 더 이용하는 방법

위 방법으로부터 조금 더 나아가자. 탐색을 진행하면서, 굳이 $2$부터 자기 자신까지 탐색할 필요가 있을까? 소수라고 확정할 수 있는 어느 특정 지점까지만 탐색한다면 계산 시간을 많이 줄일 수 있을 것이다.

잠시 합성수에 대해 생각해보자. 합성수는 $1$과 자신을 제외한 다른 정수인 약수가 존재하는 수이다. 만약 합성수 $N$의 약수들 중 한 쌍을 각각 $a$, $b$ ($a \leq b$) 라고 했을 때, 기존 방법이라면 $2$부터 시작하여 $a$에 대해 탐색하고, 이후에 $b$에 대해 탐색을 진행할 것이다. 하지만 사실 $a$만 탐색을 진행해도 우리는 $b$을 탐색할 때의 결과를 얻을 수 있다. 그럼 우리는 $b$에 대한 탐색은 진행하지 않아도 된다는 것을 알 수 있다.

그럼 그 탐색하지 않아도 되는 지점이 어디일까? 답은 $a$와 $b$가 같아지는 지점, 즉 $\sqrt{N}$이다. 이 때까지 탐색한 수들을 이용하여 더 큰 약수가 있거나 없음을 보일 수 있기 때문에, 탐색 범위를 줄일 수 있다.

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

• 시간 복잡도 : $O(\sqrt{N})$

에라토스테네스의 체

어떤 하나의 정수에 대해 소수를 판별하는 상황이 아닌, 특정 범위의 정수에 대해 각 수가 소수임을 이용해야하는 경우 유용한 방법이다. 하나의 수를 각각 따로 판별하는 방법이 아니라, 이미 찾은 소수를 이용하여 합성수를 지워가는 방식을 사용한다.

예시로, 아래와 같이 $1$부터 $50$까지의 수에 대해 에라토스테네스의 체 알고리즘을 수행해보자. 우선 표에 모든 수를 기록하자.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

먼저 맨 앞칸부터 차례대로 진행한다. 첫 수는 $1$인데, $1$은 소수도 합성수도 아니므로 제외하고 진행한다. 소수가 아니라면 표에서 지워버린다.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

다음 수는 $2$인데, $2$는 표 상에서 남아있으므로 소수라고 생각할 수 있다. ($2$보다 작은 수로 나누어 떨어지지 않았다는 의미이므로, 소수라고 할 수 있다). $2$는 소수이므로 지우지 않는다.

다만 $2$의 배수들은 약수로 $2$를 가지게 될 것이므로, 그들은 모두 소수라고 할 수 없다. 따라서 범위 안에 있는 수들 중 $2$의 배수는 모두 지울 수 있을 것이다.

	$2$	3		5		7		9
11		13		15		17		19
21		23		25		27		29
31		33		35		37		39
41		43		45		47		49

다음 수는 $3$이다. $3$도 아직 지워지지 않았으므로 소수라고 할 수 있다. $2$와 같은 방식으로 진행하자.

	2	$3$		5		7
11		13				17		19
		23		25				29
31				35		37
41		43				47		49

다음 수는 $4$이다. 그런데 $4$는 이미 지워졌다. $4$는 $2$의 배수이기 때문이다. $4$의 배수도 이미 지워졌을 것이므로 다음 수로 진행할 수 있다.

같은 방법으로 모든 수에 대해서 계속 탐색을 진행하자.

	2	3		5		7
11		13				17		19
		23						29
31						37
41		43				47

최종적으로는 아래와 같은 수들이 남는다. 이들은 모두 소수이다.

위 예시에서는 수들을 쉽게 보기 위해 2차원 표 형식을 사용했지만, 실제로 구현할 때는 1차원 배열로 true / false만 기록하는 방법으로 구현할 수 있다.

bool isPrime[MAX_IDX];

void main() {
    for (int i = 2; i < MAX_IDX; ++i) {
        if (isPrime[i] == true) {
            for (int j = i * 2; j < MAX_IDX; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return;
}

• 시간 복잡도 : $O(N^2)$
• 다만 범위 내의 수에 대한 소수 판별을 모두 할 수 있다는 장점이 있음

밀러-라빈 소수판별법

소수가 가지는 특징, 그 중에서 페르마 소정리를 이용하여 소수인지 판별하는 방법이다. 소수는 $2$를 제외하고는 모두 홀수이다. 이 때 홀수 $n$을 소수인지 판별할 때 사용할 수 있는 방법이다.

홀수 $n$에 대하여, $n-1$은 $2^s d$의 꼴로 적을 수 있다. 이 때 $d$를 홀수라고 한다면 $n-1 = 2^s d$에서 $s$와 $d$는 유일한 해를 가진다. $n-1$을 $2$로 계속해서 나누는 꼴이 되는 것이다. 이 때 $n$이 소수라면 아래 식 중 하나는 성립한다.

• $a^d \equiv 1 \pmod{n}$
• $a^{d \times 2^r} \equiv -1 \pmod{n}~ \text{for some } 0 \leq r < s$

이 식들 중 하나가 성립한다는 것은 페르마 소정리를 이용하여 증명할 수 있다고 한다. 페르마 소정리는 $n$이 소수라면 서로소 $a$에 대해 $a^{n-1} \equiv 1 \pmod{n}$이 성립한다는 이론이다. 그래서 $a^{n-1}$의 제곱근은 항상 $n$으로 나눈 나머지가 $1$ 또는 $-1$이 나온다. 그 중 $-1$이 나왔다면 위 조건의 2번식이 성립한다는 것을 보일 수 있으므로 $n$은 소수라고 얘기할 수 있다.

만약 계속해서 $n-1$을 $2$로 나누어가면서도 나머지가 $-1$이 아니라면, 1번 식에 대한 검사를 해야할 것이다. 즉 $2^d \equiv 1 \pmod{n}$이 성립해야할 수밖에 없다.

밀러-라빈 판별법은 아래 2개의 식을 이용하여, 2개의 식이 모두 성립할 때 $n$이 합성수라는 강한 증거를 내밀 수 있다고 한다. 두 식이 성립하지 않는다면 강한 거짓증거라고 하고, $n$은 아마 소수일 것이라고 예측한다.

• $a^d \not\equiv 1 \pmod{n}$
• $a^{2^r d} \not\equiv -1 \pmod{n} \text{ for all } 0 \leq r < s$

bool miller_rabin(long long n, long long a){
    long long d = n - 1;
    
    while (true) {
        long long temp = power(a, d, n);
        if (temp == n - 1) { // a ^ ((2^r)d) = -1 (mod n)
            return true;
        } else if (d % 2 == 1) {  // endpoint
           return (temp == 1);
        }
        d /= 2;
    }
}

이 때 power 함수가 사용되는데, 입력으로 주어지는 $n$의 값이 매우 크기 때문에 빠른 제곱계산을 해주어야한다. 이것은 분할정복을 이용한 제곱함수를 이용하도록 하자. 숫자가 매우 커지므로 계속해서 mod값을 취해주자.

숫자가 매우 커진다는건 곱셈연산에서마저도 해당되는 말이다. 밀러-라빈 소수판별까지 사용할 정도면 대부분 수의 범위가 $10^{18}$까지인 경우가 많다. 여기서는 unsigned long long마저도 오버플로가 발생한다. 그래서 곱셈마저도 power 함수처럼 분할정복을 활용한 함수를 따로 구현해주도록 하자.

long long multiply(long long x, long long y, long long mod) {
    long long res = 0;
    x %= mod;
    
    while (y > 0) {
        if (y % 2 == 1) {
            res = (res + x) % mod;   
        }
        y /= 2;
        x = (x + x) % mod;        
    }
    return res;
}

long long power(long long x, long long y, long long mod){
    long long res = 1;
    x %= mod;
    
    while (y > 0) {
        if (y % 2 == 1) {
            res = multiply(res, x, mod);   
        }
        y /= 2;
        x = multiply(x, x, mod);
    }
    return res;
}

밀러-라빈 알고리즘의 반환값이 true라면, 그 수는 아마 소수일 것이다라는 것을 의미한다. 반대로 얘기하면, 함수의 반환값이 false라면 그 수는 반드시 합성수를 의미한다. 아래는 소수를 판별하기 위해 사용해야하는 $a$의 리스트다.

• $n < 1\,373\,653$일 경우, $a = 2, 3$에 대해서만 검사해보면 충분하다
• $n < 9\,080\,191$일 경우, $a = 31, 73$에 대해서만 검사해보면 충분하다
• $n < 4\,759\,123\,141$일 경우, $a = 2, 7, 61$에 대해서만 검사해보면 충분하다 (unsigned int 범위)
• $n < 2\,152\,302\,898\,747$일 경우, $a = 2, 3, 5, 7, 11$에 대해서만 검사해보면 충분하다
• $n < 3\,474\,749\,660\,383$일 경우, $a = 2, 3, 5, 7, 11, 13$에 대해서만 검사해보면 충분하다
• $n < 341\,550\,071\,728\,321$일 경우, $a = 2, 3, 5, 7, 11, 13, 17$에 대해서만 검사해보면 충분하다
• $n$이 unsigned long long 범위일 때, $a=2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37$에 대해서 검사하면 된다 ($2$ ~ $37$까지의 소수)