大整数算术-如何实现模运算？

Question

我希望能够实现自己的（简单的）大型/任意精度整数计算，首先在Java中实现（因为我更熟悉语法），然后将其重写为C。

我已经完成了无限长度数字的加、减和乘法，现在需要进行密码学应用的模运算。

我将任意数字的位数存储在一个数组中，我遵循了以下指南来存储数字： 如何在不使用java.math.BigInteger的情况下处理Java中的非常大的数字？ 所以例如，我想要计算：

849465603662254214335539562 % 578907659710377778063722

当我有两个数组：

int[] a = [8, 4, 9, 4, 6, 5, 6, 0, 3, 6, 6, 2, 2, 5, 4, 2, 1, 4, 3, 3, 5, 5, 3, 9, 5, 6, 2]
int[] b = [5, 7, 8, 9, 0, 7, 6, 5, 9, 7, 1, 0, 3, 7, 7, 7, 7, 8, 0, 6, 3, 7, 2, 2]

代表这些数字。 有什么最简单的解决方案来获取。

int[] c = modFunction(a, b)

任何帮助都将不胜感激。

- luuksen

---

这是一个C++的解决方案：https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/modulus_hash.h - WaltK

Answer 1

计算D mod M时，你可以从D中减去M的任意整数倍而不改变结果。如果你用商的近似值D/M来减去，你会更接近所需的模数。重复此操作，直到商为0，就能得到答案。

while D >= M
  Q= some integer approximation of D / M
  D= D - Q.M

为了得到商的近似值，先取出 D 和 M 的前 K 位数字，并计算 Q=10^K.D/M 的整数部分。可以方便地使用双精度浮点数进行计算，得到 K 位数字（可使用最多 K=15）。在减法之前添加 len(D)-len(M)-K 个零以重新对齐。

注意，在截取 K 位数字后，由于除法使用了 D 和 M 的近似值（只有前 K 位数字），所以商可能会存在一些误差（我的猜测是最大误差为一个单位）。但这并不重要，因为只要从 M 的整数倍中减去即可使 D 保持准确值。只有最后需要检查 0<=D<M。

在给定示例中，849465603662254214335539562 mod 578907659710377778063722，近似商为 10^15.849465603662254 / 578907659710377 = 1467359412876373。，需要添加 -12 个零(!)以重新对齐，即将小数点向左移动，使用 1467。

然后，849465603662254214335539562 - 1467 * 578907659710377778063722 = 208066867130013916059388 就是所需的模数。

- user1196549

Answer 2

方法一

这是我想出来的方法，它不一定高效，但可以使用。

注意可以使用输入（以数字表示）的长度计算其对数。
您可以使用此方法执行除法，从而进行模运算。

具体来说，首先注意到：

849465603662254214335539562 / (578907659710377778063722 * 1000) = 1.4...

因此。

849465603662254214335539562 - 578907659710377778063722 * 1000 = 270557943951876436271817562

现在请注意。

270557943951876436271817562 / (578907659710377778063722 * 100) = 4.6...

因此

270557943951876436271817562 - (578907659710377778063722 * 400) = 38994880067725325046328762

现在请注意。

38994880067725325046328762 / (578907659710377778063722 * 10) = 6.7...

因此。

38994880067725325046328762 - (578907659710377778063722 * 60) = 4260420485102658362505442

最后，请注意：

4260420485102658362505442 / (578907659710377778063722 * 1) = 7.3...

因此

4260420485102658362505442 - (578907659710377778063722 * 7) = 208066867130013916059388

因此答案是 208066867130013916059388。

通过检查长度，可以轻松获得10的幂次，您可以尝试使用乘法来确定需要减去的倍数，并找出最高的非负结果。

方法2

只需使用乘法进行商的二进制搜索！然后使用商找到余数。

- user541686

---

那个第一种方法看起来非常有趣！我会尝试实现它。 - luuksen

@YvesDaoust：他怎么可能直接找到商呢？基本上这是在求解问题。 - user541686

@YvesDaoust：双精度浮点数仅适用于最多约308位数字，这在处理大数字时并不是很多。此外，它完全忽略了问题的要点。 - user541686

是的，有一个10^308的限制需要解决，通过重新规范化指数并保持自己的会计来解决。 - user1196549

我将此标记为答案，因为我尝试实现它并且似乎可以正确工作，而且对于我的需求来说非常简单和快速。如果有人需要超快速和优化的解决方案，请不要实现此方法或使用真正的库。 :) - luuksen

Answer 3

取模运算非常简单：

a % b = a - floor((a / b)) * b

你只需要整数除法（或 floor() 和除法）、乘法、减法。我想你已经有这些操作了。 如果您只有整数，则无需使用 floor() 函数：

a % b = a - (a / b) * b

例子：

849465603662254214335539562 % 578907659710377778063722 =
849465603662254214335539562 - (849465603662254214335539562  / 578907659710377778063722) *  578907659710377778063722 =
849465603662254214335539562 - 1467 * 578907659710377778063722 =
849465603662254214335539562 - 849257536795124200419480174 =
208066867130013916059388

- gaborsch

---

我还没有除法，但如果需要的话，我会考虑实现它。 - luuksen

除法和模运算就像孪生兄弟一样。如果你有其中一个，很快你就需要另一个。而且我认为实现一个简单的除法更容易。 - gaborsch

这个说法至少对于C来说是不正确的。如果你处理负数，比如-a mod b，你需要使用floor函数。整数除法会产生错误的结果，因为它会向零舍入。 - undefined

Answer 4

为什么你不想使用BigDecimal类呢？它有一个remainder方法，可以完全满足你的需求。你可以查看BigDecimal类的源代码来了解它是如何实现的。

- Bartosz Bilicki