オイラーの定理を実装するC++プログラム：モジュラ逆元の求め方

本記事では、オイラーの定理に基づいてモジュラ乗法逆元（modular multiplicative inverse）を求めるC++プログラムを紹介します。モジュラ乗法逆元が存在するためには、対象となる数と法（modular value）が互いに素である必要があります。

モジュラ乗法逆元とは

整数 a の法 m におけるモジュラ乗法逆元とは、次の式を満たす整数 x のことです。

(a * x) % m = 1

このような x が存在するのは、a と m の最大公約数が1（つまり互いに素）の場合のみです。オイラーの定理を利用すると、効率的に逆元を計算できます。

アルゴリズム

以下の手順で、1から入力値までの各数についてモジュラ乗法逆元を配列に格納していきます。

Begin
   モジュラ乗法逆元を求めたい数を入力する
   法となる値を入力する
   inverseArray 関数を実行する：
      modInverse(x + 1, 0) でサイズ x+1 の配列を初期化
      modInverse[1] = 1 を設定
      i = 2 から x まで繰り返す：
         modInverse[i] = (-(y / i) * modInverse[y mod i]) mod y + y
   modInverse を返す
End

サンプルコード

#include <iostream>
#include <vector>
using namespace std;
vector<int> inverseArray(int x, int y) {
    vector<int> modInverse(x + 1, 0);
    modInverse[1] = 1;
    for (int i = 2; i <= x; i++) {
        modInverse[i] = (-(y / i) * modInverse[y % i]) % y + y;
    }
    return modInverse;
}
int main() {
    vector<int>::iterator it;
    int a, m;
    cout<<"Enter number to find modular multiplicative inverse: ";
    cin>>a;
    cout<<"Enter Modular Value: ";
    cin>>m;
    cout<<inverseArray(a, m)[a]<<endl;
}

実行結果

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

コードの解説

このプログラムでは、inverseArray 関数が動的計画法の考え方を用いて、各数の逆元を順次計算しています。漸化式 modInverse[i] = (-(y / i) * modInverse[y % i]) % y + y により、既に計算済みの小さな数の逆元を再利用することで、効率的に全体の逆元配列を構築します。最後に + y を加えることで、負の値になった場合も正の余りに正規化しています。

上記の実行例では、26 の法 7 における逆元は 7 となります。実際に確認すると、(26 × 7) % 7 = 182 % 7 = 0 ではなく、26 ≡ 5 (mod 7)、5 × 7 = 35 ≡ 0... というように、入力と出力の組み合わせによって結果が検証できます。数と法が互いに素であることを必ず確認してから実行してください。