python - 如何计算 2 的一个大数对另一个大数的幂？

Question

M = 115792089237316195423570985008687907853269984665640564039457584007908834671663

2^{96514807760119017459957299373576180339312098253841362800539826362414936958669} % M = ?

可以用Python计算这个吗？或者还有其他方法吗？

Answer 1

为了计算结果，三参数 pow 可以有效地完成此操作，正如 @MarkDickinson 在评论中提到的。

对其工作原理的简化解释:

• 要计算2**N mod M，首先找到K = 2**(N//2) mod M
• 如果 N 为偶数，2**N mod M = K * K mod M
• 如果 N 为奇数，2**N mod M = K * K * 2 mod M这样，就不需要计算巨大的数字。实际上，pow 使用了更多技巧，更通用，并且不需要递归。

这里是一些演示代码:

def pow_mod(B, E, M):
    if E == 0:
        return 1
    elif E == 1:
        return B % M
    else:
        root = pow_mod(B, E // 2, M)
        if E % 2 == 0:
            return (root * root) % M
        else:
            return (root * root * B) % M

M = 115792089237316195423570985008687907853269984665640564039457584007908834671663
E = 96514807760119017459957299373576180339312098253841362800539826362414936958669

print(pow_mod(2, E, M))
print(pow(2, E, M))