맨위로가기

밀러-라빈 소수판별법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

밀러-라빈 소수판별법은 소수의 특별한 성질을 이용하여 주어진 수가 소수인지 여부를 확률적으로 판별하는 알고리즘이다. 페르마 소정리를 기반으로 하며, 솔로바이-스트라센 소수판별법보다 강력한 성능을 보인다. 이 알고리즘은 암호학, 정보 보안 등 다양한 분야에서 큰 소수를 효율적으로 생성하고 판별하는 데 사용된다. 밀러-라빈 소수판별법은 반복 횟수에 따라 정확도를 높일 수 있으며, 합성수를 소수로 잘못 판단할 확률을 4^{-k}로 줄일 수 있다. 알고리즘의 시간 복잡도는 O(k log³ n)이며, FFT를 사용하면 Õ(k log² n)으로 개선할 수 있다. 추가적으로, 최대공약수 계산을 통해 인수 분해를 수행하거나, 다중 밑수를 결합하여 정확도를 높이는 변형된 알고리즘도 존재한다.

더 읽어볼만한 페이지

  • 소수 판별법 - 에라토스테네스의 체
    에라토스테네스의 체는 주어진 범위에서 소수를 효율적으로 찾는 알고리즘으로, 특정 구간 내의 모든 수를 나열한 후 가장 작은 소수의 배수들을 제거하는 과정을 반복하여 소수만을 남기는 방식으로 작동하며, 다양한 변형과 최적화 기법이 존재하고, O(n \log \log n)의 시간 복잡도를 가진다.
  • 소수 판별법 - 베일리–PSW 소수판별법
    베일리-PSW 소수판별법은 초기 나눗셈, 밀러-라빈 소수판별법, 특정 조건에 따른 D, P, Q 값 선택, 강한 뤼카 소수판별법의 단계를 거쳐 주어진 정수의 소수 여부를 판별하는 알고리즘으로, 페르마 소수성 검정과 뤼카 소수성 검정을 결합하여 여러 소프트웨어에서 활용된다.
  • 유한체 - 이산 로그
    이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
  • 유한체 - 순환 중복 검사
    순환 중복 검사(CRC)는 데이터 전송 또는 저장 시 오류 검출을 위해 데이터를 다항식으로 간주하고 생성 다항식으로 나눈 나머지를 검사 값으로 사용하여 오류를 감지하는 기술이다.
밀러-라빈 소수판별법
개요
종류확률적 소수판별법
고안자게리 밀러 (1976년)
마이클 O. 라빈 (1980년)
최악 시간 복잡도O(k log³ n), k는 테스트 횟수
관련 주제페르마 소정리
제곱근을 통한 소수판별법
상세 정보
작동 원리페르마 소정리와 제곱근을 통한 소수판별법의 결합
정확도합성수를 소수로 잘못 판별할 확률은 4^(-k)보다 작음 (k는 테스트 횟수)
결정론적 변형일반화된 리만 가설이 참일 경우, 결정론적 알고리즘으로 사용 가능
활용
사용 사례암호학, 공개 키 암호 시스템 등에서 큰 소수를 생성하는 데 사용
장점비교적 간단하고 빠르며, 큰 수에 대해서도 효율적으로 작동
단점확률적 알고리즘이므로, 드물게 오류를 발생시킬 수 있음
기타
다른 이름라빈-밀러 소수판별법

2. 이론적 배경

페르마 소수판별법이나 솔로바이-스트라센 소수판별법과 마찬가지로, 밀러-라빈 소수판별법은 소수가 가지는 특별한 성질을 이용한다. 홀수인 소수 n에 대해, n - 1은 2^s d (s는 정수, d는 홀수)로 표현할 수 있다. 이는 n - 1을 계속해서 2로 나눈 형태이다.

어떤 a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^*에 대해, 다음 두 식 중 하나가 성립한다.


  • a^{d} \equiv 1 \pmod{n}\,
  • 0 \le r \le s-1 인 어떤 r에 대해, a^{2^r \cdot d} \equiv -1\pmod{n}


이는 페르마 소정리 a^{n-1} \equiv 1\pmod{n}\,에서 유도할 수 있다. 즉, a^{n-1}의 제곱근을 계속 구해나가면 1 또는 -1을 얻게 된다.

밀러-라빈 소수판별법에서 n이 소수인지 검사할 때, 위 두 식이 모두 성립하지 않으면 a는 n이 합성수라는 '''강한 증거'''(strong witness)가 된다. 반대로 위 식이 성립하면 a는 '''강한 거짓증거'''(strong liar)라 하고, n은 '''아마 소수일 것 같다'''(probable prime)고 한다.

2. 1. 소수와 합성수

페르마 소정리에 따르면, 소수 n과 서로소인 a에 대해 a^{n-1} \equiv 1 \pmod n이 성립한다. n이 홀수인 소수라면, n-1은 2^s \cdot d (s는 정수, d는 홀수) 형태로 표현 가능하다. 이때, 다음 두 식 중 하나가 성립한다.

  • a^{d} \equiv 1 \pmod{n}\,
  • 0 \le r \le s-1 인 어떤 r에 대해, a^{2^r \cdot d} \equiv -1\pmod{n}


