嗨 大家好
我想問的是說
當 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
.
.
.
.
.
.

快速蜜冪

所謂快速冪也就只是原 PO 的想法再進一步而已

取模運算，如果模的是質數可以用費馬小定理降低次方數

不用質數也有歐拉定理不互質也有某種擴展歐拉定理(不太確定學術名詞)https://blog.sengxian.com/algorithms/mod-world

oT大大說的是歐拉對廢馬小定理的推廣

歐拉歐拉