[算法]快速指数模

2019-04-13 12:14发布

站内文章 / 模拟电子
10008 0 1285
之前在学习密码学的过程中接触了miller－rabin 的素性检测，要求对一个大数进行判断它是否是素数。在算法的过程中，需要计算a^b mod c的值。
如果直接进行 a^b 再 mod c 的话 ，即使 使用python忽略掉精度方面的限制，但是 依然因为长度太大会再电脑上跑上很久一段时间。

于是我们需要对这个操作进行算法上的优化。

方案1：
快速指数幂：

通过递归的形式计算出a^b mod c

代码大致如下：
        def compute_pow(a,b,c):
                if b == 1:
                        return a % c
                if b % 2 == 0 :
                        return (compute_pow(a,b,c)  ) ** 2 % c 
                if b mod 2 != 0 :
                         return (( compute_pow(a,b,c)  ) ** 2 % c * a % c )%c

但是这个函数在a，b较大时就 在terminal 停掉了。估计是因为 b过大导致爆栈了。

于是需要进行更多的优化。

方案2：
快速指数模
在搜索引擎的帮助下，我找到了一个更好的方法。使用一个数组来保存b的位数。用模拟的方法实现递归的算法。

方案3：
使用python的话，可以直接使用大招。pow(a,b,c)

thx all...
全篇代码：
def quick_mod(a,p,n): result = a % n remainders = [] while p != 1: remainders.append(p & 1) p = p >> 1 print(remainders) while remainders: rem = remainders.pop() result = ((a ** rem) * result ** 2) % n return result


 

热门文章