소수 판정 (Primality Test)

정의

소수 판정 (Primality Test) 은 주어진 정수 N이 소수인지 합성수인지 판별하는 알고리즘. 시행 나눗셈 (Trial Division) O(√N), 확률적 Fermat Test, 결정론적 Miller-Rabin 이 대표적이며, PS 에서는 Miller-Rabin 이 사실상 표준.

문제 상황과 동기

정수 N (10^9 이하 ~ 10^18 이하) 이 소수인가?

• naive (1..N-1 전부 나눗셈): O(N). N=10^9 면 timeout.
• 시행 나눗셈 (Trial Division): 2부터 √N 까지만 검사. O(√N). N=10^12 면 10^6 회.
• Fermat Test: 확률적 O(k log^2 N), k 는 시행 횟수. Carmichael 수에서 오판 가능.
• Miller-Rabin: 결정론적 (특정 witness base) O(k log^3 N). N < 3·10^18 은 12개 base 로 완벽 판정.

핵심 통찰: N 이 합성수면 √N 이하에 약수가 반드시 하나 존재. 확률론과 정수론 (Fermat 작은 정리, 이차잉여) 을 섞어 log 시간 판정 가능.

시각화

핵심 아이디어

시행 나눗셈 (Trial Division)

N 이 합성수면, N = a · b (a ≤ b) 인 인수분해가 존재.
a ≤ √N. 따라서 2..√N 중 하나가 N 을 나눔.

Fermat Test

Fermat 작은 정리: p 가 소수이고 gcd(a, p) = 1 이면, a^(p-1) ≡ 1 (mod p).

random a 를 k 번 뽑아, a^(N-1) mod N 이 1 인지 확인.
1 이 아니면 합성수 확정.
k 번 전부 1 이면 소수 "일 가능성 높음" (확률).

문제: Carmichael 수 (561, 1105, …) 는 모든 a 에 대해 조건 만족하지만 합성수.

Miller-Rabin

N - 1 = 2^s · d (d 는 홀수) 로 분해.

witness a 에 대해,
  x = a^d mod N
  if x == 1 or x == N-1: pass
  for r = 0..s-1:
    x = x^2 mod N
    if x == N-1: pass
    if x == 1: composite (이차잉여 위반)
  fail → composite

N < 2^64 는 특정 12개 base {2,3,5,7,11,13,17,19,23,29,31,37} 로 확정 판정.

알고리즘

Trial Division (O(√N))

is_prime(N):
    if N <= 1: return false
    if N <= 3: return true
    if N % 2 == 0 or N % 3 == 0: return false
    i = 5
    while i * i <= N:
        if N % i == 0 or N % (i + 2) == 0:
            return false
        i += 6
    return true

Miller-Rabin (deterministic)

miller_rabin(N, bases):
    if N < 2: return false
    if N == 2: return true
    if N % 2 == 0: return false
    d = N - 1
    s = 0
    while d % 2 == 0:
        d /= 2
        s++
    for a in bases:
        if a >= N: continue
        x = pow(a, d, N)
        if x == 1 or x == N-1: continue
        composite = true
        for _ in range(s-1):
            x = (x * x) % N
            if x == N-1:
                composite = false
                break
        if composite: return false
    return true

구현

// Miller-Rabin, N < 3·10^18, 12-base deterministic
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u128 = __uint128_t;
​
ll mulmod(ll a, ll b, ll m) {
  return (u128)a * b % m;
}
​
ll powmod(ll a, ll b, ll m) {
  ll res = 1;
  a %= m;
  while (b > 0) {
      if (b & 1) res = mulmod(res, a, m);
      a = mulmod(a, a, m);
      b >>= 1;
  }
  return res;
}
​
bool miller_rabin(ll n, ll a) {
  if (n % a == 0) return n == a;
  ll d = n - 1, s = 0;
  while (d % 2 == 0) { d /= 2; s++; }
  ll x = powmod(a, d, n);
  if (x == 1 || x == n - 1) return true;
  for (int r = 1; r < s; r++) {
      x = mulmod(x, x, n);
      if (x == n - 1) return true;
  }
  return false;
}
​
bool is_prime(ll n) {
  if (n < 2) return false;
  if (n == 2) return true;
  if (n % 2 == 0) return false;
  for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37})
      if (!miller_rabin(n, a)) return false;
  return true;
}
​
int main() {
  int q; cin >> q;
  while (q--) {
      ll n; cin >> n;
      cout << (is_prime(n) ? "YES" : "NO") << "\n";
  }
}

