べき乗剰余アルゴリズムを実装するC++プログラム

この記事では、べき乗剰余（Modular Exponentiation、モジュラーべき乗）アルゴリズムを実装するC++プログラムを紹介します。べき乗剰余とは、(base^exp) % mod のような巨大な数の計算を効率的に求める手法で、暗号理論や競技プログラミングなど幅広い分野で活用されています。

アルゴリズムの考え方

単純に base を exp 回掛け合わせる方法では、計算量が O(exp) となり、指数が大きい場合は現実的ではありません。そこで「二進べき乗法（バイナリ法）」と呼ばれる手法を使用します。これは指数を2進数として捉え、底を繰り返し二乗しながら、指数の各ビットが1のときだけ結果に底を掛けることで、O(log exp) の時間で計算を完了させる効率的な方法です。

アルゴリズム

開始
    関数 modular():
    // 引数: base（底）、exp（指数）、mod（法）
    // 関数の処理内容:
        res = 1 として初期化
        while (exp > 0):
            if (exp を 2 で割った余り == 1):
                res = (res * base) % mod
            exp = exp を右に 1 ビットシフト
            base = (base * base) % mod
        res を返す
終了

サンプルコード

#include <iostream>
using namespace std;

long long modular(long long base, long long exp, int mod) {
    long long res = 1;
    while (exp > 0) {
        if (exp % 2 == 1)
            res = (res * base) % mod;
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return res;
}

int main() {
    long long b, e;
    int mod;
    cout << "底を入力してください: ";
    cin >> b;
    cout << "指数を入力してください: ";
    cin >> e;
    cout << "法の値を入力してください: ";
    cin >> mod;
    cout << modular(b, e, mod);
    return 0;
}

実行例

底を入力してください: 7
指数を入力してください: 6
法の値を入力してください: 26
25

出力結果の解説

上記の実行例では、7^6 mod 26 を計算しています。7^6 = 117,649 であり、117,649 ÷ 26 = 4,524 余り 25 となるため、プログラムは正しく 25 を出力します。

このアルゴリズムでは、ループのたびに底を二乗し、指数を右シフトによって半分にしていくため、指数が非常に大きい場合でも高速に動作します。また、各ステップで剰余を取ることで、中間値のオーバーフローを防いでいます。ただし、base と res の積が long long 型の範囲を超えないよう、法（mod）の大きさには十分注意が必要です。