☰

计算机如何计算指数数学而不产生溢出错误？

tag-icon • tag-icon computer-architecture
计算机如何计算指数数学而不产生溢出错误？

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

需要此项来解密该消息在此处输入图片描述

总结果在此处输入图片描述如此之大，对于 64 位/32 位机器，我不相信它可以在一个寄存器中保存这么大的值。计算机如何在不溢出的情况下做到这一点？

这个问题本周超级用户问题。
阅读博客条目了解更多详情或为博客做贡献你自己

答案1

由于整数模运算是环同态（维基百科）从ℤ -> ℤ/nℤ，

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

你可以用一些简单的代数知识自己验证这一点。（请注意，mod右侧的最后一个数字是由于模环中乘法的定义而出现的。）

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

               / 1 我 = 0，
               |
(X^I) mod N = < (X * (X^(I-1) mod N)) mod NI 奇数，
               |
               \ (X^(I/2) mod N)^2 mod NI 偶数 & 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 16 -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 2 ) 时间。如果您查看上面的算法并将其分解，您会发现它与学校教授的“长乘法”相同。您没有记住 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 这样的数值库能够根据数字的大小选择不同的算法：傅里叶变换仅对最大数字最快，较小的数字使用更简单的算法。

答案2

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

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

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

假设一个整数只能保存 0-99 的值。如何表示数字 100？这乍一看似乎是不可能的，但那是因为我们只考虑一个变量。如果我有一个名为的整数units和一个名为的整数hundreds，我可以轻松表示 100：。hundreds = 1; units = 0;我可以轻松表示更大的数字，如 9223：。hundreds = 92; units = 23虽然

这是一种简单的方法，但有人可能会说它非常低效。与大多数突破计算机能力界限的算法一样，它通常是一场能力（表示大数字）和效率（快速检索/存储）之间的拉锯战。就像我之前说的，在计算机中表示大数字的方法有很多；只需找到一种方法并尝试一下！

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

进一步阅读：这文章和这这些信息可能会有用。

答案3

实现此操作的方法是（有更快的方法，包括重复平方等）乘以，每次乘法后取模数。只要模数平方小于 2^32（或 2^64），就不会溢出。

答案4

就加法和减法而言，许多 CPU 都有一个“进位位”，如果算术运算溢出，则设置该位。因此，如果结果需要 8 个字节来存储，并且 CPU 是 32 位（相当于 4 个 8 位字节），它可以执行两次加法运算，首先对“低位字”执行加法运算，然后对“高位字”执行加法运算，进位位负责处理溢出。必须先清除进位位。这是高位 CPU 提高性能的原因之一，因为不必做太多这样的操作。

当然，这是我使用 8 位 CPU 的有限汇编经验得出的结论。我不知道进位位在具有乘法和除法指令的现代 CPU 中是如何工作的。非英特尔 RISC CPU 的行为也可能不同。

我对浮点数数学不太了解，但基本上字节代表固定数量的位数，而不是特定位数。这就是为什么它被称为“浮点”。因此，例如，数字 34459234 占用的内存空间与 3.4459234 或 3.4459234E+20（即 3.4459234 x 10 ^ 20）大致相同。

相关内容