# Miller-Rabin, pow(a, b, m) 내장 사용
def miller_rabin(n, a):
  if n % a == 0:
      return n == a
  d, s = n - 1, 0
  while d % 2 == 0:
      d //= 2
      s += 1
  x = pow(a, d, n)
  if x == 1 or x == n - 1:
      return True
  for _ in range(s - 1):
      x = pow(x, 2, n)
      if x == n - 1:
          return True
  return False
​
def is_prime(n):
  if n < 2:
      return False
  if n == 2:
      return True
  if n % 2 == 0:
      return False
  for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
      if not miller_rabin(n, a):
          return False
  return True
​
import sys
input = sys.stdin.readline
q = int(input())
out = []
for _ in range(q):
  n = int(input())
  out.append("YES" if is_prime(n) else "NO")
print("\n".join(out))

// BigInteger.isProbablePrime() 또는 직접 구현
import java.util.*;
import java.io.*;
public class Main {
  static long mulmod(long a, long b, long m) {
      return (long) (((__uint128_t) a * b) % m);  // 실제론 BigInteger 사용
  }
  static long powmod(long a, long b, long m) {
      long res = 1;
      a %= m;
      while (b > 0) {
          if ((b & 1) == 1) res = (res * a) % m;
          a = (a * a) % m;
          b >>= 1;
      }
      return res;
  }
  static boolean millerRabin(long n, long a) {
      if (n % a == 0) return n == a;
      long d = n - 1, s = 0;
      while (d % 2 == 0) { d /= 2; s++; }
      long x = powmod(a, d, n);
      if (x == 1 || x == n - 1) return true;
      for (int r = 1; r < s; r++) {
          x = (x * x) % n;  // mulmod 필요 (오버플로우)
          if (x == n - 1) return true;
      }
      return false;
  }
  static boolean isPrime(long n) {
      if (n < 2) return false;
      if (n == 2) return true;
      if (n % 2 == 0) return false;
      long[] bases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
      for (long a : bases)
          if (!millerRabin(n, a)) return false;
      return true;
  }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int q = Integer.parseInt(br.readLine());
      StringBuilder sb = new StringBuilder();
      while (q-- > 0) {
          long n = Long.parseLong(br.readLine());
          sb.append(isPrime(n) ? "YES" : "NO").append('\n');
      }
      System.out.print(sb);
  }
}

5
2
17
561
1000000007
1000000009

YES
YES
NO
YES
YES

복잡도

k: witness 개수 (보통 12~20).

변형

함정

1. 오버플로우

a^d mod N 에서 a, d 가 크면 중간 곱 a·b 가 long long 범위 초과. __uint128_t 또는 mulmod 필수.

2. witness base 선택

N < 2^64 는 12개 base {2,3,5,7,11,13,17,19,23,29,31,37} 로 완벽. 더 작은 범위는 3~4개로 충분 (N < 9080191: {31,73}).

3. N == 2 처리

N=2 는 소수인데 짝수. 초기 분기 필수.

4. Carmichael 수

Fermat Test 단독은 561, 1105 같은 Carmichael 수를 소수로 오판. Miller-Rabin 은 이차잉여 체크로 막음.

BOJ 연습 문제

참고

• 소인수분해
• 유클리드 호제법
• 에라토스테네스의 체