이는 a^{n-1}의 제곱근을 계속 구해나가면 1 또는 -1을 얻게 된다는 것을 의미한다. 만약 -1이 나오면 두 번째 식이 성립하는 것이고, 더 이상 검사할 필요가 없다.

제곱근을 계속 구해도 두 번째 식이 성립하지 않으면, 1 또는 -1의 값을 가질 첫 번째 식을 검사해야 한다. 두 번째 식이 성립하지 않는다면, r = 0일 때 a^{2^0\cdot d} = a^d \not\equiv -1\pmod{n}이 되므로 첫 번째 식은 반드시 성립해야 한다.

n이 합성수라면, 위의 두 식이 모두 성립하지 않을 수 있다. 이 경우 a는 n이 합성수라는 "강한 증거"가 된다. 반대로, 두 식 중 하나라도 성립하면 a는 "강한 거짓증거"가 되고, n은 "아마 소수일 것 같다"고 판단한다.

2. 2. 페르마 소정리

페르마 소정리에 따르면 소수 p와 p의 배수가 아닌 정수 a에 대해, 다음 식이 성립한다.

:a^{p-1} \equiv 1\pmod{p}\,

이 정리는 밀러-라빈 소수판별법에서 다음과 같은 형태로 사용된다. 홀수인 소수 n에 대해, n - 1은 2sd (s는 정수, d는 홀수)로 표현 가능하다. 이때, a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^*에 대해 다음 두 식 중 하나가 성립한다.

  • a^{d} \equiv 1 \pmod{n}\,
  • a^{2^r \cdot d} \equiv -1\pmod{n} \mbox{ for some 0 } \le r \le s-1


즉, a^{n-1}의 제곱근을 계속 구해나가면 1 또는 -1을 얻게 된다. -1이 나오면 두 번째 식이 성립하는 것이고, 그렇지 않으면 첫 번째 식이 성립한다.

2. 3. 제곱근 검사

페르마 소정리에 따르면, ''n''이 홀수인 소수이고 ''n'' - 1이 2^s \cdot d (s는 음이 아닌 정수, d는 홀수)로 표현될 때, 모든 a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^*에 대해 다음 두 식 중 하나가 성립한다.[1]

  • a^{d} \equiv 1\pmod{n}
  • a^{2^r\cdot d} \equiv -1\pmod{n} (여기서 0 \le r \le s-1)


이는 a^{n-1} \equiv 1\pmod{n}의 제곱근을 계속 구해나가면 1 또는 -1을 얻게 된다는 사실에서 유도된다.[1] 즉, 1 (mod ''n'')의 제곱근은 1 또는 -1뿐이다.[1]

만약 -1이 나오면 두 번째 식이 성립하는 것이고, 더 이상 검사하지 않아도 된다. 제곱근을 계속 구해나가도 두 번째 식이 성립하지 않으면, 첫 번째 식을 검사해야 한다. 두 번째 식이 성립하지 않는다면, r = 0일 때 a^{2^0\cdot d} = a^d \not\equiv -1\pmod{n}이므로 첫 번째 식은 반드시 성립한다.[1]

2. 4. 강한 거짓증거와 강한 의사소수

페르마 소정리에 따르면, 홀수인 소수 n과 서로소인 a에 대해 a^{n-1} \equiv 1 \pmod n이 성립한다. n-1을 2^s d (s는 정수, d는 홀수) 형태로 나타낼 수 있다. 이때, 다음 두 식 중 하나가 성립한다.

  • a^{d} \equiv 1 \pmod{n}\,
  • a^{2^r \cdot d} \equiv -1\pmod{n} \mbox{ for some 0 } \le r \le s-1


즉, a^{n-1}의 제곱근을 계속 구해나가면, 1 또는 -1을 얻게 된다. 만약 a^d \not\equiv 1 \pmod n이고, 모든 0 \le r \le s-1에 대해 a^{2^r \cdot d} \not\equiv -1 \pmod n이면, a는 n이 합성수라는 '''강한 증거'''(strong witness)가 된다.[4]

만약 위 식이 성립하지 않으면, 즉, a^d \equiv 1 \pmod n이거나 어떤 0 \le r \le s-1에 대해 a^{2^r \cdot d} \equiv -1 \pmod n이면, a는 '''강한 거짓증거'''(strong liar)라 하고, n은 '''강한 의사소수'''(strong pseudoprime)라고 한다. 강한 거짓증거는 n이 합성수임에도 불구하고 마치 소수인 것처럼 동작하기 때문에 붙여진 이름이다.

3. 알고리즘 및 작동 원리

밀러-라빈 소수판별법은 주어진 수가 소수인지 판별하는 확률적 알고리즘이다. 이 알고리즘은 페르마 소정리와 1의 제곱근에 대한 성질을 기반으로 작동한다.

주어진 홀수 정수 ''n''에 대해, ''n'' - 1을 2^s d (''s''는 양의 정수, ''d''는 홀수) 형태로 나타낸다. 이후, ''n''과 상호 소수인 밑 ''a''를 선택하여 다음 두 가지 합동식 중 하나가 성립하는지 확인한다.


  • a^d \equiv 1 \pmod n
  • a^{2^r d} \equiv -1 \pmod n (단, 0 \le r < s)


