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

该算法称为平方求幂或平方乘法。

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);