[전공수업][정보보호] Miller-Rabin Test

해당 내용은 20년 2학기 COSE354 "정보보호" 수업을 듣고 정리한 내용입니다.

---

Primality Testing

 

수많은 암호 알고리즘은, 매우 큰 소수를 사용한다. (RSA가 대표적인 예시).

이로써 주어진 매우 큰 숫자가 소수인지 판별하기 위한 효율적인 알고리즘을 찾는게 중요해졌다.

 

전통적으로, trial한 devision을 활용한 "sieve"의 방식으로 소수를 구했다.

이 말은 즉슨, 주어진 숫자의 제곱근까지의 범위에서, 모든 소수들로 나눠보는 시도를 했다. 하지만 이는 매우 큰 숫자에 대해서는 적용하기 어렵다.

 

그래서 대안으로 고안된 방법이,

 

1. Use statistical primarility tests based on properties of primes

2. Then use a slower deterministic primarility test

 

위 과정으로 매우 큰 숫자가 소수인지 판별해보는 대안이다.

 

1번 과정의 경우, statistical test, 즉 probabilitic test이다. 모든 소수들은 이 test를 만족시키지만, 해당 test에서 소수라고 판별되었더라도, 실제로는 합성수인 pseudo-prime이 존재한다는 의미다. 1번 과정에서 사용되는 알고리즘이 "Miller-Rabin Algorithm"이다.

 

2번 과정은, 대표적으로 AKS test가 있는데, 1번 과정보다 효율적이지 않아, Miller-Rabin Algorithm을 통해 합성수 몇개를 걸러낸 후 사용된다.

 

 

Properties Of Prime Numbers

Miller-Rabin test는 소수의 특성들을 활용한다고 했는데, 그렇다면 소수의 두가지 특성에 대해 알아보자.

 

Property 1.

If p is prime and a is a positive integer with a<p

a² mod p = 1 if and only if

a mod p =1 or a mod p =-1 mod p = p -1

 

a는 p 보다 작으니 이해가 된다. 당연히 그럴 것이다.

 

Property 2.

For a prime p>2, can write p-1=2^kq with k>0, q odd.

Let a be any integer 1<a<p-1

Then, one of the following conditions is true: 

1)  a^qmod p =1

2)  There is some j (1≦j≦k) that a^2j-1*qmod p =-1 = p-1

 

p-1이 2의 k 제곱 곱하기 q인 이유는 p가 2보다 큰 소수면 홀수고, p-1은 짝수이기 때문이다.

밑의 두 조건들은 페르마 소정리에 근거해 도출된다.

 

 

Miller-Rabin Algorithm

소수의 속성을 활용해 n이라는 큰 숫자가 주어졌을 때 소수인지 아닌지 판별가능하다.

 

Test(n) is:

1. Find integers k,q with k>0, q odd, so that (n-1)=2^kq

2. Select a random integer a, 1<a<n-1

3. If a^qmod n=1 then return ("inconclusive")

4. for j=0~k-1 do

         5. a^2jqmod n = n - 1

                 then return ("inconclusive")

6. return ("composite")

 

6번 줄을 통해 "composite"이라는 결과가 나오면 확실히 소수가 아니다. 하지만 결과가 "inconclusive"이면 무조건 소수는 아니지만, 적어도 pseudo-prime이다.

 

 

위의 알고리즘을 활용해 한번 퀴즈를 풀어보자.

n=29이고, a=2 이면, n-1=28, 2의 7 제곱 mod 29 는 12 이므로 통과, 2의 14제곱 mod 29는 28이므로 inconclusive이다. 소수일 수도 있다는 뜻!

 

반면, n=2047, a=2라고 해보자. 2046은 2 곱하기 1023, k=1이고 q는 1023이다. 2의 1023 제곱 mod 2047의 결과는 1이므로 inconclusive. 근데 사실 2047은 23 곱하기 89이므로 소수가 아니다. 그러므로 2047은 pseudo-prime이다.

 

 

 

Probabilistic Considerations

그렇다면 Miller-Rabin test는 정확하지 않을 수도 있다는 뜻인데, 확률적으로 얼마나 정확할까?

 

Miller-Rabin test에서 pseudo-prime을 찾을 확률은 1/4보다 작다.

그러므로 a값을 바꿔가며 t번 반복하면, n이 소수일 확률은 1-4^-t 보다 크다. 

만약 t가 10이라면, 확률이 0.999999보다 크다. 

 

그러므로, Miller-Rabin test를 시행한 후 AKS test를 시행하면 큰 숫자에 대해 소수를 판별할 수 있다.