嗨 大家好
我想问的是说
当 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大大说的是欧拉对废马小定理的推广

欧拉欧拉