フェルマーの小定理をC++で実装する方法｜モジュラー逆元の求め方

フェルマーの小定理は、初等整数論における最も基本的な結果の一つであり、フェルマー素数判定法の理論的基礎となっています。この定理は、1640年に提唱したフランスの数学者ピエール・ド・フェルマーにちなんで名付けられました。

定理の内容は次のとおりです。p が素数であるとき、任意の整数 a に対して、a^p − a は必ず p の整数倍になるというものです。特に a が p で割り切れない場合は、a^p−1 ≡ 1 (mod p) が成り立ちます。

この性質を応用すると、m が素数であり、かつ a と m が互いに素である場合、a のモジュラー逆元（m を法とする乗法逆元）は a^m−2 mod m として効率的に計算できます。

アルゴリズム

開始
　　関数 power()：M を法として a の b 乗を計算する
　　関数 modInverse()：m を法とする a のモジュラー逆元を求める
　　　※ m は素数とする
　　　a と m が互いに素であれば、
　　　モジュラー逆元は a^(m - 2) mod m となる
終了

関数 pow() では「繰り返し二乗法（バイナリ法）」を採用しています。指数 b を半分ずつ減らしながら計算を進めることで、O(log b) の時間計算量で累乗を求められるため、大きな指数を持つ a^m−2 mod m も高速に処理できます。

サンプルコード（C++）

#include <iostream>
using namespace std;
int pow(int a, int b, int M) {
    int x = 1, y = a;
    while (b > 0) {
        if (b % 2 == 1) {
            x = (x * y);
            if (x > M)
                x %= M;
        }
        y = (y * y);
        if (y > M)
            y %= M;
        b /= 2;
    }
    return x;
}
int modInverse(int a, int m) {
    return pow(a, m - 2, m);
}
int main() {
    int a, m;
    cout<<"Enter number to find modular multiplicative inverse: ";
    cin>>a;
    cout<<"Enter Modular Value: ";
    cin>>m;
    cout<<modInverse(a, m)<<endl;
}

実行結果

Enter number to find modular multiplicative inverse: 26
Enter Modular Value: 7
3

この例では、26 の mod 7 におけるモジュラー逆元を求めています。26 × 3 = 78 となり、78 を 7 で割ると余りは 1 になるため、正しく 3 が出力されていることが確認できます。