[Algorithm] Miller-Rabin Primality Test : 밀러-라빈 소수판별법

Miller-Rabin Primality Test : 밀러-라빈 소수판별법

• 임의의 수 a가 소수인지 아닌지를 확률적으로 판별해주는 알고리즘
• 이 알고리즘은 주어진 수 a이 소수임을 증명하지 않고, 소수가 아닐 확률(여사건)을 분석하여 소수를 판별함.
• 왜 확률적인가?
  • a가 큰수이고, 소수 판별을 위해 먼저 2로 나누어 떨어지지 않는다고 가정한다면, 2, 4, 6, 8 등의 2의 배수인 수로도 나누어 떨어지지 않는다. 즉 이 수들에 대해서 검사할 필요가 없다. -> 전체 자연수에 대해서 50%의 숫자들을 검사한 효과!
  • a가 3으로 나누어 떨어지지 않는다면 6, 9, 12 등의 수에 대해서도 검사할 필요가 없다. -> 전체 자연수에 대해서 33%의 숫자들을 검사한 효과
  • a가 5로 나누어 떨어지지 않는다면, 10, 15, 20 등의 수에 대해서도 검사할 필요가 없다 -> 전체 자연수에 대해서 20%의 숫자들을 검사한 효과 
  • 작은 소수들을 통해 검증한 결과가 전체 자연수 영역의 일정 비율을 커버함
  • 몇개의 작은 소수들로 나누어 떨어지는 가에 대한 확인을 통해 임의의 수 a가 소수일 확률을 구할 수 있음

    

 

 

1️⃣ 소수 판별 알고리즘의 기반 이론

• n이 홀수인 소수라면, 이때 n보다 작은 자연수 a에 대해서 다음 식 중 한가지가 성립한다. (페르마의 소정리)

1.  a^d = 1 (mod n)
2. r = 0,1,2,....s-1의 자연수 중 하나 이상의 r에 대해서, a^(d x 2^r) = -1 (mod n) : 단, 임의의 정수 s와 홀수 d에 대해서, n-1 = 2^s x d를 만족한다. 

example) n = 37 일때, n-1 = 36 = 2^2 x 9 : s=2, d=9

 

밀러-라빈 알고리즘은 주어진 수 !이 소수임을 증명하지 않고, 소수가 아닐 확률(여사건)을 분석하여 소수를 판별함.

(1), (2) 두 식 중, 하나가 만족하는 경우의 여사건 = !(1) && !(2) 

소수가 아닐 확률 (여사건)을 분석하여 소수 판별 (3) && (4) 에 해당

(3), (4)을 동시에 만족할 경우, 해당 수를 소수가 아닌 합성수로 판단하고, 그 외의 경우 해당 n을 소수로 판별함.

 

따라서 위의 예제 표 상에서, 2,3,4,5,6,7에 대해서 밀러-라빈 테스트 실패 -> 6번의 테스트 실패 = 37은 소수일 가능성이 매우 높다는 것을 알 수 있다.

 

 

 

 

 

2️⃣ 그렇다면, 비교적 정확하게 n이 소수임을 판별하기 위해서는 적어도 몇 번의 밀러-라빈 테스트를 수행해야 하는가?

Pomerance, Selfridge, Wagstaff와 jaeschke의 논문에 의하면, 

• ! < 1,373,653 인 경우, a = 2,3 
• ! < 9,080,191 인 경우,   a = 31,73
• ! < 4,759,123,141 인 경우, a = 2,7,61
• ! < 2,152,302,898,747 인 경우, a = 2,3,5,7,11
• ! < 3,474,749,660,383 인 경우, a = 2,3,5,7,11,13
• ! < 341,550,071,728,321 인 경우, a = 2,3,5,7,11,13,17

-> 상당히 적은 수의 테스트에 대해서도 100%의 소수 판별 정확도를 보임!

 

 

 

 

3️⃣ 의사 코드

• 입력 : n 
• 출력 : true or false ( true = 소수, false = 소수X )

  set tester = {2, 3} or {31, 73} or {2, 7, 61} ...  // 몇번의 밀러-라빈 테스트를 수행할지?
  
  // 첫번째 테스트
  for each test in tester:
  	calculate (s,d) where n-1 = 2^s * d
      if(a^d % n)!=1:
      	result = False
      else:
      	result = True
  
  // 두번째 테스트
  for each r=0 to s-1:
  	if (a^(2^r * s)) != (n-1):
      	result = result & False  // n은 합성수
      else:
      	result = result & True  // n은 소수
  
  return result​

 

 

 

AKS 소수 판별법
- 2002년, 컴퓨터 과학자 마닌드라 아그라왈, 니라지 카얄, 니틴 삭세나가 발표한 논문 'PRIMES is in P"에서 소수 판별 문제가 P임이 증명됨.

4️⃣ AKS 소수판별법 vs 밀러-라빈 알고리즘

• 두 알고리즘 모두 general 하여, 모든 양의 정수에 대해서 판별 가능
• 두 알고리즘 모두 다항시간 내에 풀 수 있음
• 두 알고리즘 모두 결정론적임
• 밀러-라빈은 리만 가설에 기반하고 있으며, 리만 가설이 참일 경우에만 참임
• 그러나, AKS는 증명되지 않은 가설에 기반하고 있지 않음
• 그러나, AKS 소수 판별법은 주어진 수가 소수인지 아닌지를 정확하게 판별할 수 있음에도 불구하고, 밀러-라빈 알고리즘보다 속도가 훨씬 느려서, 아직까지도 밀러-라빈 알고리즘이 주로 활용되고 있음.

 

 

 

 

5️⃣ C++ 코드

#include <iostream>
using namespace std;

typedef unsigned long long ull;
ull  mulmod(ull  a, ull  b, ull  mod)
{
    ull  x = 0,y = a % mod;
    while (b > 0)
        {
            if (b % 2 == 1)
                {
                    x = (x + y) % mod;
                }
            y = (y * 2) % mod;
            b/= 2;
        }
    return x % mod;
}

ull  modulo(ull  base, ull  exponent, ull  mod)
{
    ull  x = 1;
    ull  y = base;
    while (exponent > 0)
        {
            if (exponent % 2 == 1)
                x = (x * y) % mod;
            y = (y * y) % mod;
            exponent = exponent/2;
        }
    return x % mod;
}

bool PrimalityTest(ull  n,ull  iteration)
{
    if (n < 2)
        {
            return false;
        }

    if (n != 2 && n % 2==0)
        {
            return false;
        }

    ull  d = n - 1;
    while (d % 2 == 0)
        {
            d/= 2;
        }

    for (ull  i = 0; i < iteration; i++)
        {
            ull  a = rand() % (n - 1) + 1;
            ull  temp = d;
            ull  mod = modulo(a, temp, n);
            while (temp != n - 1 && mod != 1 && mod != n - 1)
                {
                    mod = mulmod(mod, mod, n);
                    temp *= 2;
                }
            if (mod != n - 1 && temp % 2 == 0)
                {
                    return false;
                }
        }
    return true;
}

int main()
{
    ull  iteration = 10;
    ull  n;
    cin>>n;
    if (PrimalityTest(n, iteration))
        cout<<1<<endl;
    else
        cout<<0<<endl;
    return 0;
}

 

 

 

---

Reference

• 서울과학기술대학교 알고리즘 수업