C++で素数を法とする累乗の累乗（A^(B^C) mod M）を効率的に求める方法

この問題では、4つの値 A、B、C、M（Mは素数）が与えられ、「素数を法とする累乗の累乗」を求めることが課題となります。

具体的には、(A ^ (B ^ C)) (mod M) の値を計算する必要があります。

入力例と出力例

入力

A = 3, B = 6, C = 2, M = 11

出力

3

説明

(A ^ (B ^ C)) = (3 ^ (6 ^ 2)) = (3 ^ 36)(mod 11) = 3

解法アプローチ

単純なアプローチとその問題点

最も単純な解決策は、まず (B^C) の値を計算し、次に (A ^ (B ^ C)) を計算してからmodを取るという直接的な方法です。しかし、(B^C) は桁数が非常に大きくなる可能性があり、その値を格納すること自体が課題となり、計算過程でオーバーフローが発生する恐れがあります。

効率的なアプローチ：フェルマーの小定理

そこで、より効率的なアプローチとしてフェルマーの小定理（Fermat's Little Theorem）を利用する方法があります。

この定理は次のように表されます。

a^(m-1) ≡ 1 (mod M)　※mは素数

この定理を利用すると、問題の B^C を次の形式の数に変換できます。

x*(M-1) + y（与えられた M の値に対して）

フェルマーの小定理より、A^(x*(M-1)) の部分は 1 になります。これにより、計算は A^y の値を求めるだけに簡略化されます。

y の値は次のように求められます。

B^C = x*(M-1) + y

つまり、y は B^C を (M-1) で割ったときの余りです。

y = B^C % (M-1)

したがって、最終的に求めるべき式は次のようになり、計算が大幅に簡単になります。

(A ^ ((B^C) % (M-1))) % M

実装プログラム

以下は、この解法の動作を示すC++プログラムです。内部では繰り返し二乗法（バイナリ累乗）を使用することで、べき乗計算を O(log y) の時間計算量で効率的に行っています。

サンプルコード

#include<iostream>
using namespace std;

// x^y mod p を繰り返し二乗法で計算する関数
int calcPowerMod(int x, int y, int p) {
    int powMod = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            powMod = (powMod * x) % p;
        y /= 2; // y = y / 2
        x = (x * x) % p;
    }
    return powMod;
}

// (A^(B^C)) mod M を求める関数
int findPowerOfPowerMod(int A, int B, int C, int M) {
    return calcPowerMod(A, calcPowerMod(B, C, M-1), M);
}

int main() {
    int A = 3, B = 6, C = 2, M = 11;
    cout << "The power of power under modulo is " << findPowerOfPowerMod(A, B, C, M);
    return 0;
}

出力

The power of power under modulo is 3

まとめ

このように、フェルマーの小定理を活用することで、巨大な指数を持つべき乗のmod計算をオーバーフローを避けながら効率的に求めることができます。ポイントは以下の2点です。

• 指数部分 B^C を (M-1) で割った余りに置き換える
• べき乗計算には繰り返し二乗法を使用して高速化する