Miller-Rabin 소수 판정 (Miller-Rabin Primality Test)

정의

Miller-Rabin 소수 판정 은 N 이 소수인지 확률적/결정론적으로 판별하는 알고리즘. Fermat 작은 정리와 이차잉여 성질을 결합해 O(k log^3 N) 에 동작. k 개의 witness a 에 대해 검사하며, 특정 base 집합으로는 결정론적 판정 가능.

문제 상황과 동기

N (10^18 ~ 10^100) 이 소수인가?

• 시행 나눗셈: O(√N). N >= 10^12 면 불가.
• Fermat Test: Carmichael 수 (561, 1105, …) 에서 소수로 오판.
• Miller-Rabin: N-1 = 2^s * d 로 분해 → a^d, (a^d)^2, … 검사. 이차잉여 조건으로 Carmichael 수도 걸러냄.

핵심 통찰: 합성수 N 에 대해, a^(N-1) ≡ 1 이더라도 중간 제곱 과정에서 1 의 제곱근이 ±1 이 아니라면 합성수. 이 조건이 Fermat Test 보다 강력.

시각화

핵심 아이디어

p 가 소수이면 x^2 ≡ 1 (mod p) 의 해는 x ≡ ±1 (mod p) 뿐 (이차잉여).

N - 1 = 2^s · d  (d 홀수)
a ∈ [2, N-2], witness

1. x = a^d mod N
2. if x == 1 or x == N-1: pass (소수일 가능성)
3. for r = 1..s-1:
       x = x^2 mod N
       if x == N-1: pass
       if x == 1:   composite (1 의 비자명 제곱근 발견)
4. 끝까지 pass 안 하면 composite

N < 2^64: witness {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 로 결정론 100%.

알고리즘

miller_rabin(N, a):
    d = N - 1
    s = 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
        if x == 1: return false
    return false

is_prime(N):
    if N < 2: return false
    if N == 2: return true
    if N % 2 == 0: return false
    for a in BASES:
        if a >= N: continue
        if not miller_rabin(N, a): return false
    return true

구현

// Miller-Rabin O(k log^3 N), 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 % m;
  a %= m;
  while (b > 0) {
      if (b & 1) res = mulmod(res, a, m);
      a = mulmod(a, a, m);
      b >>= 1;
  }
  return res;
}
​
bool witness(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 i = 1; i < s; i++) {
      x = mulmod(x, x, n);
      if (x == n - 1) return true;
      if (x == 1) return false;
  }
  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 (!witness(n, a)) return false;
  return true;
}
​
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int q; cin >> q;
  while (q--) {
      ll n; cin >> n;
      cout << (is_prime(n) ? "YES" : "NO") << "\n";
  }
}

# Miller-Rabin, pow(a, b, m) 내장. N < 2^64 deterministic
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
      if x == 1:
          return False
  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 a >= n: continue
      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))

5
2
17
561
1000000007
1000000009

YES
YES
NO
YES
YES

복잡도

k: 보통 12 개 (N < 2^64). N < 2^32 면 {2, 7, 61} 로 충분.

변형

함정

1. a >= N 처리

witness a 가 N 이상이면 검사 불필요 (a mod N = a). if (a >= n) continue.

2. mulmod 오버플로우

C++ 에서 (a * b) % m 은 a, b < 10^18 이면 10^36 으로 64비트 초과. __uint128_t 또는 mulmod (이집트 곱) 필수.

3. N == 2 분기

N=2 는 유일한 짝수 소수. 짝수 체크에서 걸러지지 않도록 초기 분기 필요.

4. base 개수 줄이기

BOJ 연습 문제

참고

• 소수 판정 (시행 나눗셈, Fermat)
• Pollard Rho 소인수분해 (Miller-Rabin 과 세트)
• 모듈러 역원
• 카마이클 함수