C++로 구현하는 페르마 소수성 테스트(Fermat Primality Test)

페르마 소수성 테스트(Fermat Primality Test)는 주어진 수가 소수인지 아닌지를 판별하는 확률적 알고리즘입니다. 이 테스트는 페르마의 소정리에 기반하며, 다음과 같습니다.

p가 소수이고 a가 p의 배수가 아니라면, 항상 a^p-1 ≡ 1 (mod p)가 성립합니다.

즉, 무작위로 선택한 밑(base) a에 대해 a^m-1 mod m의 값이 1이 아니라면 m은 합성수임이 확실하고, 1이라면 m이 소수일 가능성이 높다고 판단하는 방식입니다. 아래에서 알고리즘의 동작 원리와 C++ 전체 코드를 살펴보겠습니다.

알고리즘

핵심 함수는 두 가지입니다.

1. 모듈러 거듭제곱 함수 (modulo)

(base^e) mod mod 값을 분할 정복(이진 거듭제곱) 방식으로 빠르게 계산합니다. 지수를 절반씩 줄여가며 계산하기 때문에 시간 복잡도는 O(log e)입니다.

Begin
    modulo(base, e, mod)
    a = 1
    b = base
    while (e > 0)
        if (e mod 2 == 1)
            a = (a * b) % mod
        b = (b * b) % mod
        e = e / 2
    return a % mod
End

2. 페르마 테스트 함수 (Fermat)

입력받은 수 m에 대해 지정된 횟수(iterations)만큼 무작위 밑 x를 선택하여 페르마의 소정리를 검증합니다. 단 한 번이라도 조건을 만족하지 않으면 즉시 합성수로 판정합니다.

Begin
    Fermat(m, iterations)
    if (m == 1)
        return false
    for (i = 0; i < iterations; i++)
        x = rand() mod (m - 1) + 1
        if (modulo(x, m - 1, m) != 1)
            return false
    return true
End

예제 코드

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.

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

// 분할 정복 기반 모듈러 거듭제곱: (base^e) % mod 반환
ll modulo(ll base, ll e, ll mod) {
    ll a = 1;
    ll b = base;
    while (e > 0) {
        if (e % 2 == 1) {
            a = (a * b) % mod;
        }
        b = (b * b) % mod;
        e = e / 2;
    }
    return a % mod;
}

// 페르마 소수성 테스트
bool Fermat(ll m, int iterations) {
    if (m == 1) {
        return false;
    }
    for (int i = 0; i < iterations; i++) {
        ll x = rand() % (m - 1) + 1;
        if (modulo(x, m - 1, m) != 1) {
            return false;
        }
    }
    return true;
}

int main() {
    int iteration = 70;
    ll num;
    cout << "소수 여부를 확인할 정수를 입력하세요: ";
    cin >> num;
    if (Fermat(num, iteration))
        cout << num << "은(는) 소수입니다" << endl;
    else
        cout << num << "은(는) 소수가 아닙니다" << endl;
    return 0;
}

실행 결과

소수 여부를 확인할 정수를 입력하세요: 13
13은(는) 소수입니다

주의 사항

페르마 테스트는 확률적 알고리즘이므로 완벽하지 않습니다. 카마이클 수(Carmichael number)라고 불리는 특수한 합성수(예: 561, 1105, 1729 등)는 서로소인 모든 밑 a에 대해 페르마의 소정리를 만족하기 때문에, 소수가 아님에도 불구하고 테스트를 통과할 수 있습니다. 따라서 더 높은 정확도가 필요하다면 반복 횟수를 늘리거나, 카마이클 수에도 강건한 밀러-라빈(Miller-Rabin) 소수성 테스트를 사용하는 것이 좋습니다.