c - Wolfram Alpha 的指数怎么能这么快？

Question

我想知道 RSA 算法如何处理如此大的数字和 tried one example in WolframAlpha 。他们如何处理如此疯狂的数字？

编辑:只是为了让它更奇怪，one more example

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 修改它，这也使数字的数量保持较少并使其更快。

希望这对您有所帮助!