핵심 인사이트
- 소수 판별(Primality Test)의 기본 최적화는 √N까지만 나눗셈을 시도하는 것 — N이 합성수라면 N=a×b에서 min(a,b) ≤ √N이 항상 성립하므로, √N 이하의 약수가 없으면 소수다.
- 밀러-라빈 테스트(Miller-Rabin Test)는 확률적 소수 판별의 표준 — O(k log²N)의 빠른 복잡도로 대용량 수(256~4096 비트)의 소수 여부를 검사하며, k번 반복으로 2^(-2k)의 오류 확률을 달성한다.
- 결정론적 밀러-라빈(Deterministic Miller-Rabin)이 실무의 답 — 특정 범위의 수에 대해 고정된 베이스 집합을 사용하면 오류 없는 결정론적 판별이 가능하며, 2^64 미만 수에 대해 {2,3,5,7,11,13,17,19,23,29,31,37} 7개면 충분하다.
Ⅰ. 기본 소수 판별
소수 정의:
1과 자기 자신만을 약수로 가지는 자연수
2, 3, 5, 7, 11, 13, ...
나이브한 접근 (O(N)):
2 ~ N-1까지 나누어 보기
is_prime(97): 2~96까지 95번 나눗셈
최적화 1 - √N까지만 (O(√N)):
증명:
N = a × b이면 min(a, b) ≤ √N
따라서: √N 이하에서 약수 없으면 소수
is_prime(97): 2~9(≈√97)까지 8번만 나눗셈
최적화 2 - 2와 홀수만:
짝수(2 제외)는 소수 불가
→ 2로 나눈 후 3, 5, 7, ... (홀수만 검사)
약 50% 추가 최적화
최적화 3 - 6k±1 패턴:
2와 3 제외한 모든 소수 = 6k±1 형태
(2: 2, 3: 3, 5: 6×1-1, 7: 6×1+1, 11: 6×2-1, ...)
검사: 2, 3, 5, 7, 11, 13, ... (6k±1)
약 33% 추가 최적화
Python 구현:
def is_prime(n):
if n < 2: return False
if n < 4: return True # 2, 3
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 # 다음 6k-1, 6k+1 쌍
return True
# 성능
is_prime(10**15 + 37): ~31,622번 나눗셈
vs 나이브: ~10^15번
📢 섹션 요약 비유: √N까지 검사 = 책 절반만 뒤지기 — 100페이지 책에서 정보 찾을 때 1~50페이지에 없으면 나머지에도 없음. 이유: 짝이 한 쪽엔 항상 50 이하. 소수도 약수 짝 중 작은 쪽은 √N 이하!
Ⅱ. 페르마 소수 판별 (Fermat Primality Test)
페르마의 소정리 (Fermat's Little Theorem):
p가 소수이고 gcd(a, p) = 1이면:
a^(p-1) ≡ 1 (mod p)
페르마 테스트:
p가 소수인지 확인:
1. 1 < a < p 인 랜덤 a 선택
2. a^(p-1) mod p 계산
3. 결과가 1이면 "아마도 소수"
4. 결과가 1이 아니면 "확실히 합성수"
문제 - 카마이클 수 (Carmichael Numbers):
합성수인데 모든 a에 대해 a^(n-1) ≡ 1 (mod n)
561 = 3 × 11 × 17: 카마이클 수
1105, 1729, 2465, ... 무한히 많음
→ 페르마 테스트는 카마이클 수에 실패
→ 보완 필요 → 밀러-라빈 테스트
모듈러 거듭제곱 (Fast Exponentiation):
a^(p-1) mod p 계산
나이브: a×a×... (p-2번 곱셈)
반복 제곱법 (Repeated Squaring):
a^b = a^(b/2) × a^(b/2) (b가 짝수)
= a^((b-1)/2) × a^((b-1)/2) × a (b가 홀수)
O(log b) 번 연산으로 계산 가능
a^100 = ((a^25)^2)^2
= a^25 계산 후 2번 제곱
📢 섹션 요약 비유: 페르마 테스트 = 대략적 소수 확인 — 소수면 항상 통과. 단, 카마이클 수(가짜 소수)가 항상 통과. 의심스럽지만 완벽하지 않은 검사!
Ⅲ. 밀러-라빈 테스트
Miller-Rabin 소수 판별 (1975):
페르마 테스트를 강화한 확률적 테스트
카마이클 수 문제 해결
핵심 원리 (강한 소수 조건):
n이 소수이고 n-1 = 2^r × d (d는 홀수)이면:
임의의 a에 대해 다음 중 하나 반드시 성립:
(1) a^d ≡ 1 (mod n)
(2) 어떤 s (0 ≤ s < r)에 대해 a^(2^s × d) ≡ -1 (mod n)
테스트 절차:
입력: n (소수 여부 확인할 수)
1. n-1 = 2^r × d로 분해 (d는 홀수)
2. 베이스 a 선택
3. x = a^d mod n 계산
4. x가 1 또는 n-1이면 → 이번 라운드 통과
5. r-1번 반복: x = x^2 mod n
x가 n-1이 되면 통과
끝까지 n-1이 안 되면 → 합성수!
6. 여러 a로 반복 → 모두 통과하면 "아마도 소수"
오류 확률:
합성수가 임의의 a에 대해 테스트 통과할 확률 ≤ 1/4
k번 반복 → 오류 확률 ≤ (1/4)^k
k=15: 오류 확률 < 10^(-9)
결정론적 버전:
특정 범위의 n에 대해 베이스 집합 고정
n < 3,215,031,751: {2, 3, 5, 7}로 충분 (오류 없음)
n < 2^64: {2,3,5,7,11,13,17,19,23,29,31,37}로 충분
Python 구현:
def miller_rabin(n, a):
if n == a: return True
if n % 2 == 0: return False
d, r = n - 1, 0
while d % 2 == 0:
d //= 2
r += 1
x = pow(a, d, n) # 빠른 모듈러 거듭제곱
if x == 1 or x == n - 1: return True
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1: return True
return False
def is_prime_deterministic(n):
if n < 2: return False
for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
if n == a: return True
if not miller_rabin(n, a): return False
return True
📢 섹션 요약 비유: 밀러-라빈 = 강화된 신분증 검사 — 페르마(기본 신분증 확인)에서 발전해 카마이클 수(정교한 위조 신분증)도 잡아냄. k번 반복으로 오류 확률 10^(-9)!
Ⅳ. AKS 소수 판별과 실용적 선택
AKS 소수 판별 (2002, Agrawal-Kayal-Saxena):
최초의 다항식 시간 결정론적 소수 판별 알고리즘
복잡도: O(log^7.5(n)) (실용적 버전: O(log^6(n)))
의의:
"소수 판별은 P에 속한다" 증명
이론적으로 완벽 (오류 없음, 다항식 시간)
실용적 한계:
밀러-라빈보다 실제로 훨씬 느림
RSA 키 생성에서 실용적으로 사용 안 함
실용적 선택:
코딩테스트:
N ≤ 10^6: 에라토스테네스 체 (전처리)
N ≤ 10^12: √N 나눗셈 (O(√N))
N ≤ 10^18: 밀러-라빈 (결정론적)
암호학 (RSA, DSA):
512~4096비트 소수: 밀러-라빈 (k=15~20 라운드)
성능: 1024비트 소수 생성 ~100ms
Python 내장:
sympy.isprime(n): 밀러-라빈 + AKS 내부 사용
from sympy import isprime
isprime(10**100 + 267) # True/False
복잡도 요약:
나이브: O(N)
√N: O(√N)
밀러-라빈: O(k log²N)
AKS: O(log^6(N)) - 실용적으로 느림
📢 섹션 요약 비유: 소수 판별 선택 = 신분증 검사 강도 — 일반인(코딩테스트): 사진 확인(√N). 공항 출국(RSA): 지문+얼굴+데이터베이스 대조(밀러-라빈). AKS는 완벽하지만 공항에서도 너무 오래 걸려 안 씀!
Ⅴ. 실무 시나리오 — RSA 소수 생성
RSA-2048 키 쌍 생성에서의 소수 판별:
요구사항:
1024비트 소수 p, q 2개 생성
(n = p × q = 2048비트)
소수 생성 파이프라인:
1. 후보 생성:
import secrets
p = secrets.randbits(1024)
p |= (1 << 1023) # 1024비트 확보 (최상위 비트 1)
p |= 1 # 홀수 만들기
2. 에라토스테네스 빠른 필터:
작은 소수 목록으로 나눗셈 검사
< 100,000 소수(9,592개)로 빠른 제거
통과율: 약 30% (70%는 빠르게 제거)
3. 밀러-라빈 테스트:
통과한 후보에 밀러-라빈 (20 라운드)
오류 확률: (1/4)^20 ≈ 10^(-12)
4. 추가 검사 (FIPS 186-5):
Lucas 소수 판별 추가 (밀러-라빈 보완)
강한 소수(Strong Prime) 검사:
p-1의 큰 소인수 존재 확인 (Pohlig-Hellman 공격 방어)
성능 (Python, 현대 PC):
1024비트 소수 1개 생성: ~50~200ms
통계:
1024비트 수 밀도: ~1/709 (소수 정리)
평균 709번 시도 → 1개 소수
빠른 필터로: ~240번 밀러-라빈 시도
OpenSSL 소수 생성:
openssl genrsa 2048
내부: BN_generate_prime_ex() → 밀러-라빈
📢 섹션 요약 비유: RSA 소수 생성 = 복권 당첨 + 신원 확인 — 1024비트 랜덤수(복권) 뽑기 → 빠른 필터(가짜 당첨 70% 제거) → 밀러-라빈 20라운드(진짜 당첨 확인). 평균 240번 시도!
📌 관련 개념 맵
소수 판별 (Primality Test)
+-- 기본: √N 나눗셈
+-- 페르마 테스트 (한계: 카마이클 수)
+-- 밀러-라빈 (표준 실용)
| +-- 확률적 (k 라운드)
| +-- 결정론적 (고정 베이스)
+-- AKS (이론적 완벽, 실용적 느림)
+-- 복잡도
| +-- √N: O(√N)
| +-- 밀러-라빈: O(k log²N)
+-- 응용
+-- RSA/DSA 소수 생성
+-- 코딩테스트 (N ≤ 10^18)
📈 관련 키워드 및 발전 흐름도
[페르마 소정리 (1640년경)]
a^(p-1) ≡ 1 (mod p)
이론적 기반
|
v
[밀러-라빈 (1975, 1980)]
Miller + Rabin
확률적 소수 판별 표준
|
v
[RSA 알고리즘 (1977)]
소수 판별 실용화
암호화 핵심
|
v
[AKS 알고리즘 (2002)]
P에 속하는 소수 판별
이론적 성취
|
v
[현재: 양자 컴퓨팅]
쇼어 알고리즘: RSA 소수 해독
Post-Quantum 연구
👶 어린이를 위한 3줄 비유 설명
- √N까지 검사 = 책 절반만 뒤지기 — 약수는 항상 짝으로 존재. 작은 쪽이 √N 이하. √N까지만 확인하면 충분!
- 밀러-라빈 = 강화 신분증 검사 — 15~20번 다른 방법으로 검사. 가짜 신분증(합성수) 통과 확률 10억분의 1!
- RSA 소수 생성 = 복권 당첨 확인 — 랜덤 숫자 뽑고 빠른 필터 후 밀러-라빈 확인. 평균 240번 시도로 1024비트 소수 발견!