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

Question

我想实现我自己的(简单)大/任意整数精度算术，首先用Java(因为我更熟悉语法)，然后将其重写为C。

我对无限长度的数字进行加法、减法和乘法，现在我需要对加密应用程序进行取模。

我将任意数字的数字存储在数组中，我遵循以下有关如何存储数字的指南: How to handle very large numbers in Java without using java.math.BigInteger

例如我想计算

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)

感谢任何帮助。

Answer 1

计算时D mod M ，您可以从 D 中减去M 的任意整数倍而不改变结果。如果用商 D/M 的近似值进行减法，您会更接近所需的模数。重复直到商 0会给你答案。

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

要获得这样的商近似值，请采用 K D 的最高有效数字和M并计算 Q=10^K.D/M 的整数部分。使用 double 算术可以方便地完成此操作，并为您提供 K数字(您最多可以使用 K=15 )。添加len(D)-len(M)-K在减法之前重新调整零。

请注意，K 之后的截断当您除以 D 的近似值时，数字可能会导致商出现小错误。和M (到第一个 K 数字)。 (我的猜测是Q上的最大误差是一个单位。)这个误差并不重要，因为只要减去M的整数倍即可。 , D仍然是一个精确值。只有最后你才需要检查 0<=D<M .

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

然后849465603662254214335539562 - 1467 * 578907659710377778063722 = 208066867130013916059388是请求的模数。