algorithm - 查找 find a^s mod b

Question

我们有 3 个数字:a、s 和 b，每个数字都在 1 到 1000000 之间变化。我们需要找到 pow(a,s)%b。显然，我们不能使用简单的 pow 函数，因为我们无法生成大数字，例如 1000000^1000000。这是问题的解决方案:

sol=1
for(int i=0;i<s;i++) 
{
            sol = sol * a;
            sol = sol % b;
}

print sol

我不明白这个算法。有人可以向我解释吗？

附言我在哪里可以找到更多算法来解决像这个这样的非平凡数学问题？干杯!

Answer 1

首先，您编写的算法根本没有优化，因为它在 s 中是线性的，而您可以轻松地编写一个 log(s) 算法，正如您可以阅读 here .

也就是说，没有太多需要解释的:你只需要知道这一点

a*b mod N = ((a mod N) * ( b mod N)) mod N

还有那个

a^s = a*a*...*a s times

紧随其后的是您的算法以朴素的方式计算结果。