WolframAlpha如何快速取幂数字？

Question

我想知道RSA算法如何处理如此大的数字,并在WolframAlpha中尝试了一个例子.他们怎么能处理这些疯狂的数字呢？

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

Answer 1

有一种简单的算法称为取幂,通过平方可以非常有效地计算^b mod.这是基于观察结果

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

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

鉴于此,您可以使用此递归方法计算^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迭代相反),所以它很快就疯了.你实际上从来没有计算过^b然后用c修改它,这也使得数字保持较低并使其更快.

希望这可以帮助!