[問題] 餘數的演算法

[triumphant10 (Look-three-small)]

嗨 大家好

我想問的是說

當 k^n mod m (k,n,m皆為正整數)

n,m 非常大時

有什麼樣的方法可以更有效地計算出來?

我只有想到如下的方法

k mod m = r1

k^2 mod m = r1^2 mod m (假設r1^2超過m) = r2

k^4 mod m = r2^2 mod m
.
.
.
.
.
.





--

      當年我每回翻開課本，腦袋裡就先告訴自己

  這是戰場，我是來拼命的 !



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.17.184
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1555862480.A.8D6.html
推 GYLin: 快速蜜
→ GYLin: 冪
→ LPH66: 所謂快速冪也就只是原 PO 的想法再進一步而已
推 fatcat8127: 取模運算，如果模的是質數可以用費馬小定理降低次方
→ fatcat8127: 數
推 oToToT: 不用質數也有歐拉定理
→ oToToT: 不互質也有某種擴展歐拉定理(不太確定學術名詞)
→ oToToT: https://blog.sengxian.com/algorithms/mod-world
推 GYLin: oT大大說的是歐拉對廢馬小定理的推廣
推 rareone: 歐拉歐拉