위 두 식 중 하나라도 만족하면 ''n''은 밑 ''a''에 대한 강한 가능 소수라고 한다. 만약 두 식 모두 만족하지 않으면 ''n''은 합성수이고, ''a''는 ''n''의 합성성을 나타내는 증인이 된다.

하지만, ''n''이 합성수임에도 불구하고 위 합동식을 만족하는 경우가 존재할 수 있는데, 이러한 경우 ''n''을 '''강한 유사 소수'''라고 하며, ''a''를 '''강한 거짓말쟁이'''라고 한다.

밀러-라빈 소수판별법은 이러한 과정을 ''k''번 반복하여 주어진 수 ''n''이 소수인지 판별한다. 만약 ''k''번의 테스트를 통과한다면, ''n''은 높은 확률로 소수라고 판정한다.
''n''이 소수일 경우, 법 ''n''에 대한 1의 제곱근은 1과 -1뿐이다.1과 -1을 ''n''으로 나눈 나머지를 제곱하면 항상 1이 된다. ''x''가 ''n''을 법으로 하는 1의 제곱근이라고 가정하면, (x - 1)(x + 1) = x^2 - 1 \equiv 0 \pmod{n} 이 성립한다. 유클리드의 보조정리에 의해 ''n''이 소수이므로, ''n''은 (x - 1) 또는 (x + 1) 중 하나를 나누어야 한다. 따라서 ''x''는 ''n''을 법으로 1 또는 -1과 합동이다.
''n''이 홀수 소수일 경우, ''n''은 밑 ''a''에 대한 강한 확률적 소수이다.''n''이 홀수 소수이고 n - 1 = 2^s d로 표현될 때, 페르마 소정리에 의해 a^{2^s d} \equiv 1 \pmod{n}이 성립한다. a^{2^s d}, a^{2^{s-1} d}, \dots, a^{2d}, a^d 수열의 각 항은 이전 항의 제곱근이다. 첫 번째 항은 1과 합동이므로, 두 번째 항은 ''n''을 법으로 하는 1의 제곱근이므로 1 또는 -1과 합동이다. 만약 -1과 합동이면 증명이 완료된다. 그렇지 않으면 1과 합동이므로 귀납법을 통해 반복한다. 결국, 항 중 하나가 -1과 합동이거나, 모든 항이 1과 합동이며, 특히 마지막 항인 a^d가 그렇다.

3. 1. 알고리즘

n − 1을 2s \* d 형태로 변환한다.

다음을 k번 반복한다.

  • [1, n - 1]에서 임의의 a를 선택한다.
  • [0, s - 1]의 모든 r에 대해 ad mod n ≠ 1이고 a2rd mod n ≠ n − 1 이면 "합성수"를 반환한다.


위 조건을 만족하지 않으면 "아마 소수일 것"을 반환한다.

제곱을 반복하는 방법으로 모듈로 지수승을 계산하면 이 알고리즘의 시간복잡도는 {\color{Blue} O}(k \, \log^3 n)이다.(k는 a의 개수이다.) 이때 FFT를 이용하여 곱셈의 횟수를 줄이면 시간복잡도를 {\color{Blue} \tilde{O}}(k \, \log^2 n)로 줄일 수 있다.[5]

'''입력 #1''': ''n'' > 2, 소수성 검사를 위한 홀수 정수

'''입력 #2''': ''k'', 수행할 테스트 라운드 수

'''출력''': ''n''이 합성수로 판명되면 “''합성수''”, 그렇지 않으면 “''소수일 확률 큼''”

'''let''' ''s'' > 0 과 ''d'' 홀수 > 0 such that ''n'' − 1 = 2''s''''d'' # ''n'' − 1에서 2의 거듭제곱을 인수분해하여

'''repeat''' ''k'' '''번''':

  • ''a'' ← random(2, ''n'' − 2) # ''n''은 항상 밑수 1과 ''n'' − 1에 대한 확률적 소수
  • ''x'' ← ''a''''d'' mod ''n''
  • '''repeat''' ''s'' '''번''':
  • ''y'' ← ''x''2 mod ''n''
  • '''if''' ''y'' = 1 and ''x'' ≠ 1 and ''x'' ≠ ''n'' − 1 '''then''' # ''n''을 모듈로로 하는 1의 자명하지 않은 제곱근
  • '''return''' “''합성수''”
  • ''x'' ← ''y''
  • '''if''' ''y'' ≠ 1 '''then'''
  • '''return''' “''합성수''”

'''return''' “''소수일 확률 큼''”

3. 2. 작동 원리

밀러-라빈 소수판별법은 페르마 소정리와 제곱근 검사를 결합하여 작동한다. 주어진 수 ''n''이 소수일 때 만족해야 하는 조건을 검사하며, 만약 이 조건을 만족하지 않는 ''a''를 찾으면 ''n''은 확실히 합성수이다.

