RSA模重复平方算法小示例

2019-04-13 12:32发布

站内文章 / 模拟电子
10792 0 1363

RSA模重复平方算法实现示例代码

  1. 模重复平方算法
  2. 编码实现的两种思路：
    2.1.先算高位再算低位
    2.2.先算低位再算高位
    本文参照《算法导论》做了些许尝试，发现matlab和C++都发生了超限情况。后无意中发现Python能够很好的处理244位的大数数的乘法，于是使用Python实现模重复平方算法，并给出一个小的例子。

2.1. 先算高位

"""模重复平方计算方法:算高位 """ import time #算法解决的是a=b^n mod(n) #输入的三个参数 n=5611111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111; m=777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777; b=7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777; len(str(n)) #244位的大整数 #小整数测试用例 # n =560 # m =561 # b =7 start_time = time.time(); n_2 = bin(n) x=0 a=1 for i in range(2,len(n_2)): x = 2*x a = a*a%m if float(n_2[i]) == 1: x = x+1 a = a*b%m end_time=time.time() total_time=end_time-start_time print('总时间为%.3f' %total_time) print('最终结果为%d' %a) 总时间为0.003 最终结果为597827521175301244475889063191856870100052394123770191590098011180384570125304731583699751371102528978113393699464822577528851786374198270141726642146665802894688261814615330540304839361320974730299148780013422574662587164800349707056407379

2.2.先算低位

"""模重复平方计算方法:算低位 """ import time #算法解决的是a=b^n mod(n) #输入的三个参数 n=5611111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111; m=777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777; b=7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777; #小整数测试 # n =560 # m =561 # b =7 start_time = time.time(); #将大素数转化为二进制 n_2 = bin(n) x=1 y=0 a=1 #转化为二进制最高两位为0b for i in range(len(n_2)-1,1,-1): if float(n_2[i]) == 1: y = y+x a = a*b%m b = b*b%m x = 2*x end_time=time.time() total_time=end_time-start_time print('总时间为%.3f' %total_time) print('最终结果为%d' %a) 总时间为0.006 最终结果为597827521175301244475889063191856870100052394123770191590098011180384570125304731583699751371102528978113393699464822577528851786374198270141726642146665802894688261814615330540304839361320974730299148780013422574662587164800349707056407379

热门文章