math - 我们如何计算具有大除数和指数的模运算？

Question

例子：

(30000000^30000000) mod 40000000 = ?

我一直在使用欧拉理论和指数性质，但仍然无法得到答案有人知道如何仅通过理论和简单的计算器来计算吗？

我的尝试是通过费马小定理减少 30000000 的指数，但指数仍然太大，计算器无法计算。

Answer 1

# b^e (mod m)
function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := floor(e / 2)
    return x

Answer 2

您使用减半和平方方法来计算功率，并在每一步中以给定的除数为模来减少中间结果。

您还可以使用负余数来获得更小的中间结果。

还要注意 n=40000000=4*10^7=2^9*5^7 是一个合数，所以欧拉函数给出 phi(n)=2^8*4*5^6=16*10^ 5=160000。现在首先减少指数 mod phi(n)-1。

仅当您知道除数的因式分解时，最后一种方法才有效。