大容量存储

Question

我正在尝试为一个学校项目实现RSA Key Generation algorithm。我在算法的加密阶段遇到了问题。它要求我提高用户输入的整数的随机数的幂(随机数有一个标准)，这些随机数通常是2或3位数的长度；例如。23^239 = d。在大多数情况下，'d‘值是100s的数字长度，我找不到任何东西来存储它。我已经尝试过long long，但是返回值总是为负值。

如何生成和存储非常大的数字？

Answer 1

RSA中的所有幂运算都是模幂运算。也就是说，您永远不会只计算23^239...取而代之的是，您将计算类似23^239 mod 11的内容。你可以计算指数，然后计算模数……但正如您所看到的，这需要表示一个相当大的数字的能力。相反，一个人同时执行这两个操作；这样效率更高，并且不需要太多存储空间。

有关详细信息和算法，请参阅https://en.wikipedia.org/wiki/Modular_exponentiation。

(请注意，通常情况下，您仍然需要一个用于RSA的bigint库，因为您将处理数百位长的数字，而不是2或3位长的数字。不过，这里的任务似乎是为了让您不必这么做而设计的。)