어떤 자연수 n이 소수인지 판별하는 좋은 방법이 여러 가지 있습니다. 우선 가장 근본인 2부터 n - 1까지의 수로 n을 나누어보는 방법이 있습니다. 약수가 1과 n 말고 또 있는지 확실히 알 수 있습니다. 그런데 n이 만약 1,000,000,007 같은 수라면, 혹은 2136279841-1처럼 답도 없이 큰 소수에 대해서는 실행 가능성이 좀 낮거나 아예 없습니다.
그리고 구현하기 쉽고 성능도 확실한 "에라토스테네스의 체"가 있습니다. 근데 이건 특정한 소수 하나를 판별하기 보다 N까지의 소수를 모두 구하는데 좋은 방법입니다. n까지의 모든 소수를 빠짐 없이 확실하게 구할 수 있는 결정론적인 성질이 있습니다. 하지만 역시 자릿수가 좀 커진다 싶으면 매우 느려지는 단점이 있습니다. 가장 최적화된 에라토스테네스의 체로 n까지의 소수들을 구할 때의 시간복잡도는 O(Nlog(logN))입니다. log가 두 번이나 들어갔으니 엄청 빠르긴 하지만 n이 그냥 그대로 들어가버려서 일단 선형시간(일차)이 소모된다는 점, 그리고 무엇보다 n이 20자리 정수쯤 되어버리면 메모리를 엄청 먹습니다. 딱 n개의 정수를 저장할 공간이 필요합니다.
이와 같이 잘 알려진 두 방법의 단점을 극복하기 위해 다양한 소수판별법이 등장합니다. 에라토스테네스나 깡나눗셈 연산 같이 결정론적 방법들도 있지만 그들은 대부분 다항시간이 소모됩니다. PS에서 나올법한 소수들에 대해 적당히 쓸만한 "확률적 소수판별법"이 있습니다.
1. 밀러-라빈 소수판별법
이 알고리즘은 원래 밀러가 일반 리만 가설을 근거로 만든 결정론적 알고리즘이었으나 후에 라빈이 수정해 확률적 알고리즘이 되었습니다. 소수가 갖는 무슨 특징을 활용합니다. 저는 수학적 지식이 부족해 도저히 이해할 수가 없어서 그냥 이해한 만큼만 써보겠습니다. ㅎㅎ
n의 소수 여부를 확인하기 위해 n보다 작은 어떤 자연수 a가 필요합니다. 이걸 증거로 활용해 어떤 연산을 실행한 결과가 조건을 만족하면 반드시 n은 합성수입니다. 연산과 조건은 그런데 반대로 조건을 만족하지 않는다면 반드시 n이 소수인 게 아니라 소수일 가능성이 있습니다. a가 하나가 아니라 여러 개라면 그 가능성이 점점 커지는 식입니다.
이 가능성이 얼마나 되는지 잘 모르겠지만 이미 확인된 바로는 다음 범위에 대해서는 a가 이렇게만 쓰여도 100% 소수를 판별해낼 수 있다고 합니다. (아마 a에는 소수가 쓰입니다.이는 것 같습니다.)
n < 1,373,653일 경우 a = [2, 3]
n < 9,080,191일 경우 a = [31, 73]
n < 4,759,123,141일 경우 a = [2, 7, 61] (uint 범위 내의 모든 소수 판별)
n < 2,152,302,898,747일 경우 a = 11까지의 소수
n < 3,474,749,660,383일 경우 a = 13까지의 소수
n < 341,550,071,728,321일 경우 a = 17까지의 소수
n < 3,825,123,056,546,413,051일 경우 a = 23까지의 소수
n < 318,665,857,834,031,151,167,461일 경우 a = 37까지의 소수 (long long 범위 내의 모든 소수 판별)
n < 3,317,044,064,679,887,385,961,981일 경우 a = 41까지의 소수
이보다 더 큰 범위에서도 쓸 수 있는 것 같지만 일단 저에겐 쓸모가 없군요.
2. 원리 찍먹
2를 제외한 모든 소수는 홀수입니다. n이 2가 아닌 소수라고 가정해봅시다. 그렇다면 n - 1은 반드시 짝수가 되고 다음과 같은 등식이 성립합니다.
n - 1 = 2sd (d는 홀수)
그리고 또 잘은 모르지만 페르마 소정리는 이런 내용이랍니다.
[보조정리1 - 페르마의 소정리]
p가 소수이고 a가 정수라면 ap ≡ a (mod p)
p가 a의 약수가 아니면 양변을 나누어 ap-1 ≡ 1 (mod p) (a ≠ 0)
그러니까 p가 소수가 아니라면 이게 안될 수도 있다는 건데 n에 대해 페르마의 소정리를 적용해본 결과, 안된다면 n은 확실한 합성수가 됩니다. 아무튼 이걸 이용하면 아까 식을 이렇게 쓸 수 있습니다. 여기서 a는 소수판별의 증거가 될 n 미만의 자연수입니다.
n이 소수라면 n 미만의 자연수 a에 대해 an ≡ a (mod n)
a는 n보다 작으니 약수일 수가 없고 0도 아니므로 양변을 나눌 수 있음
an-1 ≡ 1 (mod n)
이제 여기가 어려운데, 다음과 같은 정리가 하나 필요합니다.
[보조정리2]
소수 p가 있을 때 n2 ≡ 1 (mod p)라면, n ≡ -1 (mod p) 또는 n ≡ 1 (mod p)이다.
∵ n2 - 1 = k*p로 표현할 수 있는데, n2 - 1 = (n - 1)(n + 1)이므로 n - 1이 p의 배수이거나 n + 1이 p의 배수가 된다.
n + 1 = h*p라면 n = h*p + 1이므로 n ≡ 1 (mod p)가 성립
n - 1 = h*p라면 n = h*p - 1이므로 n ≡ -1 (mod p)가 성립한다.
그럼 또 아까 그 식을 다시 바꿔볼까요.
an-1 = a2sd = (ad2s-1)2≡ 1 (mod n)
이렇게 지수에 있는 2s에서 지수를 뽑아낼 수 있습니다. 자 이제 중요한 부분. 위 식에서 괄호로 묶인 부분의 제곱이 n으로 나눈 나머지가 1이랍니다. 그럼 거기서 1을 빼서 인수분해를 해주면 이런 식이 나옵니다.
(ad2s-1)2 - 1 ≡ 0 (mod n), 좌변은 n의 배수
(ad2s-1 - 1)(ad2s-1+1) = n*q (q는 n과 서로소)
좌변의 두 인수 중 하나만이 n을 소인수로 갖습니다. 보조정리2에 의해서 각각의 경우에 따라 다음 두 식 중 하나가 반드시 성립해야 합니다. 맨 처음에 가정했던대로 n이 소수가 맞다면 말이죠.
ad2s-1 ≡ -1 (mod n) 또는 ad2s-1 ≡ 1 (mod n)
전자인 경우, 더 이상 지수를 빼내서 같은 과정을 실행할 수 없습니다. 후자인 경우 s가 0이 되지 않는 한 계속 이 과정을 반복할 수 있습니다. 모듈러 연산의 결과가 계속 1이 나온다면 여기까지 오게 됩니다.
ad ≡ -1 (mod n) 또는 ad ≡ 1 (mod n)
d는 맨 위에서 홀수로 시작되었으니 더 이상 지수를 뽑아내지 못합니다. 여기까지 왔다면 n은 소수일 가능성이 있습니다. 이제 a는 n이 소수임을 가리키는 강한 증거가 됩니다. 이게 왜 강한 증거냐면 몇 개의 a에 대해 이게 성립했다고 해서 반드시 소수인 것은 아니기 때문입니다. 이런 특징 때문에 밀러-라빈 소수판별법은 확률적 알고리즘입니다.
하지만 아까 위에서 보여준 것과 같이 PS에서 다루는 소수는 몇 개의 a로 결정론적 판별이 가능하니 상관 없습니다.
3. 소스코드
빠른 거듭제곱과 a로 쓰일 소수 목록이 좀 필요합니다. long long 범위에서 판별하는 것으로 해봅시다.
# 37까지의 소수 목록 prime
# 이걸로 long long 범위의 모든 소수를 판별할 수 있습니다.
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
# 빠른 거듭제곱
# x의 y제곱을 mod로 나눈 몫 반환
def fast_mod_power(x, y, mod):
ret = 1
x %= mod
while y:
if y & 1:
ret *= x
ret %= mod
y >>= 1
x **= 2
x %= mod
return ret
# 밀러-라빈 소수판별 알고리즘
def miller_rabin(n, a):
d = n - 1 # d는 짝수
while d % 2 == 0:
d >>= 1 # 일단 d를 홀수가 될 때까지 2로 나눕니다.
# 앞선 설명과는 반대로 지수에서 2를 뽑으며 진행하는 것이 아니라
# 지수에 2를 끼워 넣으며 진행합니다.
# 이유는 나중에 설명할게요.
x = fast_mod_power(a, d, n)
if x == 1 or x == -1:
return True # n이 소수가 아니라면 이게 안 나옵니다.
while d < n - 1:
x = fast_mod_power(x, 2, n)
d <<= 1
if x == 1: # 24행에서 처리되지 않고 넘어왔는데 여기서 1이 뜬다는 건
# 여기서 지수를 뽑아다 모듈러를 돌렸을 때
# 1 또는 -1이 안나왔다는 의미이므로 반드시 합성수입니다.
return False
elif x == n - 1:
return True
return False # 끝까지 다 해봤는데 한 번도 -1이 안나왔다면
# 반드시 합성수라는 의미입니다.
# n이 소수인지 판별
def is_prime(n):
if a in prime:
return True
if n == 1 or n & 1 == 0:
return False
for a in prime:
if not miller_rabin(n, a):
return False
return True # 37까지의 모든 소수에 대해 한 번도 걸러지지 않았다면
# 318,665,857,834,031,151,167,461미만까지 결정론적으로 소수가 맞습니다.
