Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 라빈-밀러(Rabin-Miller) 소수 판별 프로그램 – 알고리즘과 예제 코드

라빈-밀러 소수 판별 테스트란?

라빈-밀러(Rabin-Miller) 소수 판별 테스트는 주어진 수가 소수(prime number)인지 아닌지를 판별하는 대표적인 확률적 알고리즘입니다. 페르마 소수 판별법이나 솔로베이-스트라센(Solovay-Strassen) 테스트와 유사한 방식으로 동작하며, 이 테스트의 기반이 되는 개념은 처음에 러시아 수학자 M. M. 아르튜호프(M. M. Artjuhov)에 의해 발견되었습니다.

이 테스트는 페르마의 소정리에 기반을 두고 있습니다. 홀수 n이 소수일 때, n−1 = 2s·d(d는 홀수) 형태로 분해하면 임의의 밑 a에 대해 ad ≡ 1 (mod n)이거나, 어떤 0 ≤ r < s에 대해 a2r·d ≡ −1 (mod n)이 성립해야 합니다. 이 조건을 만족하지 않으면 n은 확실한 합성수이며, 만족하더라도 n이 소수일 '확률'이 높다는 것만 보장됩니다. 다만 반복 횟수 k를 늘리면 합성수를 소수로 오판할 오류 확률이 최대 4−k까지 급격히 줄어들기 때문에, 실용적으로는 충분히 신뢰할 수 있는 결과를 얻을 수 있습니다.

알고리즘

구현에서는 큰 수를 곱하거나 거듭제곱할 때 발생할 수 있는 오버플로우를 피하기 위해, 모듈로 연산을 단계별로 수행하는 두 개의 보조 함수(mulmod, modulo)를 사용합니다.

Begin
    함수 mulmod(a, b, m): (a × b) mod m 을 오버플로우 없이 계산
        x ← 0, y ← a mod m
        while b > 0:
            if b mod 2 == 1:
                x ← (x + y) mod m
            y ← (y * 2) mod m
            b ← b / 2
        return x mod m
End

Begin
    함수 modulo(base, e, m): base^e mod m 을 빠른 거듭제곱으로 계산
        x ← 1, y ← base
        while e > 0:
            if e mod 2 == 1:
                x ← (x * y) mod m
            y ← (y * y) mod m
            e ← e / 2
        return x mod m
End

Begin
    함수 Miller(p, iteration): p가 소수인지 검사
        if p < 2: return false
        if p ≠ 2 이고 p mod 2 == 0: return false
        s ← p − 1
        while s mod 2 == 0:
            s ← s / 2
        for i = 0 to iteration − 1:
            a ← rand() mod (p − 1) + 1, temp ← s
            mod ← modulo(a, temp, p)
            while temp ≠ p − 1 이고 mod ≠ 1 이고 mod ≠ p − 1:
                mod ← mulmod(mod, mod, p)
                temp ← temp * 2
            if mod ≠ p − 1 이고 temp mod 2 == 0:
                return false      // 합성수로 확정
        return true               // 소수일 가능성이 매우 높음
End

C++ 예제 코드

#include <iostream>
#include <cstdlib>
#define ll long long
using namespace std;

// (a * b) % m 을 오버플로우 없이 계산한다.
ll mulmod(ll a, ll b, ll m) {
    ll x = 0, y = a % m;
    while (b > 0) {
        if (b % 2 == 1) {
            x = (x + y) % m;
        }
        y = (y * 2) % m;
        b /= 2;
    }
    return x % m;
}

// base^e % m 을 빠른 거듭제곱 방식으로 계산한다.
ll modulo(ll base, ll e, ll m) {
    ll x = 1;
    ll y = base;
    while (e > 0) {
        if (e % 2 == 1)
            x = (x * y) % m;
        y = (y * y) % m;
        e = e / 2;
    }
    return x % m;
}

// 라빈-밀러 테스트: 소수이면 true, 아니면 false 반환
bool Miller(ll p, int iteration) {
    if (p < 2) {
        return false;
    }
    if (p != 2 && p % 2 == 0) {
        return false;
    }
    ll s = p - 1;
    while (s % 2 == 0) {
        s /= 2;
    }
    for (int i = 0; i < iteration; i++) {
        ll a = rand() % (p - 1) + 1, temp = s;
        ll mod = modulo(a, temp, p);
        while (temp != p - 1 && mod != 1 && mod != p - 1) {
            mod = mulmod(mod, mod, p);
            temp *= 2;
        }
        if (mod != p - 1 && temp % 2 == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int iteration = 10; // 테스트 반복 횟수
    ll num;
    cout << "Enter integer to test primality: ";
    cin >> num;
    if (Miller(num, iteration))
        cout << num << " is prime" << endl;
    else
        cout << num << " is not prime" << endl;
    return 0;
}

실행 결과

Enter integer to test primality: 26
26 is not prime

위 실행 예시에서는 26을 입력했습니다. 26 = 2 × 13이므로 프로그램은 26이 소수가 아니라고 올바르게 판별합니다.

참고 사항

  • 반복 횟수(iteration)를 늘릴수록 판별의 신뢰도가 높아집니다. 일반적으로 10~20회면 실용적인 용도로 충분합니다.
  • 시간 복잡도는 반복 횟수를 k라 할 때 약 O(k · log³ n)으로, 매우 큰 수에도 효율적으로 동작합니다.
  • rand() 함수의 표현 범위가 제한적이므로, 64비트 전체 범위의 큰 수를 검사하려면 mt19937_64 같은 더 넓은 범위의 난수 생성기를 사용하는 것이 좋습니다.