WolframAlpha如何如此快速地进行数字指数运算？

Question

我想知道RSA算法如何处理如此巨大的数字，在WolframAlpha上尝试了一个例子。他们如何处理这样疯狂的数字？

编辑：为了让它更加奇怪，再来一个例子

- good_evening

---

也许这篇文章可以帮助你。特别是关于实现问题的部分。 - Shashank

Answer 1

有一种简单的算法叫做指数平方算法（Exponentiation by Squaring），可以非常高效地计算 a^b mod c 的值。它基于这样一个观察结果:

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

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

有了这个规律，我们可以用以下递归方法来计算 a^b mod c：

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 次），速度非常快。您实际上从未计算过 a^b 并对 c 取模，这也使数字位数保持较低并且更快。

希望这能帮到您！

- templatetypedef