如果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))
为了计算结果,三个参数
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
使用了更多的技巧,更通用,不需要递归李>下面是一些演示代码:
相关问题 更多 >
编程相关推荐