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

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

PS 我在哪里可以找到更多用于解决诸如此类的非平凡数学问题的算法？干杯!

score 7 · Accepted Answer

首先，您编写的算法根本没有优化，因为它在 s 中是线性的，而您可以轻松地编写日志，如您在此处阅读的那样。

也就是说，没有什么要解释的：你只需要知道

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

然后

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

紧接着你的算法以天真的方式计算结果。

score 4 · Accepted Answer

a ^s mod b = (a • a ^s-1 ) mod b = (a mod b) • (a ^s-1 mod b) mod b = ...

如您所见，第一步是微不足道的，而第二步是模的已知属性。所以你可以迭代并找到a ^s mod b。

正如其他人提到的，你可以做得更好。对于其他方法，您可以访问Wikipedia。但我将解释这个算法背后的想法：s用二进制表示数字，这样你就可以用s以下方式编写：

s=∑(2 ⁱ • b _i ) 其中每个 b _i为 0 或 1。

所以： a ^s mod b = a ^{∑(2 ⁱ • b _i )} mod b，所以你可以在 LSB = 1 时进行乘法运算，然后将指数右移 ...

2 回答 2