[암호학] Miller-rabin test를 통한 소수판별

밀러-라빈(miller-rabin) test를 통한 prime 판별

이번 포스팅에서는 강력한 소수 판별 기법 중 하나인 밀러라빈 소수판별법에 대해서 알아보겠습니다.

밀러라빈 테스트를 요약해서 말한다면, Fermat test와 Fermat factorization을 통해 소수를 판별하는 기법이라고도 할 수 있습니다.

Fermat test란 ? 페르마의 소정리(Fermat Little Theorem)를 이용해서, 소수를 판별하고자 하는 것입니다. 페르마의 소정리란  다음과 같습니다 이때 이 역과정을 이용해서 만약 위의 식을 만족하는 p가 존재한다면, p는 소수라고 할 수 있을까? 라는 아이디어를 가지고 소수를 판별한 것입니다. 결과적으로, Fermat test만을 가지고 소수를 판별하는 것을 불가능합니다.  Fermat test를 통과하면서 합성수인 숫자가 존재하기때문입니다. 이때 이 수를 pseudo prime이라고 부릅니다.

따라서 Fermat test만을 가지고는 소수를 판별하는데에 무리가 있습니다. 그래서 수도 프라임까지 선별할 수 있도록

보완해줄 수 있는 해결책이 바로 Fermat Factorization입니다. 

 

Fermat Factorization란? Fermat Factorization은 합성수를 판단하는 기법입니다. 그 내용은 당장 위의 문장을 읽으면, 직관적으로 이해가 가지않습니다. 왜 n이 합성수가 될까? 사실은 간단합니다. x^2 - y^2 = 0 mod n 일때 이것을 n = (x+y)(x-y)*k의 꼴로 나타낼 수 있고 이것은 다시 말해서 n이 인수 (x+y)와 (x-y)를 가지는 합성수라는 것을 증명하는 것이기때문입니다. 이때 x=y이거나 x= -y 라면, 위의 식이 성립하지 않기때문에 x 는 +-y와 같지않아야한다는 조건이 생기게 되는 것입니다. 그렇다면 실제로, x-y가 진짜 n의 factor가 맞는지 간단하게 증명과정을 거쳐보겠습니다. x+y=p, x-y=q라 하자. 이때 n= p*q*k로 나타낼 수 있다. 따라서 gcd(x-y,n) = d 를 만족하는 d는 1 , p ,q , n 4가지 경우 중 하나일 수 밖에 없다. 여기서 d가 1인 경우와 n인 경우가 불가능함을 증명한다면, gcd(x-y,n) =d 에서 , d가 n의 factor p나 q를 즉 비자명한 factor를 나타낸다는 것을 보이게 된다. 먼저, d=n의 case에 대해서 불가능함을 증명해보자. x-y = 0 mod n 이므로, x=y mod n이다. 이것은 처음 가정에 x는 mod n상에서 +-y 와 다른 값이어야하므로 모순이다. 따라서 d=n은 불가능하다. 다음으로 d=1인 case에 대해서 불가능함을 증명해보자. 먼저 하나의 보조정리를 채택할텐데, 만약 a|bc 이고 gcd(a,b) =1 (a,b가 서로소)이라면 a|c 이다. 이 보조정리에 의해서 ==> n| x^2-y^2 ==> n| (x+y)(x-y) 이고 d=1 이기때문에 n|(x+y) 가 된다. 따라서 x= -y mod n이 되므로 마찬가지로 처음 가정과 모순되어 불가능하다. 그래서 d는 n의 factor p 또는 q이다.

이렇게 Fermat test와 , Factorization에 대해서 알아보았습니다. 그렇다면 이제부터 본격적으로, 두가지 기법을 활용한 밀러 라빈 테스트에 대해서 알아보겠습니다.

 

밀러 - 라빈 소수 판별 알고리즘

여기서 앞서 다루었던, 페르마 소정리를 이용한 소수판별은 앞으로 FLT, Fermat Factorization은 FF로 축약해서 부르도록 하겠습니다.

 

Algorithm 먼저 n>1인 홀수인 정수가 있을때, n-1은 항상 짝수이다.  따라서 n-1 = (2^k) * m으로 표현할 수 있다.  (단 k>1이고 m은 홀수 ) 그리고 1< a < n-1인 a를 무작위로 선택한 뒤에 b0 = a^m mod n 을 계산한다. 이때 b0가 +1이나 -1이라면, n은 FLT에 의해 probably prime으로 판정된다. (불확실한 소수) ++ ( 그 이유는, b0가 남은 지수 연산 (2^k)에 의해 a^(n-1) mod n=1을 만족하여, FLT를 통과하게 됨) 만약 b0가 +-1이 아닌 다른 값이라면, b1 = b0^2 mod n을 통해 b1을 구한다. 즉 앞서 구한 a^m mod n에 2의 제곱을 한번 실행해준 것. 이때 b1 = 1 이라면 , FF에 의해 n은 합성수가 된다. ( b0^2 = b1^2 mod n이고 b0은 +-1이 아니므로)        b1= -1 이라면, FLT에 의해 n은 소수가 된다. ( 남은 2^(k-1)의 연산을 수행하면 -1이 제곱되어 1이 됨)        b1이 +-1이 아니라면 b2 = b1 ^2 mod n 을 계산하여 위와 같은 과정을 반복한다. 이렇게 b(k-1)까지 위 과정을 반복해서, 수도 프라임을 제외하는 소수 판별을 시행한다.

밀러 라빈 테스트를 통해서도 여전히 아주 강력한 수도 프라임에 대해서는 판별을 못할 가능성이 있기때문에

다양한 base 값을 가지고 테스트를 시행할 수록 정확성이 매우 높아집니다.

 

실제로 위의 알고리즘을 파이썬으로 구현해보았습니다.

 

def miller_rabin_test(n,b,s,t):     #n은 odd integer     #b는 base     # n-1 = 2^s *t     x = pow(b, t, n)  # b0= b^t mod n     if x == 1 or x == n-1:         return 1     else: #b0가 +-1이 아니라면         for i in range(s):             if x==n-1:                 return 1             x= pow(x,2,n)         return 0 def is_prime(n):     s=0     if n<2 or not n&1:         return 0 #짝수이거나 1은 소수가 아니다.     if n==2:         return 1 #2는 소수이다.     t = (n-1)     while t%2==0:         s=s+1         t>>=1     for i in range(0,25):         b = random.randrange(2,n-1);         test=miller_rabin_test(n, b, s, t)         if test==0:             return 0     return 1

 

위의 코드를 활용한 소수판별 결과.

감사합니다.