计算器中怎样计算一个数的n次方（快速计算一个数n次方mod）
在密码学中我们经常会看到 这样的计算(如RSA, Diffie Hellman key exchange), 而且往往这个n次幂很大. 如何快速对一个数的n 次方求mod, 很可能决定一个加密算法的性能. 下面我们会一步步引导大家来思考这个问题，我来为大家讲解一下关于计算器中怎样计算一个数的n次方?跟着小编一起来看一看吧!
计算器中怎样计算一个数的n次方
在密码学中我们经常会看到 这样的计算(如RSA, Diffie Hellman key exchange), 而且往往这个n次幂很大. 如何快速对一个数的n 次方求mod, 很可能决定一个加密算法的性能. 下面我们会一步步引导大家来思考这个问题
- 快速求
举例 如果要计算 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
后续博主可能会连续写一些关于密码学, 同态加密方面的文章 希望大家关注
,免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。文章投诉邮箱：anhduc.ph@yahoo.com
