NUMBER THEORY PRIMALITY TEST
가능한 모든 소수에 대해서 나누어 보는 방식이다. 단 p에 대해서는 [ \sqrt{p} ]만큼만 확인해보면 test가 가능하다.
일종의 확률적인 방법이다. p가 소수인지 아닌지 알기위해 GCD(a, p) = 1을 만족하는 a를 뽑는다. a에 대해서 a^n-1^ mod p의 계산 결과가 1인지 아닌지를 확인하는 방식이며, 이를 만족하는 a를 하나라도 얻을 수 있다면 p는 소수가 아니다.
기본적으로는 이 방식도 일종의 fermat test이다. 여기에 NSR test를 더하여 Miller-Rabin test가 된다. p가 만약에 홀수인 소수라면 
을 만족하는 해는 x = 1, p - 1(
)밖에 없다. 따라서 이 두수에 대해서 x = 1, p - 1이 아닌 해를 구할 수 있다면 p는 소수가 아니다.
기본적으로 Miller-Rabin test는 fermat test를 기반으로 하기 때문에 확률적인 방식이다. 알고리즘이 확률적이라는 것은 아래와 같은 의미이다.
- 항상 답은 얻지만, 입력에 따라 수행시간이 확률적으로 들쭉날쭉한 방식
- 알고리즘의 수행시간은 항상 일정하지만, 입력에 따라 결과가 틀릴 수 있는 방식
Miller-Rabin test는 2번의 방식이다. 그렇다면 이런 방식을 믿고 사용할 수 있는가? 그렇다. 2번의 방식을 어느정도 반복하면 오답의 확률이 매우 적어지기 때문에 활용이 가능하다.
// Miller-Rabin Algorithm
Miller_Rabin(n, s) // Test if n is prime with error probability << 2 ^-s
For j = 1 to s
a = random positive integet < n
if Test(a, n) = Composite, then return Composite. // definitely
End For
Return Prime // almost sure
Subroutine Test(a, n)
Let t and u be such that t >= 1, u is odd, and n - 1 = (2^t) * u
x_0 = a^u mod n
For i = 1 to t
x_i = (x_i-1)^2 mod n.
if x_i = 1 and x_i-1 != 1 and x_i-1 != n - 1, then return Composite. // NSR test
End For
if x_t != 1, then return Composite. // Fermat test
Return Prime
// 출처: Cormen, Leiserson, Rivest, and Stein, Introduction ro ALgorithms, 3rd ed., MIT Press위 방식에서 subroutine Test의 정답 확률은 50%정도로 알려져 있다. 따라서 s번을 반복한다면 Test의 오답 확률은 
정도로 작아진다. 보통 s정도는 100회정도로 하도록 권장되며 이는 약 
이며 0에 근접한다.
개발환경: macOS catalina 10.15.6, pyCharm 사용언어: python3
import random
"""
int_to_bin
convert an inr to a binary representation
(the most significant bit becomes leftmost)
"""
def int_to_bin(num):
return list(bin(num))[2:]
"""
exponential modular
a ^ b mod n을 구하는 연산이다.
이때 a^b는 상당히 큰 수이므로 기존의 a ** b 와는 다른 방법이 필요하다.
a mod n * b mod n = (a * b) mod n을 이용한다.
"""
def exponential_modular(a, b, n):
count, result = 0, 1
binary_format_b = int_to_bin(b)
for i in range(len(binary_format_b)):
count = 2 * count
result = (result * result) % n
if binary_format_b[i] == '1':
count = count + 1
result = (result * a) % n
return result
"""
Miller_rabin algorithm
주어진 n이 소수인지 아닌지 판별하는 함수
이때 Miller_rabin 의 결과는 deterministic 하지 않다.
따라서 함수의 실행결과의 정확도를 사용자가 원하는 만큼으로 지정할수 있는데
s에 따라서 2^-s가 최대의 오차 확률이다.
"""
Prime = True
Composite = False
def miller_rabin(n, s):
if n == 2:
return Prime # 100%
if n % 2 == 0:
return Composite # 100%
for _ in range(s):
a = random.randint(1, n - 1)
if test(a, n) == Composite: # 100%
return Composite # 100%
return Prime # almost sure
def test(a, n):
u, t = n - 1, 0
while u % 2 == 0:
u = u // 2
t = t + 1
x_prev = exponential_modular(a, u, n)
x_cur = x_prev
for _ in range(t):
x_cur = exponential_modular(x_prev, 2, n)
if x_cur == 1 & x_prev != 1 & x_prev != n - 1: # NST test
return Composite
x_prev = x_cur
if x_cur != 1: # Fermat test
return Composite
return Prime
if __name__ == "__main__":
primes = [2, 3, 4, 5, 6, 7, 8, 9, 10, 483749031827, 1837801471603]
start = time.time() # 시작 시간 저장
for p in primes:
result = miller_rabin(p, 100)
print(p, end='')
if result == Prime:
print(" is Prime")
elif result == Composite:
print(" is Composite")
else:
print(" is Undefined")
print("elapsed time :", time.time() - start) # 현재시각 - 시작시간 = 실행 시간trial division방식은 상당히 비효율적이고 miller-rabin test는 정답을 보장할수는 없다. trial division보다 효율적이고 정답이 보장되는 방법을 찾으려는 시도는 항상 있었다. AKS algorithm이라는 방식이 제안되었지만 miller-rabin 방식보다 상당히 비효율적이다. 현재 2020년까지는 deterministic 하면서 miller-rabin보다 빠른방식은 알려지지 않았다.
실무에서는 trial division과 Miller-Rabin을 조합하여 사용한다. 100자리 이상의 거대한 숫자가 prime인지 확인하는 문제에서 2, 3, 5, 7, 11등의 아주 작은 prime까지만 trial division으로 확인해보고 이후로 MR방식으로 확인한다. trial 방식을 사용하면서 상당히 많은 후보군을 줄일 수 있으므로 MR의 확률이 매우 좋아진다.