
快速指数算法
发布日期:2021-05-09 01:25:57
浏览次数:18
分类:精选文章
本文共 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
突然想起来,今天林老师课上说我们讲义上错误真的很多,但我相信以你们的能力都能纠正过来,呜呜呜,我哭辣,一下午就记住这一句话
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2025年05月15日 11时04分00秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Mac os 如何安装SVN
2023-02-06
Mac OS下错误The superclass “javax.servlet.http.HttpServlet“ was not found on the Java Build Path的解决方法
2023-02-06
Mac OS升级10 11以后cocoaPods不能使用的解决办法
2023-02-06
Mac os如何安装绿盾客户端
2023-02-06
mac os开发之简单动画
2023-02-06
mac php环境启动
2023-02-06
mac xmind 激活
2023-02-06
mac 下 android studio 的离线gradle极速配置方法
2023-02-06
Mac 下 Python+Selenium 自动上传西瓜视频
2023-02-06
mac 下 react Native ios环境搭建
2023-02-06
Mac 下使用sourcetree操作git教程
2023-02-06
mac 下如何建立vue-cli项目
2023-02-06
Mac 在命令行快速切换目录 mark
2023-02-06
mac 安装PIL
2023-02-06
Mac 开发PhoneGap 应用,怎样加入插件 barcodescaner
2023-02-06
mac 搭建APK反编译环境[转]
2023-02-06
Mac 效率工具必备神器 —— Alfred
2023-02-06