2

我有一组同余

x = a1 (mod n)
...
x = ak (mod nk)

我想找到x，这可以通过中国剩余定理和相关算法来解决：https ://en.wikipedia.org/wiki/Chinese_remainder_theorem

一些例子：https ://rosettacode.org/wiki/Chinese_remainder_theorem

对于这个特定的例子：

x = 1031 (mod 1473)
x = 1141 (mod 1234)
x = 50   (mod 1827)

我尝试过的所有算法都不起作用，因为模不是成对互质的。但是，1024360583是一个有效的解决方案：

1024360583 % 1473 == 1031
1024360583 % 1234 == 1141
1024360583 % 1827 == 50

什么算法可以找到这样的解决方案？

我还实现了密码学手册中的加纳算法：它没有解决那个例子。

4

1 回答 1

2

正如您所说，模数不是成对素数。您可以检查每一对（三个模数的三对），并且 GCD（最大公约数）大于 1 的唯一一对是1473和1827，GCD 为3。然后我们寻找除一个以上给定模数的所有素数。（有几种方法可以做到这一点。）我们发现它3是唯一除以一个以上模数的素数，并且除以一个以上模数的素数的最高幂是3**1 = 3（我使用 Python 和 Fortran 中使用的求幂符号为清楚起见，因为插入符号在计算机中也有其他用途。）

这可能会阻止您的方程组有任何解决方案。我们可以通过在方程中用它们的 GCD 替换这些模量来检查这一点，看看我们是否得到矛盾。

x = 1031 = 2 (mod 3)
x =   50 = 2 (mod 3)

结果方程是一致的，因此您的原始系统可能仍有解。（如果更高的幂3也除一个以上的模，我们也需要检查那些更高的幂。）对于我们发现的每个素数和每个模，我们找到除模的那个素数的最高幂。在我们的例子中，我们看到了3divides 1473but not3**2和 that 3**2divides 1827but not 3**3。所以我们的最高功率是3**2 = 9，我们看到该功率和更低功率的方程是一致的。

我们现在用新的方程替换两个相关方程，方法是将模数替换为最后一段中素数的最高幂之后的模数。这意味着1473用1473 / 3 = 491和1827替换1827 / 9 = 203。我们还为除一个以上模数的素数的每个幂添加了新的方程。所以现在我们有四个联立模方程：

x = 1031 (mod  491)
x = 1141 (mod 1234)
x =   50 (mod  203)
x =   50 (mod    9)  [from your original equation #1, 3]

我们可以减少其中一些方程的右手边，我们得到

x =   49 (mod  491)
x = 1141 (mod 1234)
x =   50 (mod  203)
x =    5 (mod    9)

该系统的解决方案也适用于您的原始系统。

我相信您可以将其转换为算法，然后将其转换为计算机代码。询问您是否有更多问题。

于 2018-04-28T22:59:16.183 回答