Primality Testing (Miller-Rabin)
Problem Solving/Algorithm notes 2010. 3. 23. 01:25
어떤 수가 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 으로 나눠봐야하겠지만..
단순히 다음과 같이 할 수 있다..
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 이기 때문이다.. (진짜????)
뭐.. 이러쿵 저러쿵 하면.. 다음과 같은 코드가 나온다..
아.. 어렵다.. ㅠ_ㅠ
참고로 Carmichael Number 라는게 있다.. 심심할때 읽어보자..
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!
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
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 |