python 快速幂取模

2019-04-13 12:42发布

站内文章 / 模拟电子
17887 0 1196
在算幂的模的时候，比如2^64mod（10086），不必要算64次乘法，只需要首先算2^2 mod 10086,再算2^4在算2^8一般情况下，即将指数进行二进制分解，如果二进制不为0的位，则进行乘法运算，具体的算法如下def fastExpMod(b, e, m): result = 1 while e != 0: if (e&1) == 1: # ei = 1, then mul result = (result * b) % m e >>= 1 # b, b^2, b^4, b^8, ... , b^(2^n) b = (b*b) % m return result

热门文章