[Algorithm] Miller-Rabin 소수판별법
이번 포스트는 baekjoon 에서 알고리즘 문제를 풀다가 소수와 관련된 문제를 풀면서 시간 초과가 떠서 빠르게 소수를 찾는 방법이 무엇이 있는지 찾아보다가 Miller-Rabin 소수판별법 대해 알게 되어 스스로 공부하는 차원에서 정리도 하고, 이후에 해당 내용을 빨리 찾을 수 있도록 하기 위해 포스트로 작성해보게 되었습니다. Miller-Rabin 소수판별법에 대해서 정리해보고 이를 python 코드로도 한 번 구현해보도록 하겠습니다.
1. 개요
소수는 대부분 아는 개념이니 따로 설명하지는 않도록 하겠습니다.
Miller-Rabin 소수판별법은 큰 수에 대해 매우 빠르게 소수 여부를 판단할 수 있는 확률적 소수 판별법입니다. 페르마의 소정리를 기반으로 하며, 테스트 반복 횟수를 늘리면 오류 확률을 무시할 수 있을 정도로 낮출 수 있습니다.
2. 이론적 배경
2.1 페르마의 소정리
페르마의 소정리는 소수 판별의 기초가 되는 정리입니다.
\[a^{n-1} \equiv 1 \pmod{n}\]만약 ( n )가 소수이고, ( 1 < a < n )인 정수 ( a )에 대해 다음이 성립합니다:
하지만 이 조건만으로는 충분하지 않으며, 소수가 아닌 합성수도 위 조건을 만족하는 경우가 있습니다. 이러한 합성수를 카마이클 수 라고 하며, 대표적으로 561 이라는 수가 있습니다.
2.2 Miller-Rabin 소수판별법
Miller-Rabin 소수판별법은 소수의 특별한 성질을 이용합니다. n 이 홀수인 소수라고 할 때 n-1 은 $ 2^sd $ 라고 할 수 있으며 이 때, s 는 정수이고 d는 홀수가 되며 소수인 n 은 다음 식을 만족하게 됩니다.
\[a^{d} \equiv 1 \pmod{n}\]하지만 a 는 1 < a < n 이기 때문에 아주 운이 나쁜 경우 a 를 잘못 고르게 되어 위 식을 만족하지 못할 수 있습니다. 그에 대한 예시로 n 은 97로 소수이고, a 가 5일 경우를 보도록 하겠습니다.
- a = 97 (소수)
- n-1 = 96 = $ 2^{5} \cdot 3 $ s = 32, d = 3
- a = 5
위와 같이 소수인 경우라도 식을 만족하지 못할 때가 있습니다. 이를 위해 $a^{n-1}$ 의 제곱근들을 모두 검사하는 조건을 추가합니다.
위에서 언급한 s 를 $2^r$ 으로 나타내도록 하겠습니다. 그러면 수식은 다음과 같습니다.
\[a^{2^r \cdot d} \equiv -1 \pmod{n} \ for \ some \ 0 \le r \le s-1\]소수인 경우 $a^{n-1}$ 제곱근들 중에서 하나는 무조건 $\equiv -1$ 을 만족하게 됩니다.
즉 정리를 하자면 특정 자연수 n 이 소수라면 1번과 2번식 중에서 하나는 만족하게 됩니다.
mod 연산에서 -1의 의미
mod 연산에서 -1 의 의미는 mod 연산을 당하는 수가 mod 연산을 하는 수보다 1 작을 때 표현하는 것으로 이렇게 표현하는 이유는 수론에서 수학적 대칭성을 강조하기 위해서입니다.
3. 알고리즘으로써 Miller-Rabin 소수판별법
3.1 알고리즘 절차
3.1.1 전처리 : $n-1 = 2^r \cdot d$ 꼴로 분해
3.1.2 조건 검사
임의의 정수 $a \in [2, n-2]$를 선택하고 이론적 배경에서 알아본 두 가지 조건 중 하나라도 만족하면 소수일 가능성이 있습니다.
3.1.3 여러 번 반복
특정 합성수의 경우 고르는 a 값에 따라 위 두 가지 조건 중 하나를 만족할 수 있습니다. 이를 위해 여러번 반복하여 신뢰도를 높입니다. Miller-Rabin 은 n 이 홀수인 합성수 인데 여러 수 중 강한 거짓증거(strong liar) 인 a가 선택되면 합성수임에도 불구하고 소수로 오인할 수 있으며, 이러한 오류율은 $ \le \frac{1}{4}$ 이며, 이는 이미 “Michael O. Rabin, “Probabilistic algorithm for testing primality,” Journal of Number Theory, 1980.” 에 의해 증명이 되었습니다. 즉 오류가 존재할 수 있기 때문에 오류율을 극한으로 낮추기 위해 여러 번 반복을 진행합니다. 그래서 k 번 진행을 하게 된다면 오류율은 $\le \frac{1}{4^k}$ 가 됩니다.
3.2 예시
3.2.1 예시1: 합성수에서 조건 실패
입력
- $ n = 561$ (합성수)
- $n-1 = 560 = 2^4 \cdot 35$
- $a = 2$
계산
- $x_0 = 2^{35} \mod 561 = 263$
- $x_1 = 263^2 \mod 561 = 166$
- $x_2 = 166^2 \mod 561 = 67$
- $x_3 = 67^2 \mod 561 = 1$
어느 순간에도 $x_i \equiv -1 \mod 561$ 즉, 560이 나타자니 않으므로 합성수로 판별됨
3.2.2 예시 2: 두 번째 조건 만족
입력
- $n=97$
- $n-1 = 96 = 2^5 \cdot 3$
- $a = 5$
계산
- x_0 = 5^3 \mod 97 = 28$
- $x_1 = 28^2 \mod 97 = 8$
- $x_2 = 8^2 \mod 97 = 64$
- $x_3 = 64^2 \mod 97 = 22$
- $x_4 = 22^2 \mod 97 = \mathbf{96} \equiv -1 \mod 97$
$x_4 = 22^2 \mod 97 = \mathbf{96} \equiv -1 \mod 97$ 로 조건에 부합
3.3 알고리즘으로써 시간복잡도
시간복잡도는 한 번 테스트할 때마다 $O(\log{n})$ 의 시간복잡도를 가지며, k 번 반복을 한다면 $O(k\log{n})$ 의 시간복잡도를 가집니다.
4. python 코드
import random
def is_prime(n, k=5) :
# n 이 1보다 작거나 같으면 소수가 아니므로 False return
if n <= 1:
return False
if n <= 3: # n 이 3보다 작거나 같으면 2와 3 밖에 없으니 소수이므로 True return
return True
if n % 2 == 0: # 3보다 큰 n 이 2로 나누어 떨어지면 소수가 아니므로 False return
return False
r, d = 0, n-1
# 조건 검사를 위한 r와 d 를 구함
while d % 2 == 0:
d //= 2
r += 1
# 높은 신뢰도를 위해 k 번 실행 k의 값이 커질 수록 오류율이 1/4^k 만큼 줄어듦
for _ in range(k):
a = random.randrange(2, n-1) # 2~n-1 값 사이에 있는 랜덤 숫자를 선택
x= pow(a, d, n) # a^d 를 구하고 그 값을 mod n 을 진행
# x 가 1 이거나 n-1 이면 소수라고 보고 continue
if x == 1 or x == n-1:
continue
# 위 조건에서 소수 판별이 되지 않으면 두 번째 조건 판별을 진행
for _ in range(r-1):
x = pow(x, 2, n)
if x == n-1:
break
else: # 위 두 조건 모두 만족하지 못하면 False return
return False
# k 번 반복하는 동안 return 하지 않으면 소수라고 판단하고 True return
return True
5. 마치며
소수판별법 중 하나인 Miller-Rabin 소수판별법에 대해서 알아보았습니다. 부족한 제가 알기론 소수는 컴퓨터 공학에서 암호학이 아니면 그렇게 많이 쓰이진 않는 것으로 알고 있습니다만 그래도 알고리즘 문제에서 간혹 소수와 관련된 문제들이 출제되다 보니 이번 기회에 한 번 정리를 해보았습니다.
긴글 읽어주셔서 감사드리며 잘못된 내용이나 오타가 있을 경우 댓글 달아주시기 바랍니다.
Comments