WolframAlpha如何如此快地取数字？

a^2k mod c = (a^k)² mod c

a^{2k + 1} mod c = a · (a^k)² mod c

鉴于此,您可以使用递归方法计算ab modc：

function raiseModPower(a,b,c):
    if b == 0 return 1
    let d = raiseModPower(a,floor(b/2),c)
    if b mod 2 = 1:
        return d * d * a mod c
    else
        return d * d mod c

这只有O(log b)乘法,其中每个都不能有比O(log c)更多的数字,所以它真的很快.这就是RSA实现如何将事情提升到权力.如果您愿意,可以将其重写为迭代,尽管我认为递归演示文稿真的很干净.

一旦有了这个算法,就可以使用标准技术来乘以任意精度数来进行计算.由于只需要O(log b)的乘法迭代(与b迭代相反),所以这是快速的.你从来没有真正结束计算ab,然后用c修改它,这也保持数字的数字低,并使其更快.

希望这可以帮助！