algorithm - 确定同余系统是否有解

Question

有一个线性同余系统，我想确定它是否有解。使用简单的算法来解决此类系统是不可能的，因为答案可能呈指数级增长。

我的一个假设是，如果同余系统没有解决方案，那么其中有两个是相互矛盾的。我不知道这是否成立，如果成立，那将导致一个简单的 O(n^2 log n) 算法，因为检查一对同余是否有解决方案需要 O(log n) 时间。尽管如此，对于这个问题，我宁愿看到更接近 O(n) 的问题。

我们可以假设没有模数超过 10^6，特别是我们可以快速将它们全部分解。我们甚至可以进一步假设所有模数的总和不超过 10^6(但它们的乘积仍然可能很大)。

Answer 1

如您所料，有一种相当简单的方法可以确定同余集是否有解，而无需实际构建该解。你需要:

1. 如有必要，将每个同余项简化为 x = a (mod n) 形式；从评论来看，您似乎已经有了这个。
2. 将每个模数 n 分解为质数幂的乘积:n = p1^e1 * p2^e2 * ... * pk^ek。
3. 将每个同余 x = a (mod n) 替换为一组同余 x = a (mod pi^ei)，每个 一个k 您在第 2 步中找到的素数幂。

现在，通过 Chinese Remainder Theorem独立检查每个素数的兼容性就足够了:给定任意两个同余 x = a (mod p^e) 和 x = b (mod p^f)，它们'当且仅当 a = b (mod p^(min(e, f)) 时才兼容。确定兼容性后，您可以在不丢失任何信息的情况下丢弃模数较小的同余。

使用正确的数据结构，您可以通过同余式一次性完成所有这些操作:对于遇到的每个素数 p，您需要跟踪最大的指数 e 到目前为止找到的，连同相应的右侧(为方便起见，减少模 p^e )。运行时间可能主要由模数分解决定，但如果没有模数超过 10^6，那么您也可以通过从范围 1 .. 10^6 到它的最小质因数。

---

编辑:因为这应该是一个编程站点，这里有一些(Python 3)代码来说明上面的内容。 (对于 Python 2，将 range 调用替换为 xrange 以提高效率。)

def prime_power_factorisation(n):
    """Brain-dead factorisation routine, for illustration purposes only."""
    # DO NOT USE FOR LARGE n!
    while n > 1:
        p, pe = next(d for d in range(2, n+1) if n % d == 0), 1
        while n % p == 0:
            n, pe = n // p, pe*p
        yield p, pe


def compatible(old_ppc, new_ppc):
    """Determine whether two prime power congruences (with the same
    prime) are compatible."""
    m, a = old_ppc
    n, b = new_ppc
    return (a - b) % min(m, n) == 0


def are_congruences_solvable(moduli, right_hand_sides):
    """Determine whether the given congruences have a common solution."""

    # prime_power_congruences is a dictionary mapping each prime encountered
    # so far to a pair (prime power modulus, right-hand side).

    prime_power_congruences = {}
    for m, a in zip(moduli, right_hand_sides):
        for p, pe in prime_power_factorisation(m):
            # new prime-power congruence: modulus, rhs
            new_ppc = pe, a % pe
            if p in prime_power_congruences:
                old_ppc = prime_power_congruences[p]
                if not compatible(new_ppc, old_ppc):
                    return False
                # Keep the one with bigger exponent.
                prime_power_congruences[p] = max(new_ppc, old_ppc)
            else:
                prime_power_congruences[p] = new_ppc
    # If we got this far, there are no incompatibilities, and
    # the congruences have a mutual solution.
    return True

最后一点:在上面，我们利用了模量很小的事实，因此计算素数功率因数分解并不是什么大问题。但是，如果您确实需要为更大的模数(数百或数千位)执行此操作，它仍然可行。您可以跳过因式分解步骤，而是找到模数集合的“互质基”:即成对相对质数正整数的集合，这样出现在您的同余中的每个模数都可以表示为乘积(可能有重复) 该集合的元素。现在按照上面的方法进行，但引用的是互质基而不是素数和素数的幂集。参见 this article Daniel Bernstein 提供了一种计算一组正整数的互质基数的有效方法。您最终可能会两次 遍历您的列表:一次计算互质基数，第二次检查一致性。