计算机如何计算指数数学而不会出现溢出错误？

Question

研究了一些 RSA 加密/解密方法，我发现了这篇文章：RSA 算法的一个例子

它需要这个来解密这个消息

总结果 太大了，对于64位/32位机器，我不相信它可以在一个寄存器中保存这么大的值。计算机如何做到不溢出？

---

这个问题是本周的超级用户问题。
阅读博客条目以了解更多详细信息或自己为博客做出贡献

Answer 1

因为整数模运算是一个环同态（维基百科）从 ? -> ?/n?,

(X * Y) mod N = (X mod N) * (Y mod N) mod N

您可以通过一些简单的代数来自己验证这一点。（请注意，mod由于模环中乘法的定义，出现了右侧的final 。）

计算机使用这个技巧来计算模环中的指数，而无需计算大量数字。

               / 1 I = 0,
               |
(X^I) mod N = < (X * (X^(I-1) mod N)) mod NI 奇数，
               |
               \ (X^(I/2) mod N)^2 mod NI even & I /= 0。

在算法形式中，

-- compute X^I mod N
function expmod(X, I, N)
    if I is zero
        return 1
    elif I is odd
        return (expmod(X, I-1, N) * X) mod N
    else
        Y <- expmod(X, I/2, N)
        return (Y*Y) mod N
    end if
end function

(855^2753) mod 3233如果您愿意，您可以使用它来仅使用 16 位寄存器进行计算。

但是，RSA 中 X 和 N 的值要大得多，太大而无法放入寄存器。模数通常为 1024-4096 位长！因此，您可以让计算机以“长”的方式进行乘法运算，就像我们手动进行乘法一样。计算机不会使用数字 0-9，而是使用“单词”0-2 ¹⁶ -1 或类似的东西。（仅使用 16 位意味着我们可以将两个 16 位数字相乘并获得完整的 32 位结果，而无需求助于汇编语言。在汇编语言中，通常很容易获得完整的 64 位结果，或者对于 64 位计算机，完整的 128 位结果。）

-- Multiply two bigints by each other
function mul(uint16 X[N], uint16 Y[N]):
    Z <- new array uint16[N*2]
    for I in 1..N
        -- C is the "carry"
        C <- 0
        -- Add Y[1..N] * X[I] to Z
        for J in 1..N
            T <- X[I] * Y[J] + C + Z[I + J - 1]
            Z[I + J - 1] <- T & 0xffff
            C <- T >> 16
        end
        -- Keep adding the "carry"
        for J in (I+N)..(N*2)
            T <- C + Z[J]
            Z[J] <- T & 0xffff
            C <- T >> 16
        end
    end
    return Z
end
-- footnote: I wrote this off the top of my head
-- so, who knows what kind of errors it might have

这将在大致等于 X 中的单词数乘以 Y 中的单词数的时间量内将 X 乘以 Y。这称为 O(N ² ) 时间。如果您查看上面的算法并将其拆开，就会发现他们在学校教授的“长乘法”相同。您没有记住 10 位数字的乘法表，但如果您坐下来计算，您仍然可以乘以 1,926,348 x 8,192,004。

长乘法：

    1,234
  x 5,678
---------
    9,872
   86,38
  740,4
6,170
---------
7,006,652

实际上有一些更快的乘法算法（维基百科），例如 Strassen 的快速傅立叶方法，以及一些更简单的方法，它们执行额外的加法和减法，但乘法较少，因此总体上速度更快。像 GMP 这样的数字库能够根据数字的大小选择不同的算法：傅立叶变换仅对最大的数字最快，较小的数字使用更简单的算法。

Answer 2

简单的答案是他们不能，而不是靠他们自己。实际上，如果您采用 x 位机的概念，那么可以由有限数量的位表示的数字数量是有限的，就像有限数量的数字可以由 2 位数字表示一样十进制系统。

话虽如此，非常大数字的计算机表示是密码学领域的一个重要组成部分。在计算机中表示非常大的数字的方法有很多种，每种方法都各不相同。

这些方法中的每一种都有不同的优点和缺点，虽然我没有/不能在这里列出所有方法，但我将介绍一个非常简单的方法。

假设一个整数只能保存 0-99 之间的值。一个人怎么能代表数字100？乍一看这似乎是不可能的，但那是因为我们只考虑一个变量。如果我有一个整数叫做units，一个叫做hundreds，我可以很容易地表示 100: hundreds = 1; units = 0;。我可以轻松地表示更大的数字，例如 9223: hundreds = 92; units = 23。

虽然这是一种简单的方法，但人们可能会争辩说它非常低效。像大多数推动计算机功能界限的算法一样，它通常是权力（代表大量）和效率（快速检索/存储）之间的拉锯战。就像我之前说的，在计算机中表示大数的方法有很多种；只需找到一种方法并进行实验即可！

我希望这回答了你的问题！

进一步阅读：这篇文章和这篇文章可能会派上用场以获取更多信息。