c - WolframAlpha 怎么能这么快地对数字求幂？

Question

我想知道 RSA 算法如何处理如此大的数字，并在 WolframAlpha 中尝试了一个示例。他们如何处理如此疯狂的数字？

编辑：只是为了让它更奇怪，再举一个例子

Answer 1

有一种简单的算法，称为平方求幂，可用于非常有效地计算 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 对其进行修改，这也可以保持低位数并使其更快。

希望这可以帮助！