algorithm - 最小化中国余数定理中的余数

Question

我有多个包含多个同余项的集合。

我试图在应用 Chinese remainder theorem 时找到最小的余数每组中的一个项目。

例如有 2 组:

第 1 组:

7x + 1
7x + 3

第 2 组:

11x
11x + 2
11x + 7
11x + 8

7x + 1 & 11x 得到 77x + 22。
我追求的是最小余数(在上面的示例中为 77x + 8)，而不必测试所有组合。

---

这是我的实际问题的非常简化版本(约 50 组，每组约 100 个同余)。

我一直在研究如何解决这个问题，如果有任何建议，我们将不胜感激。

此外，如果我的数学术语不正确，我深表歉意。

Answer 1

有一种中间相遇算法，可以及时找到最小的残差

O(max(|S1|, |S2|) log(max(|S1|, |S2|))).

先用中国剩余定理求出S1中所有0 <= t < n1*n2满足t mod n1且t mod n2 == 0的集合T1和所有 0 <= u < n1*n2 的集合 T2 满足 S2 中的 t mod n1 == 0 和 t mod n2。

即在问题中给出的示例中:

T1 = {22, 66}

T2 = {0, 7, 35, 63}

现在您正在寻找的残差是总和 (t1 + t2) mod n1*n2，对于 T1 中的任何 t1 和 T2 中的 t2。因此，最小留数要么是 T1 和 T2 中两个最小元素的总和，要么是两个刚好大于 n1*n2 的元素。如果对集合 T1 和 T2 进行排序，则可以通过从最小元素到最大元素扫描第一个集合并从最大元素到最小元素扫描最大集合来找到第二种情况的最佳解决方案，即推进 T1 中的位置每当总和小于 n1*n2 时，当总和大于 n1*n2 时减少 T2 中的位置。

如果你有两个以上的模数 n1 .. nk 那么我能看到的最快的解决方案是将模数分成两组，比如 n1 .. nr 和 nr+1 .. nk 找到集合 T1 使得 t 在T1 iff t mod ni in Si 对于所有 1 <= i <= r 和 t mod ni == 0 对于所有 r < i <= k。相应地定义了 T2。复杂度取决于模数的分布，但通常应约为可能性数量的平方根。 Schroeppel和Shamir有一个算法，可以节省一些内存，但不会降低时间复杂度。

对于您的应用，即 50 个模数和 100 个同余，该算法仍然使用大约 100^25 个步骤，这是不可行的。不幸的是，看起来没有多项式算法。特别地，已知找到方程 x^2 == a (mod n) 的最小解 x，其中n 是一个高度复合的整数，是 NP 完全的。但是找到这样的解决方案可以减少你的问题。因此，您的问题通常也应该是 NP 完全问题，除非同余具有某些可以利用的特殊属性。