먼저, 홀수 정수 ''n'' > 2에 대해, ''n'' - 1을 2''s''''d''로 표현한다. 여기서 ''s''는 양의 정수이고 ''d''는 홀수 양의 정수이다. ''a''를 ''n''과 상호 소수인 '밑'이라고 하는 정수로 가정한다.

그러면, ''n''은 다음 합동 관계식 중 하나가 성립하면 '''밑 ''a''에 대한 강한 가능 소수'''라고 한다.

  • a^d \equiv 1 \pmod n, 또는
  • a^{2^r d} \equiv -1 \pmod n (단, ).


이는 a^d \bmod n = 1을 확인하고, 연속적인 ''r'' 값에 대해 a^{2^r d} = n-1 을 확인하는 것으로 단순화된다. 각 r 값에 대해, 표현식의 값은 모듈로 ''n''에서 제곱하여 이전 ''r'' 값에 대해 얻은 값을 사용하여 계산할 수 있다.

이 테스트의 기본 아이디어는 ''n''이 홀수 소수일 때 다음 두 가지 사실 때문에 테스트를 통과한다는 것이다.

  • 페르마의 소정리에 의해, a^{n-1} \equiv 1 \pmod{n}이다.
  • 1 모듈로 ''n''의 유일한 제곱근은 1과 −1이다.[2]


따라서, 대우에 의해, ''n''이 밑 ''a''에 대한 강한 가능 소수가 아니면, ''n''은 확실히 합성수이며, ''a''는 ''n''의 합성성을 위한 '''증인'''이라고 불린다.

만약 ''n''이 합성수라면, 그럼에도 불구하고 밑 ''a''에 대한 강한 가능 소수일 수 있으며, 이 경우 '''강한 유사 소수'''라고 불리며 ''a''는 '''강한 거짓말쟁이'''이다.

a^d \equiv 1 \pmod n은 a \equiv 1 \pmod n에 대해 자명하게 성립한다. 그리고 a^{2^0 d} \equiv -1 \pmod n은 a \equiv -1 \pmod n에 대해 자명하게 성립한다. 따라서 임의의 ''a''는 일반적으로 1 < a < n - 1 구간에서 선택된다.
''n''이 소수일 경우, ''n''을 법으로 하는 1의 제곱근은 1과 −1뿐임을 증명1과 −1을 ''n''을 법으로 제곱하면 항상 1이 된다. 이제 ''n''을 법으로 하는 1의 다른 제곱근이 없음을 보이면 된다. ''x''가 ''n''을 법으로 하는 1의 제곱근이라고 가정하면 다음과 같다.

: (x - 1)(x + 1) = x^2 - 1 \equiv 0 \pmod{n}.

''n''은 곱 (x - 1)(x + 1)을 나누며, 유클리드의 보조정리에 따라, ''n''이 소수이므로, 인수 x - 1 또는 x + 1 중 하나를 나누며, 이는 ''x''가 ''n''을 법으로 1 또는 −1과 합동임을 의미한다.
''n''이 홀수 소수일 경우, ''n''이 밑 ''a''에 대한 강한 확률적 소수임을 증명''n''이 홀수 소수이고 n - 1 = 2^s d로 표현될 때, 여기서 ''s''는 양의 정수이고 ''d''는 홀수 양의 정수이며, 페르마의 소정리에 의해:

: a^{2^s d} \equiv 1 \pmod{n}.

수열 a^{2^s d}, a^{2^{s-1} d}, \dots, a^{2d}, a^d의 각 항은 이전 항의 제곱근이다. 첫 번째 항은 1과 합동이므로, 두 번째 항은 ''n''을 법으로 하는 1의 제곱근으로 1 또는 −1과 합동이다. −1과 합동인 경우 증명이 완료된다. 그렇지 않은 경우, 1과 합동이므로 수학적 귀납법을 통해 반복할 수 있다. 결국, 항 중 하나가 −1과 합동이거나, 모두 1과 합동이며, 특히 마지막 항인 ''a''''d''가 그렇다.

예를 들어 n = 221이 소수인지 판별하려 한다고 가정해 보자. n - 1을 2^2 \times 55로 나타낼 수 있으며, 이로부터 s = 2와 d = 55를 얻는다. 2 \leq a \leq n-2를 만족하는 숫자 a를 무작위로 선택한다.

a = 174라고 하면:



\begin{align}

a^{2^0d} \bmod n \rightarrow & 174^{2^0 \cdot 55} \bmod 221 \equiv 174^{55} \equiv 47. \\

& 47 \neq 1 \text{이고 } 47 \neq n - 1 \text{이므로, 계속 진행한다.} \\

& 174^{2^1 \cdot 55} \bmod 221 \equiv 174^{110} \equiv 220 = n - 1

\end{align}



220 \equiv -1 \pmod n이므로, 221이 소수이거나, 174가 221에 대한 강한 거짓말쟁이일 수 있다.

다른 무작위 a = 137을 선택하면:



\begin{align}

a^{2^0d} \bmod n \rightarrow & 137^{2^0 \cdot 55} \bmod 221 \equiv 137^{55} \equiv 188. \\

& 188 \neq 1 \text{이고 } 188 \neq n - 1 \text{이므로, 계속 진행한다.} \\

& 137^{2^1 \cdot 55} \bmod 221 \equiv 137^{110} \equiv 205 \neq n - 1

\end{align}



따라서 137은 221의 합성수를 증명하는 증인이 되며, 174는 실제로 강한 거짓말쟁이였다.

여러 개의 ''a''에 대해 검사를 반복함으로써, ''n''이 소수일 확률을 높일 수 있다.

3. 3. 시간 복잡도

반복 제곱을 이용한 모듈로 지수승 계산을 사용하면, 이 알고리즘의 시간 복잡도는 O(k log³ n)이다. 여기서 k는 a의 개수, 즉 반복 횟수를 의미한다. FFT를 이용하면 곱셈 횟수를 줄여 시간 복잡도를 Õ(k log² n)로 줄일 수 있다.[1]

4. 결정론적 변형: 밀러 테스트

밀러-라빈 소수 판별법의 결정론적 변형은 게리 L. 밀러가 제안한 밀러 테스트를 마이클 라빈이 확률적 알고리즘으로 수정한 것이다. 원래 밀러 테스트는 확장 리만 가설에 기반한 결정적 알고리즘이었으나, 이 가설이 증명되지 않았기 때문에 실제로는 잘 사용되지 않는다.

밀러 테스트는 확장 리만 가설을 필요로 하고, 판정의 신뢰도를 위해 조사해야 할 ''a''값의 한계를 결정하는 문제가 있다. 판정 대상 수 ''n''이 합성수일 때, ''n''과 서로소인 "강력한 거짓말쟁이" ''a''는 특정 군의 진부분군에 포함된다. 확장 리만 가설이 참이라면, 이 집합은 O((ln ''n'')2)보다 작은 원소로부터 생성된다는 것이 알려져 있으며, 에릭 바흐는 이 상수를 2까지 감소시켰다.

이를 바탕으로, ''n'' - 1을 2의 거듭제곱으로 나누어 2^s \cdot d 형식으로 만들고, [2, min(''n''-1, ⌊2(ln ''n'')2⌋)] 범위의 모든 ''a''에 대해 ''a''''d'' mod ''n'' ≠ 1이고 [0, ''s'' − 1] 범위의 모든 ''r''에 대해 a^{d \cdot 2^r} mod ''n'' ≠ −1이면 ''n''을 합성수로 판정하는 알고리즘이 유도된다. 이 알고리즘의 실행 시간은 Õ((log ''n'')4)이다.

하지만, ''n''이 충분히 작을 경우에는 모든 ''a'' < 2(ln ''n'')2을 조사할 필요가 없으며, 더 작은 수의 집합으로도 충분하다. 예슈케는 다음 범위를 검증했다.

n의 범위검사할 a 값
n < 4,759,123,1412, 7, 61
n < 341,550,071,728,3212, 3, 5, 7, 11, 13, 17



이러한 결과는 특정 범위의 수에 대해 매우 빠르고 결정적인 소수 판별을 가능하게 한다. 그러나 모든 합성수에 대해 이러한 유한 집합으로 충분하지 않다는 한계가 있다.

4. 1. 밀러 테스트

밀러 테스트는 확장 리만 가설(ERH) 하에서 작동하는 결정론적 알고리즘 소수 판별법이다. 이 가설이 참이라면, 밀러 테스트는 \tilde{O}((\log n)^4)의 시간 복잡도로 소수 여부를 판별할 수 있다.[1][9]

'''입력''': ''n'' > 2, 소수성을 테스트할 홀수 정수

'''출력''': ''n''이 합성수이면 “''합성수''”, 그렇지 않으면 “''소수''”

# ''n'' − 1에서 2의 거듭제곱을 인수분해하여 ''s'' > 0 이고 ''d'' 홀수 > 0 일 때, ''n'' − 1 = 2''s''''d'' 를 구한다.

# 2부터 min(''n'' − 2, ⌊2(ln ''n'')2⌋) 범위에 있는 모든 ''a''에 대해 다음을 반복한다:

## ''x'' ← ''a''''d'' mod ''n''

## ''s''번 반복한다:

### ''y'' ← ''x''2 mod ''n''

### 만약 ''y'' = 1 이고 ''x'' ≠ 1 이고 ''x'' ≠ ''n'' − 1 이면: (1 modulo ''n''의 비자명 제곱근)

#### “''합성수''”를 반환한다.

### ''x'' ← ''y''

## 만약 ''y'' ≠ 1 이면:

### “''합성수''”를 반환한다.

# “''소수''”를 반환한다.

테스트의 정확성을 보장하기 위해 일반화된 리만 가설 전체가 필요한 것은 아니다. 지수가 짝수인 부분군을 다루므로, 2차 디리클레 문자에 대한 GRH의 유효성을 가정하는 것으로 충분하다.[6]

밀러 테스트는 실제로 자주 사용되지는 않는다. 대부분의 경우 확률적 밀러-라빈 소수판별법이나 베일리-PSW 소수 판별법이 더 효율적이다. 또한, APR-CL 및 ECPP과 같이 증명되지 않은 가설에 의존하지 않는 다른 소수 판별법보다 느리다. 결정론적 다항 시간 알고리즘이 필요한 이론적 목적을 위해, AKS 소수 판별법이 밀러 테스트를 대체하였다.

''n''이 합성수라면, ''n''과 서로소인 "강력한 거짓말쟁이" ''a''는 군 \left(\mathbb{Z}/n\mathbb{Z}\right)^*의 진부분군에 포함된다. 확장 리만 가설이 참이라면, 이 집합은 O((ln ''n'')2)보다 작은 원소로부터 생성된다는 것이 알려져 있다. 빅 오 표기의 상수는 에릭 바흐에 의해 2까지 감소되었다.

''n''이 충분히 작으면, 모든 ''a'' < 2(ln ''n'')2을 조사할 필요는 없다. 더 작은 증거 가능성이 있는 수의 집합으로도 충분하다. 예를 들어, 예슈케는 다음을 검증했다.

n의 범위검사할 a 값
n < 4,759,123,1412, 7, 61
n < 341,550,071,728,3212, 3, 5, 7, 11, 13, 17



물론, ''a'' < ''n''인 경우만 조사한다. 그러나 모든 합성수에 대해 이러한 유한 집합으로는 충분하지 않다.

4. 2. 작은 수에 대한 최적화

판별할 수 \(n\)의 크기가 작을 경우, 작은 수의 \(a\)에 대해서만 검사해도 결정론적으로 소수를 판별할 수 있다. Pomerance, Selfridge, Wagstaff[22]와 Jaeschke[23]에 따르면, 특정 범위 내에서 \(a\)값에 대한 검사만으로 충분하다.

\(n\)의 범위검사해야 할 \(a\) 값
\(n < 1,373,653\)\(a = 2, 3\)
\(n < 9,080,191\)\(a = 31, 73\)
\(n < 4,759,123,141\)\(a = 2, 7, 61\)
\(n < 2,152,302,898,747\)\(a = 2, 3, 5, 7, 11\)
\(n < 3,474,749,660,383\)\(a = 2, 3, 5, 7, 11, 13\)
\(n < 341,550,071,728,321\)\(a = 2, 3, 5, 7, 11, 13, 17\)



어떤 합성수도 동시에 모든 밑에 대한 강한 유사소수일 수 없다. (카마이클 수와는 대조적). 하지만 증인을 찾는 간단한 방법은 알려져 있지 않다.

테스트할 숫자 \(n\)이 작을 경우, \(a < 2(\ln n)^2\)를 모두 시도하는 것은 불필요하며, 훨씬 작은 집합의 잠재적 증인으로도 충분하다. 다음은 이미 검증된 내용들이다.

\(n\)의 범위검사해야 할 \(a\) 값
\(n\) < 2,047\(a\) = 2
\(n\) < 1,373,653\(a\) = 2, 3
\(n\) < 9,080,191\(a\) = 31, 73
\(n\) < 25,326,001\(a\) = 2, 3, 5
\(n\) < 3,215,031,751\(a\) = 2, 3, 5, 7
\(n\) < 4,759,123,141\(a\) = 2, 7, 61
\(n\) < 1,122,004,669,633\(a\) = 2, 13, 23, 1662803
\(n\) < 2,152,302,898,747\(a\) = 2, 3, 5, 7, 11
\(n\) < 3,474,749,660,383\(a\) = 2, 3, 5, 7, 11, 13
\(n\) < 341,550,071,728,321\(a\) = 2, 3, 5, 7, 11, 13, 17
\(n\) < 3,825,123,056,546,413,051\(a\) = 2, 3, 5, 7, 11, 13, 17, 19, 23
\(n\) < 264 = 18,446,744,073,709,551,616\(a\) = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
\(n\) < 318,665,857,834,031,151,167,461\(a\) = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
\(n\) < 3,317,044,064,679,887,385,961,981\(a\) = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41


  • \(a\) = 19를 이용한 테스트를 추가해도 이전 경계가 개선되지 않는다.[12]
  • \(a\) = 29와 31을 이용한 테스트를 추가해도 이전 경계가 개선되지 않는다.[13]
  • Sorenson과 Webster는 위 내용을 확인하고 64비트보다 큰 결과에 대한 정확한 결과를 계산했다.[14]


이러한 결과들을 활용하면, 작은 \(n\)값에 대해 매우 빠르고 결정론적인 소수 판별을 수행할 수 있다.

5. 정확도 및 한계

밀러-라빈 소수판별법은 확률적 알고리즘이기 때문에 합성수를 소수로 잘못 판별할 가능성이 있다. 이러한 수를 강한 의사소수라고 하며, 암호학적 공격에 악용될 수 있으므로 주의해야 한다.

소수판별의 정확도는 검사를 여러 번 반복할수록 높아진다. 밀러-라빈 소수판별법에서 합성수가 소수라고 판별될 확률은 최대 4^{-k}이다. (k는 반복 횟수) 이는 솔로베이-스트라센 소수 판별법보다 개선된 결과이다. 평균적으로 합성수가 소수로 판별될 확률은 이보다 훨씬 낮지만, 안전을 위해 4^{-k} 확률을 사용하는 것이 좋다.

5. 1. 정확도

밀러-라빈 소수판별법은 확률적 알고리즘이기 때문에, 합성수를 소수로 잘못 판별할 가능성이 있다. 즉, n이 소수가 아닌데도 알고리즘 실행 결과 n이 소수라고 잘못 판별할 수 있는 경우가 있는데, 이러한 n을 강한 의사소수라고 한다.[4]

소수판별에 필요한 검사를 여러 번 반복할수록 정확도는 높아진다. 밀러-라빈 소수판별법에서 n이 합성수일 때, n이 아마도 소수일 것이라고 판별할 확률은 최대 4^{-k}이다. (k는 반복 횟수)[2][6] 이는 최악의 경우 오류 경계가 2^{-k}인 솔로베이-스트라센 소수 판별법보다 개선된 것이다.[7]

평균적으로 어떤 합성수가 아마도 소수일 것이라고 판별될 확률은 4^{-k}보다 현저히 낮다. 그러나 이처럼 개선된 확률은 소수를 생성할 때에만 유효하며, 소수를 판별할 때에는 4^{-k}라는 확률을 사용하는 것이 안전하다.[7]

5. 2. 강한 의사소수

소수가 아닌데도 밀러-라빈 소수판별법에서 소수로 판별될 수 있는 수를 '''강한 의사소수'''라고 한다. 이러한 수는 암호학적 공격에 악용될 수 있으므로, 실제 사용 시에는 주의가 필요하다.[4]

밀러-라빈 소수판별법은 솔로바이-스트라센 소수판별법보다 더 강력한 소수판별법이다. 합성수 n이 밀러-라빈 소수판별법에서 아마도 소수일 것이라고 판별될 확률은 최대 4^{-k}인 반면, 솔로바이-스트라센 소수판별법에서는 최대 2^{-k}이다. 평균적으로 합성수가 아마도 소수일 것이라고 판별될 확률은 4^{-k}보다 현저히 낮다.

암호학에서는 의사소수를 사용하여 암호시스템을 공격할 수 있으므로, 4^{-k}이라는 확률을 사용하는 것이 안전하다.

5. 3. 솔로바이-스트라센 소수판별법과의 비교

밀러-라빈 소수판별법의 강력한 거짓증거 집합은 솔로바이-스트라센 소수판별법의 강력한 거짓증거 집합의 부분집합이다.[4] 그러므로, 밀러-라빈 소수판별법이 솔로바이-스트라센 소수판별법보다 더 강력한 소수판별법이다.

합성수 n이 있을 때, 밀러-라빈 소수판별법에서 n이 아마도 소수일 것이라고 판별할 확률은 최대 4^{-k}이다. 반면에, 솔로바이-스트라센 소수판별법에서는 합성수 n이 아마도 소수일 것이라고 판별할 확률은 최대 2^{-k}이다.

6. 한국 정보 사회에의 응용 및 중요성

밀러-라빈 소수판별법은 정보화 시대에 필수적인 다양한 기술, 특히 정보 보안 분야에서 중요한 역할을 수행한다.

6. 1. 정보 보안

밀러-라빈 소수판별법은 전자 서명, 키 교환 프로토콜 등 다양한 정보 보안 기술에서 소수 판별이 필요한 경우에 활용된다. 소수 판별은 이러한 기술들의 안전성과 신뢰성을 보장하는 데 핵심적인 역할을 한다. 특히, 큰 수에 대한 소수 판별이 필요한 경우, 밀러-라빈 소수판별법과 같이 확률적 검사를 통해 빠르게 소수 여부를 판별하는 것이 효율적이다.[4]

7. 개선된 알고리즘(Variants) 및 인수 분해

밀러-라빈 소수판별법은 최대공약수(GCD) 계산을 추가하여, 합성수 판별뿐만 아니라 ''n''의 인수도 찾을 수 있도록 개선할 수 있다.[20] ''n''이 특정 밑 ''a''에 대해 가능 소수이지만 강한 가능 소수가 아닌 경우, gcd(''x'' − 1, ''n'') 및 gcd(''x'' + 1, ''n'')을 계산하면 ''n''의 비자명 약수를 얻을 수 있다. (여기서 ''x''는 1 모듈로 ''n''의 비자명 제곱근이다.)

예를 들어, ''n'' = 341, ''a'' = 2일 때, 285 mod 341 = 32이고 322 mod 341 = 1이므로, ''n''은 밑 2에 대한 유사 소수이지만 강한 유사 소수는 아니다. 이때 gcd(32 − 1, 341) = 31을 계산하면 341의 약수 31을 찾을 수 있다.

서로 다른 밑에 대한 강력한 확률적 소수 판별법을 결합하면, 추가적인 소수 판별 기능을 얻을 수 있다.[15] ''n'' ≡ 1 (mod 4)일 때, 두 개 이상의 밑 ''a''에 대해 ''a''d ≢ ±1 (mod ''n'')를 만족하는 경우, -1의 제곱근이 2개 이상 존재할 수 있으므로 ''n''이 합성수임을 판별할 수 있다.

7. 1. 최대공약수 계산을 통한 인수 분해

밀러-라빈 소수판별법에 최대공약수(GCD) 계산을 추가하면, 합성수 여부뿐만 아니라 ''n''의 인수도 찾을 수 있다. 이는 ''n''이 밑 ''a''에 대한 가능 소수이지만 강한 가능 소수가 아닌 경우에 발생한다.[20]

만약 ''x''가 1 모듈로 ''n''의 비자명 제곱근이면, 다음이 성립한다.

  • ''x''2 ≡ 1 (mod ''n'')이므로, ''n''은 ''x''2 − 1 = (''x'' − 1)(''x'' + 1)을 나눈다.
  • ''x'' ≢ ±1 (mod ''n'')이므로, ''n''은 ''x'' − 1 또는 ''x'' + 1을 나누지 않는다.


따라서, ''A'' = gcd(''x'' − 1, ''n'') 및 ''B'' = gcd(''x'' + 1, ''n'')은 ''n''의 비자명 약수이다. 즉, 인수분해가 목표라면, 이러한 gcd 계산을 알고리즘에 추가하여 ''n''의 약수를 찾을 수 있다.

예를 들어, ''n'' = 341, ''a'' = 2일 때, ''n'' − 1 = 85 × 4이다. 285 mod 341 = 32이고 322 mod 341 = 1이므로, ''n''은 밑 2에 대한 유사 소수이지만 강한 유사 소수는 아니다. 이때 gcd(32 − 1, 341) = 31을 계산하면 341의 약수 31을 찾을 수 있다. 실제로 341 = 11 × 31이다.

7. 2. 다중 밑수 결합

Caldwell[15]은 서로 다른 밑에 대한 강력한 확률적 소수 판별법이 때때로 추가적인 소수 판별법을 제공한다고 지적한다. 강력한 검사가 ''n''을 모듈로 한 1의 제곱근이 2개 이상 존재하는지 확인하는 것과 마찬가지로, 이러한 두 개의 검사는 때때로 -1의 제곱근이 2개 이상 존재하는지 확인할 수 있다.

만약 확률적 소수 판별법 과정에서 a|a영어2rd ≡ a|a영어'2r'd ≡ -1 (mod n)를 만족하는 두 개의 밑 a|a영어와 a|a영어'를 발견한다고 가정하면 ''r'', ''r'' ≥ 1이 된다. 이는 검사의 일부로 두 개의 제곱근을 계산했음을 의미하며, a|a영어2r-1d ≡ ± a|a영어'2r'-1d (mod n)인지 확인할 수 있다. 만약 ''n''이 소수라면 이 관계는 항상 성립해야 한다. 그렇지 않다면 -1의 제곱근이 2개 이상 발견된 것이므로 ''n''이 합성수임을 증명한 것이다.

이는 ''n'' ≡ 1 (mod 4)일 경우에만 가능하며, a|a영어d ≢ ±1 (mod ''n'')를 만족하는 두 개 이상의 밑 a|a영어로 확률적 소수 판별법을 통과해야 하지만, 기본적인 밀러-라빈 소수판별법에 추가할 수 있는 방법이다.

참조

[1] 논문 Riemann's Hypothesis and Tests for Primality
[2] 논문 Probabilistic algorithm for testing primality
[3] 간행물 Certain criteria for primality of numbers connected with the little Fermat theorem
[4] 학술지 Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases 1995-08
[5] 서적 Introduction to Algorithms
[6] 서적 Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography Cambridge University Press
[7] 논문 Average case error estimates for the strong probable prime test http://www.math.dart[...]
[8] 학술발표 Prime and Prejudice: Primality Testing Under Adversarial Conditions https://eprint.iacr.[...] Association for Computing Machinery 2018-10-15
[9] 논문 Explicit bounds for primality testing and related problems
[10] 학술지 The pseudoprimes to {{nowrap|25 ⋅ 109}} http://www.math.dart[...] 1980-07
[11] 논문 On strong pseudoprimes to several bases https://www.ams.org/[...] 1993-10
[12] 웹사이트 Tables of pseudoprimes and related data http://www.cecm.sfu.[...] 2013-04-25
[13] 학술지 Strong pseudoprimes to the first eight prime bases 2014
[14] 학술지 Strong Pseudoprimes to Twelve Prime Bases 2015
[15] 웹사이트 Finding primes & proving primality — 2.3: Strong probable-primality and a practical test https://primes.utm.e[...] 2019-02-24
[16] 논문 Finding strong pseudoprimes to several bases. II https://www.ams.org/[...] 2003-10
[17] 웹사이트
[18] 웹사이트 Deterministic variants of the Miller–Rabin primality test https://miller-rabin[...] 2019-02-24
[19] 서적 Algorithmic Number Theory http://www.math.dart[...] Springer-Verlag
[20] 학술지 Lucas Pseudoprimes http://mpqs.free.fr/[...] 1980-10
[21] 논문 Further investigations with the strong probable prime test https://www.ams.org/[...]
[22] 논문 The pseudoprimes to 25·109
[23] 논문 On strong pseudoprimes to several bases


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com