Primality Testing (Miller-Rabin)

어떤 수가 prime 인지 아닌지 판단하는 작업을 primality testing 이라고 한다
pirmality testing 에는 여러가지 방법이 있는데..
Introduction to Algorithms 책 page 889 ~ 892 까지의 내용을 대략 정리해보았다


Fermat's Little Theorem 에 의하면 p 가 prime 일 경우 다음을 항상 만족한다

a^(p-1) mod p = 1 (a 는 p 보다 작은 자연수)

하지만 모든 a 에 대해서 위 식을 만족한다고해서 반드시 p 가 prime 인것은 아니다
그러나.. prime 일 가능성이 상당히 높다


어떤 수 p 가 prime 인지 아닌지 판단해본다고 하자..
제대로 하려면 sqrt(p) 보다 작거나 같은 모든 prime 으로 나눠봐야하겠지만..
단순히 다음과 같이 할 수 있다..

PSEUDOPRIME(n)
1  if MODULAR-EXPONENTIATION(2, n-1, n) <> 1 (mod n)
2      then return COMPOSITE  --> Definitely.
3      else return PRIME           --> We hope!

MODULAR-EXPONENTIATION 에 대해서는 여기 포스팅 했다..

위의 코드는 항상 올바른 결과를 return 하지 않으므로 이를 Pseudoprimality Testing 이라고 한다
그리고 p 보다 작은 모든 a 에 대해서 시도한게 아니라 단지 a = 2 인 경우만 시도했다
단지 2 로만 하더라도 상당히 높은 정확도를 보이는데.. 이를 base-2 pseudoprime 이라고 한다


위 개념을 바탕으로 좀 더 개선된 Miller-Rabin Primality Test 가 있다..

대략적인 내용은..
어떤 홀수 n 에 대해서 (짝수중에 소수는 2밖에 없으므로.. 그냥 홀수만 검사하기로 하자)

a^(n-1) mod n <> 1

위 식을 빨리 검사하는게 목적이다..
n-1 = u * 2^t 형태로 나타낼수 있으므로.. a^(n-1) = (a^u)^(2^t) 이 된다.. 
그래서 t 번 만큼 loop 를 돌면서 제곱을 해나가는데 중간에 modulo 결과가 1 이 나오면 stop 할 수 있다
x = x^2 = 1 (mod n) 을 만족하는 x 는 1 이거나 composite 이기 때문이다.. (진짜????)

뭐.. 이러쿵 저러쿵 하면.. 다음과 같은 코드가 나온다..

WITNESS(a, n)
1  let n - 1 = 2^t * u, where t >= 1 and u is odd
2  x0 <- MODULAR-EXPONENTIATION(a, u, n)
3  for i <- 1 to t
4      do xi <- xi-1 * xi-1 mod n
5          if xi = 1 and xi-1 <> 1 and xi-1 <> n-1
6              then return TRUE
7  if xi <> 1
8      then return TRUE
9  return FALSE

MILLER-RABIN(n, s)
1  for j <- 1 to s
2      do a <- RANDOM(1, n-1)
3          if WITNESS(a, n)
4              then return COMPOSITE  --> Definitely
5  return PRIME                              --> Almost surely

아.. 어렵다.. ㅠ_ㅠ


참고로 Carmichael Number 라는게 있다.. 심심할때 읽어보자..