作者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/cn.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