三年级脱式计算格式（数学脱式计算格式）

投稿用户 • • 自媒体 • 阅读 659

在密码学中我们经常会看到 这样的计算(如RSA, Diffie Hellman key exchange), 而且往往这个n次幂很大. 如何快速对一个数的n 次方求mod, 很可能决定一个加密算法的性能. 下面我们会一步步引导大家来思考这个问题

  1. 快速求
举例 如果要计算 5^128 我们可以
1 5^2 
2 5^4
3 5^8
4 5^16
5 5^32
6 5^64
7 5^128
如果需要计算5^129 我们只需要 5^128 * 5

2 快速求

先来看一个定理 对左边式子做分解很容易得到右边的式子

有了上面的定理结合快速求幂的方法我们再来看

举例我们要计算2^512 mod 31

首先找到大于31的2整次幂 2^5
2^5 == 31 + 1
所以 2^512 可以改写 (31+1)^102 * 4  mod 31 == 1^102 * 4 mod 31  == 4

我们再看一个例子 3^480 mod 10
首先找到大于10 的3整次幂3^3
3^3 == 2*10 + 7
所以3^480 可以改写7^160 mod 10
同理 可以该写9^80 
同理可以该写1^40 == 1

后续博主可能会连续写一些关于密码学, 同态加密方面的文章 希望大家关注

本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 sumchina520@foxmail.com 举报，一经查实，本站将立刻删除。
如若转载，请注明出处：https://www.summeng.net/2635.html
赞 (0)
投稿用户
0
上一篇 2022年5月26日 pm1:08
下一篇 2022年5月26日 pm3:08

相关推荐