最初に

C++で書かれた、冪剰余コードです。

表記

冪剰余

情報

Wikipedia

C++コード

/**
* 冪剰余を返す。
* C ≡ b^e ( mod m)
*
* @param [in] b 基底
* @param [in] e 冪指数
* @param [in] m m を法とした b の e 冪剰余
* @return 冪剰余を返す。
*/
template<typename IntType>
IntType Modpow(IntType b, IntType e, IntType m) {

    IntType result = 1;

    while (e > 0) {
        if ((e & 1) == 1) result = (result * b) % m;
        e >>= 1;
        b = (b * b) % m;
    }

    return result;
}

オンライン実行