Re: [其他] Modular Exponentiation運算的原理
有人把這個叫做反覆平方法...
現在我們要求 a^b mod c
若 b 是偶數, 那 a^b ≡ [ a^(b/2) ]^2 (mod c)
若 b 是奇數, 那 a^b ≡ [ a^((b-1)/2) ]^2 ×a (mod c)
然後有 a^0 ≡ 1 (mod c)
所以可以寫成程式(assume Mod > 1)：
function fast_exp_mod(base, exponent, Mod)
1 if exponent＝0 then
2 return 1
3 tmp ← fast_exp_mod(base, [exponent / 2], Mod)
4 tmp ← tmp ×tmp mod Mod
5 if exponent is odd number then
6 tmp ← tmp ×base mod Mod
7 return tmp
其時間複雜度為 O(lb exponent), []代表取floor
把這個程式改成非遞迴形式, 應該就是你在書上看到的寫法了
※ 引述《vity (逍遙盃-佛得)》之銘言：
: 大家好
: 我知道想計算 b^n mod m時
: 會先把 n用2進位表示
: 但是接下來的步驟就看不懂
: 例如3^644 mod 645
: 先把644用成 1010000100
: 但接著就只是照書上的演算法做, 不懂原理
: 似乎是看不懂這個, 讓我搞不懂RSA公開金鑰加密系統的原理, 只會計算
: 是這樣嗎...
: 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.32.112
※ 編輯: suhorng 來自: 61.217.32.112 (09/18 19:42)
推
09/18 19:45, , 1F
09/18 19:45, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：