RSA模重复平方算法实现示例代码
- 模重复平方算法
- 编码实现的两种思路：
2.1.先算高位再算低位
2.2.先算低位再算高位
本文参照《算法导论》做了些许尝试，发现matlab和C++都发生了超限情况。后无意中发现Python能够很好的处理244位的大数数的乘法，于是使用Python实现模重复平方算法，并给出一个小的例子。
"""模重复平方计算方法:算高位 """
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%mend_time=time.time()
total_time=end_time-start_timeprint('总时间为%.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_timeprint('总时间为%.3f' %total_time)
print('最终结果为%d' %a)
总时间为0.006
最终结果为597827521175301244475889063191856870100052394123770191590098011180384570125304731583699751371102528978113393699464822577528851786374198270141726642146665802894688261814615330540304839361320974730299148780013422574662587164800349707056407379
推荐阅读
- 集合的全排列（Java实现）
- 算法导论学习笔记——2.3.1分治法——习题2-4逆序对数
- 拓展欧几里得算法详解
- 算法导论程序15-计数排序（Python）
- 算法导论 — 8.3 基数排序
- 算法导论程序16--基数排序（Python）
- 算法导论 基数排序
- 【算法导论之四】计数排序
- 算法导论计数排序实现