Miller-Rabin 소수 판별법 Code

Miller-Rabin에 대해 공부해봤습니다. 정리까지 끝냈으나 포스팅은 늦어질 거 같아서 코드 먼저 올려두겠습니다.

 

[N의 범위가 int일 때]

// Miller-Rabin, N이 int의 범위 일때

#include <iostream>
#include <cmath>
using namespace std;

int base[3] = {2, 7, 61};

int power(int a, int k, int mod){
    if(k == 0) return 1;
    else if(k == 1) return a;
    else{
        int value = power(a, k / 2, mod) % mod;
        
        if(k % 2 != 0){
            return (((value * value) % mod) * (a % mod)) % mod;
        }
        else{
            return value * value % mod;
        }
    }
}

bool millerRabin(int n, int a){
    // a(비교하는 수)가 모두 소수이기 때문에 a % N의 나머지가 0이라면
    // N도 소수다.
    if(a % n == 0) return true;
    int k = n - 1;
    while(true){
        // 거듭제곱 분할정복을 이용하여 더 빠르게
        int temp = power(a, k, n);
        // 2번 정리에 해당
        if(temp == n - 1) return true;
        // 1번 정리와 2번 정리의 r == 0인 경우
        if(k % 2){
            if(temp == 1 || temp == n - 1) return true;
        }
        k /= 2;
    }
}

bool isPrime(int n){
    if(n == 2) return true;
    else if(n % 2 == 0) return false;
    else{
        // N이 소수가 아니더라도 만족하는 특정한 a가 존재하기 때문에
        // 여러 a와 많이 비교해보아야 한다.
        for(int i = 0; i < 3; i++){
            int a = base[i];
            if(!millerRabin(n, a)){
                return false;
            }
        }
        return true;
    }
}

int main(){
    int n;
    cin >> n;
    if(isPrime(n)) cout << "It's Prime";
    else cout << "It's not Prime";
}