作者triumphant10 (Look-three-small)
看板Prob_Solve
標題[問題] 餘數的演算法
時間Mon Apr 22 00:01:16 2019
嗨 大家好
我想問的是說
當 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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1555862480.A.8D6.html
1F：推 GYLin: 快速蜜 04/22 00:10
2F：→ GYLin: 冪 04/22 00:10
3F：→ LPH66: 所謂快速冪也就只是原 PO 的想法再進一步而已 04/22 00:58
4F：推 fatcat8127: 取模運算，如果模的是質數可以用費馬小定理降低次方 04/22 01:52
5F：→ fatcat8127: 數 04/22 01:52
6F：推 oToToT: 不用質數也有歐拉定理 04/23 22:59
7F：→ oToToT: 不互質也有某種擴展歐拉定理(不太確定學術名詞) 04/23 23:00
9F：推 GYLin: oT大大說的是歐拉對廢馬小定理的推廣 04/24 01:38
10F：推 rareone: 歐拉歐拉 10/11 18:29