math - x^y mod z を計算するには?

Question

x^y mod z の計算方法を知りたいです。x と y は非常に大きく (64 ビット整数に収まりません)、z は 64 ビット整数に収まります。x^y mod z は (x mod z)^y mod z と同じです。

Answer 1

疑似コードでの標準的な方法は次のとおりです。

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
            e := e - 1
        else
            b := (b * b) % m
            e := e / 2
    return x

このアルゴリズムは、2 乗による累乗法または2 乗と乗算法として知られています。

Answer 2

Java を使用している場合は、x、y、および z を BigInteger に変換します。

BigInteger xBI = new BigInteger(x);
BigInteger yBI = new BigInteger(y);
BigInteger zBI = new BigInteger(z);
BigInteger answer = xBI.modPow(yBI,zBI);