어떤 수가 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 라는게 있다.. 심심할때 읽어보자..



'Problem Solving > Algorithm notes' 카테고리의 다른 글

The Tower of Hanoi  (0) 2011.08.28
Gaussian Prime  (0) 2011.04.03
점과 선분과의 거리  (2) 2011.01.22
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Modular Exponentiation (Big Mod)  (2) 2010.02.19
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Bell Number  (0) 2009.07.12
Finding Minimum Path Cover in DAG  (0) 2009.06.15
Plane Equation (평면의 방정식)  (0) 2009.04.16

to Top