밀러-라빈 소수판별법

위키백과 ― 우리 모두의 백과사전.

밀러-라빈 소수판별법(Miller-Rabin primality test)은 입력으로 주어진 수가 소수인지 아닌지 판별하는 알고리즘이다. 라빈-밀러 소수판별법(Rabin-Miller primality test)이라고도 한다. 개리 L. 밀러의 원래 알고리즘은 일반 리만 가설에 기반한 결정론적 알고리즘이었는데, 마이클 O. 라빈이 확률적 알고리즘으로 변경했다.

[편집] 이론적 배경

페르마 판별법이나 솔로바이-스트라센 소수판별법과 마찬가지로, 밀러-라빈 소수판별법은 소수가 가지는 특별한 성질을 이용한다. 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}$
$a^{2^r\cdot d} \equiv -1\pmod{n}$ for some $0 \le r \le s-1$

위 두가지 식 중에서 한가지가 성립한다는 것은 다음과 같은 페르마의 작은 정리에서 유도할 수 있다

$a^{n-1} \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이 합성수라는 것에 대한 강한 증거(strong witness)가 된다.

$a^{d} \not\equiv 1\pmod{n}$
$a^{2^rd} \not\equiv -1\pmod{n}$ for all $0 \le r \le s-1$

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

[편집] 알고리즘 및 시간복잡도

알고리즘은 다음과 같다.

입력: 소수인지 검사할 숫자 n; k: 소수판별법을 몇회 실행할지 결정하는 인자.

출력: n이 합성수이면 합성수이다, 아니면 아마 소수일 것 같다는 것을 반환한다.

n − 1을 2^s × d 형태로 바꾼다.

다음을 k 번 반복한다.

[1, n − 1]에서 임의의 a를 선택한다.

[0, s − 1]의 모든 r에 대해 a^d mod n ≠ 1 이고 $a^{2^rd}$ mod n ≠ −1 이면 합성수이다.

위 조건을 만족하지 않으면 소수일 것 같다.

제곱을 반복하는 방법으로 모듈로 지수승을 계산하면 이 알고리즘의 시간복잡도는 O(k × log³ n)이다.(k는 a의 개수이다.) 이때 FFT를 이용하여 곱셈의 횟수를 줄이면 시간복잡도를 Õ(k × log² n)로 줄일 수 있다.

[편집] 참고

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

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

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

일반 리만 가설이 맞다면, 2(log n)²개의 a로 검사했을때 '아마 소수일 것'이라고 판별되었으면 이 수는 실제로 소수이다. 이때, 이 알고리즘은 Õ((log n)⁴)의 시간복잡도를 가지는 '결정론적' 소수판별법이 된다.

[편집] 참고문헌

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 0262032937. Pages 890–896 of section 31.8, Primality testing.