C++で学ぶフェルマー素数判定テスト：アルゴリズムと実装コード

フェルマー素数判定テスト（Fermat Primality Test）は、与えられた整数が素数かどうかを確率的に判定するための古典的な手法です。本記事では、このアルゴリズムの仕組みと、C++による実装コードをわかりやすく解説します。

フェルマーの小定理の基本

フェルマー素数判定は「フェルマーの小定理」に基づいています。p を素数、a を p の倍数でない任意の整数とすると、次の関係が常に成り立ちます。

a^p−1 ≡ 1 (mod p)

この性質を利用し、判定したい数 n に対してランダムな底 a を選び、aⁿ⁻¹ mod n が 1 と一致するかを確認します。一致しなければ n は確実に合成数です。一方、一致した場合でも n が素数である保証はありません（カーマイケル数のような擬素数が存在するため）が、試行回数を重ねることで誤判定の確率は大幅に低下します。

アルゴリズム

まず、繰り返し二乗法により高速に剰余べき乗を計算する modulo 関数の処理の流れです。

関数 modulo(base, e, mod)
　a = 1
　b = base
　e > 0 の間繰り返し：
　　e が奇数の場合　a = (a × b) % mod
　　b = (b × b) % mod
　　e = e ÷ 2
　a % mod を返す

続いて、フェルマーテスト本体の手順です。

関数 Fermat(m, iterations)
　m が 1 なら false を返す
　iterations 回繰り返し：
　　x = rand() % (m − 1) + 1（1 以上 m−1 以下の乱数）
　　modulo(x, m − 1, m) の結果が 1 以外なら false を返す
　true を返す

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 は素数です

まとめ

フェルマー素数判定テストは、乱数を活用したシンプルな確率的素数判定手法です。厳密な判定にはミラー・ラビン法などより強力なテストが推奨されますが、実装が容易で大きな数にも高速に対応できる点が大きな魅力です。暗号技術のように巨大な素数を扱う場面では、候補を素早く絞り込む前段処理として広く活用されています。