Home 소수 판별법
Post
Cancel

소수 판별법

By Joe2357
Posted 2023-01-10 Updated 2024-02-16 14 min read

소수 판별법

소수

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

판별법

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

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

정의를 이용한 방법

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

1
2
3
4
5
6
7
8

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 < b$) 라고 했을 때, 기존 방법이라면 2부터 시작하여 $a$에 대해 탐색하고, 이후에 $b$에 대해 탐색을 진행할 것이다. 하지만 사실 $a$만 탐색을 진행해도 우리는 $b$을 탐색할 때의 결과를 얻을 수 있다. 그럼 우리는 $b$에 대한 탐색은 진행하지 않아도 된다는 것을 알 수 있다.

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

1
2
3
4
5
6
7
8

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까지의 수에 대해 에라토스테네스의 체 알고리즘을 수행해보자. 우선 표에 모든 수를 기록하자.

12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950

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

 2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950

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

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

 23 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와 같은 방식으로 진행하자.

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12

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^{2r \cdot d} \equiv -1 \pmod{n} \text{ for some } 0 \leq r < s$

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

만약 계속해서 $n-1$을 2로 나누어가면서도 나머지가 $-1$이 아니라면, 1번 식에 대한 검사를 해야할 것이다. 이 때 $2^d = 2^{r^0 d}$이므로 나머지가 $-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$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool miller(long long n, long long a){
    if (a % n == 0) {
        return true;
    }
    
    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;
        }
        if (d % 2 == 1) {  // endpoint
           return (temp == 1 || temp == n - 1);
        }
        d /= 2;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13

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 = (res * x) % mod;   
        }
        y /= 2;
        x = (x * x) % mod;
    }
    return res;    
}

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

  • $n < 1\,373\,653$일 경우, $a = 2, 3$에 대해서만 검사해보면 충분하다
  • $n < 9\,080\,191$일 경우, $a = 31, 73$에 대해서만 검사해보면 충분하다
  • $n < 4\,759\,123\,141$일 경우, $a = 2, 7, 61$에 대해서만 검사해보면 충분하다
  • $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$에 대해서만 검사해보면 충분하다
Storage, Algorithm
Algorithm
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents