
快速指数算法
发布日期:2021-05-09 01:25:57
浏览次数:14
分类:博客文章
本文共 877 字,大约阅读时间需要 2 分钟。
出问题了,程序好像错了,这两天考试,考完试改
问题简介
在RSA中,加、解密过程都是要求某个整数的整数次幂后再取模。大多时候,这两个整数都会比较大,这时候直接按含义来进行计算时得到的中间结果会超出计算机所允许的整数取值范围(例如计算\(66^{77}\),这还是比较小的);另一方面,我们也要考虑计算的效率,如\(66^{77}\)直接按照定义计算的话需要做76次乘法,开销是相当大的。针对这两个问题,我们就需要有一个好的算法来高效且准确地计算大整数的幂运算。
初步思路
针对第一个问题,即数值过大问题,可以考虑利用模运算的性质:
\[(a*b)(mod n) = [(a (mod n))*(b (mod n))](mod n)\]
就能有效减小中间值。
针对第二个问题,可以利用指数的性质,对每个部分的结果重复做平方运算,最低可以将运算次数减为\(log_2n\),如计算\(x^{16}\)时,可以按照如下方式进行: \[x^2,x^4,x^8,x^{16}\]
只需要计算4次,比按照定义计算减少了3/4。
快速指数算法
快速指数算法整合了上面两种思想,算法描述如下:
通常,在我们计算\(a^mmodn\)时,先将m表示为二进制形式\(b_k,b_{k-1},...,b_0\),即
\[m = \sum\limits_{b_i=1}2^i\]
因此,
\[a^m = a^{\sum\limits_{b_i=1}2^i} = \prod\limits_{b_i=1}a^{2^i}\]
\[a^mmodn = [\prod\limits_{b_i=1}a^{2^i}]modn = \prod\limits_{b_i=1}[a^{2^i}modn]\]
代码简略实现:
d = 1for i in range(k+1): d = d*d%n if b[i] == '1': d = d*a%n
突然想起来,今天林老师课上说我们讲义上错误真的很多,但我相信以你们的能力都能纠正过来,呜呜呜,我哭辣,一下午就记住这一句话
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2025年04月23日 00时18分29秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
OpenStack 最小化安装配置(一):物理机网桥配置
2019-03-15
PS快速美白照片
2019-03-15
ubuntu 16.04 镜像下载
2019-03-15
CUDA9.1、cuDNN7在Ubuntu16.04上的安装
2019-03-15
微信小程序云开发:怎么删除云函数?已解决
2019-03-15
什么是句柄(经典)
2019-03-15
第一次被黑
2019-03-15
PyCharm配置anaconda环境
2019-03-15
修改linux 系统自带日志系统systemd-journald && 参数
2019-03-15
Redis工具类
2019-03-15
SpringBoot与缓存(JSR-107、Spring缓存抽象)
2019-03-15
ERROR 总结
2019-03-15
C语言—— 符号函数
2019-03-15
钞票最优解
2019-03-15
查找最小值栈的O(1)
2019-03-15
淘宝天猫双十一养猫组队怎么踢人
2019-03-15
Java面试题整理,闭关在家37天“吃透”这份345页PDF,纯干货
2019-03-15