計算器中怎樣計算一個數的n次方?在密碼學中我們經常會看到 這樣的計算(如RSA, Diffie Hellman key exchange), 而且往往這個n次幂很大. 如何快速對一個數的n 次方求mod, 很可能決定一個加密算法的性能. 下面我們會一步步引導大家來思考這個問題，我來為大家講解一下關于計算器中怎樣計算一個數的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
後續博主可能會連續寫一些關于密碼學, 同态加密方面的文章 希望大家關注
,更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
