밀러-라빈 소수판별법 문서 원본 보기

{{위키데이터 속성 추적}}
'''밀러-라빈 소수판별법'''(Miller-Rabin primality test)은 입력으로 주어진 수가 [[소수 (수론)|소수]]인지 아닌지 [[소수판별법|판별]]하는 [[알고리즘]]이다. '''라빈-밀러 소수판별법'''(Rabin-Miller primality test)이라고도 한다. [[개리 L. 밀러]]의 원래 알고리즘은 [[일반 리만 가설]]에 기반한 [[결정론적 알고리즘]]이었는데, [[미하엘 라빈]]이 [[확률적 알고리즘]]으로 변경했다.

== 이론적 배경 ==
[[페르마 판별법]]이나 [[솔로바이-스트라센 소수판별법]]과 마찬가지로, 밀러-라빈 소수판별법은 소수가 가지는 특별한 성질을 이용한다. <math>n</math>이 홀수인 소수라고 할 때, <math>n - 1</math>은 <math>2^s d</math> 라고 할 수 있다.
이때, <math>s</math>는 정수이고 <math>d</math>는 홀수이다. 이것은 <math>n - 1</math>을 계속해서 2로 나눈 형태이다. 이제 어떤 <math>a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^*</math>에 대해, 다음 식 중 한 가지가 성립한다.
* <math>a^{d} \equiv 1 \pmod{n}\,</math>
* <math>a^{2^r \cdot d} \equiv -1\pmod{n} \mbox{ for some 0 } \le r \le s-1</math>

위 두 가지 식 중에서 한 가지가 성립한다는 것은 다음과 같은 [[페르마 소정리]]에서 유도할 수 있다
:<math>a^{n-1} \equiv 1\pmod{n}\,</math>

즉 <math>a^{n-1}</math>의 제곱근을 계속 구해나가면, 1 이거나 -1을 얻게 된다. 만약 -1이 나오면 두 번째 식이 성립하는 것이고, 더 이상 검사하지 않아도 된다.

제곱근을 계속 구해나가도 두 번째 식이 성립하지 않으면, 마찬가지로 1이나 -1의 값을 가질 첫 번째 식을 검사해야 한다. 그런데, 두 번째 식이 성립하지 않는다면, <math>r = 0</math>일 때 성립할 수 없고 결과적으로 다음 식이 성립한다.
:<math>a^{2^0\cdot d} = a^d \not\equiv -1\pmod{n}</math>

그러므로 두 번째 경우가 성립하지 않으면, 첫 번째는 반드시 성립한다.

밀러-라빈 소수판별법은 위와 같은 관계를 이용한다. <math>n</math>이 소수인지 아닌지 검사하려고 할 때, 다음 두 식이 성립하면 <math>a</math>는 <math>n</math>이 합성수라는 것에 대한 '''강한 증거'''(strong witness)가 된다.
* <math> a^{d} \not\equiv 1\pmod{n} </math>
* <math> a^{2^r d} \not\equiv -1\pmod{n} \mbox{ for all } 0 \le r \le s-1 </math>

만약 위 식이 성립하지 않으면 <math>a</math>는 '''강한 거짓증거'''(strong liar)라 하고, <math>n</math>은 '''아마 소수일 것 같다'''(probable prime)고 한다.

== 알고리즘 및 시간복잡도 ==
알고리즘은 다음과 같다.
:'''입력''': <math>n</math>: 소수인지 검사할 숫자 , <math>k</math>: 소수판별법을 몇회 실행할지 결정하는 인자.
:'''출력''': <math>n</math>이 합성수이면 <u>합성수이다</u>, 아니면 <u>아마 소수일 것 같다</u>는 것을 반환한다.
:<math>n - 1</math>을 <math>2^s d</math> 형태로 바꾼다.
:다음을 ''k'' 번 반복한다.
::<math>[1, n - 1]</math>에서 임의의 <math>a</math>를 선택한다.
::<math>[0, s - 1]</math>의 모든 <math>r</math>에 대해 <math>a^d \,\bmod\, n \ne 1</math>이고 <math>a^{2^rd} \,\bmod\, n \ne n -1 </math>이면 <u>합성수이다.</u>
:위 조건을 만족하지 않으면 <u>소수일 것 같다.</u>

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

== 작은 수에 대한 판별 ==
판별할 수 <math>n</math>의 크기가 작을 경우, 작은 수의 <math>a</math>에 대해서만 검사해보면 결정론적으로 소수를 판별할 수 있다는 것이 알려져 있다. Pomerance, Selfridge, Wagstaff,<ref>{{인용|last=Pomerance |first=C. |last2=Selfridge |first2=J. L. |last3=Wagstaff |first3=S. S., Jr. |lastauthoramp=yes |year=1980 |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |volume=35 |issue=151 |pages=1003–1026 |doi=10.2307/2006210 |issn= }}</ref> 그리고 Jaeschke<ref>{{인용|last=Jaeschke |first=Gerhard |last2= |first2= |last3= |first3= |lastauthoramp= |year=1993 |title=On strong pseudoprimes to several bases |journal=Mathematics of Computation |volume=61 |issue=204 |pages=915–926 |doi=10.2307/2153262 |issn= }}</ref>에 의하면

* <math>n < 1,373,653</math>일 경우 <math>a = 2, 3</math>에 대해서만 검사해보면 충분하다
* <math>n < 9,080,191</math>일 경우 <math>a = 31, 73</math>에 대해서만 검사해보면 충분하다
* <math>n < 4,759,123,141</math>일 경우 <math>a = 2, 7, 61</math>에 대해서만 검사해보면 충분하다
* <math>n < 2,152,302,898,747</math>일 경우 <math>a = 2, 3, 5, 7, 11</math>에 대해서만 검사해보면 충분하다
* <math>n < 3,474,749,660,383</math>일 경우 <math>a = 2, 3, 5, 7, 11, 13</math>에 대해서만 검사해보면 충분하다
* <math>n < 341,550,071,728,321</math>일 경우 <math>a = 2, 3, 5, 7, 11, 13, 17</math>에 대해서만 검사해보면 충분하다

== 참고 ==
다른 확률적 소수판별 알고리즘과 마찬가지로, <math>n</math>이 소수가 아닌데도 알고리즘 실행결과 언제나 거짓증거가 나와서 <math>n</math>이 소수라고 잘못 판별할 수 있다. 이런 <math>n</math>을 [[강한 의사소수]]라고 한다.

소수판별에 필요한 검사를 여러 번 하면 할수록 정확도는 높아진다. 모든 홀수 소수 <math>n</math>에 대하여 <math>a</math>의 최소한 3/4은 <math>n</math>이 합성수라는 것에 대한 강한 증거가 된다.
밀러-라빈 소수판별법의 강력한 거짓증거 집합은 솔로바이-스트라센 소수판별법의 강력한 거짓증거 집합의 부분집합이다. 그러므로, 밀러-라빈 소수판별법이 솔로바이-스트라센 소수판별법보다 더 강력한 소수판별법이다.
<math>n</math>이 합성수일 때, 밀러-라빈 소수판별법에서 <math>n</math>이 아마도 소수일 것이라고 판별할 확률은 최대 <math>4^{-k}</math>이다. 반면에, 솔로바이-스트라센 소수판별법에서 합성수 <math>n</math>이 아마도 소수일 것이라고 판별할 확률은 최대 <math>2^{-\!k}</math>이다.

평균적으로 어떤 합성수가 아마도 소수일 것이라고 판별될 확률은 <math>4^{-\!k}</math>보다 현저히 낮다. 확률의 한계값을 Damgard, Landrock , Pomerance등이 명확하게 계산한 결과가 있는데, 이것은 소수를 생성하는데만 사용할 수 있고 소수를 판별하는데는 사용할 수 없다. 암호학에서 공격자가 소수 대신 의사소수를 사용하여 암호시스템을 공격하려 할 수도 있다. 이런 공격에 안전하려면 의사난수인지 더 엄밀하게 검사해야 하므로, <math>4^{-\!k}</math>이라는 확률을 사용하는 것이 안전하다.

[[일반화 리만 가설]]이 맞다면, <math>2 \,\log^2 n</math>개의 <math>a</math>로 검사했을 때 '아마 소수일 것'이라고 판별되었으면 이 수는 실제로 소수이다. 이때, 이 알고리즘은 <math>\tilde{O}(\log^4 n)</math>의 시간복잡도를 가지는 '결정론적' 소수판별법이 된다.

== 각주 ==
<references/>

== 참고 문헌 ==
* I. Damgard, P. Landrock and C. Pomerance (1993), ''Average case error estimates for the strong probable prime test'', Math. Comp. 61(203) p.177–194.
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7}}. Pages 890–896 of section 31.8, Primality testing.

== 외부 링크 ==
* [https://web.archive.org/web/20070204201558/http://www.cryptomathic.com/labs/rabinprimalitytest.html Online demo of Miller-Rabin]
* [http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html MathWorld - Rabin-Miller Strong Pseudoprime Test]

{{수론 알고리즘}}

[[분류:소수 판별법]]
[[분류:유한체]]