algorithm - 求解 "xy + z ≡ 0 (mod k)"中的 x

Question

我需要求解同余关系中的 x

xy + z ≡ 0   (mod k)

其中 y、z 和 k 是已知的。 (k 可能不是质数。)

有没有比只测试从 0 到 k-1 的所有值更好的算法？

我尝试使用数论，得到了这个:

xy ≡ -z   (mod k)
x ≡ -z · (inverse(y)%k)   (mod k)

但在某些情况下我会得到错误的结果。例如，如果 k = 728、x = 272、y = 344 和 z = 344，则原始关系成立(因为 272 · 344 + 344 = 129 · 728)但最后一个关系不成立。我做错了什么？

Answer 1

您的解决方案失败是因为 当且仅当 y 和 k 互质(即，如果 gcd(y, k) = 1)时，“y modulo k”的乘法逆存在。在您选择的示例中 y 和 k 不是互质数
这是解决问题的另一种方法

xy + z ≡ 0 (mod k)
xy ≡ -z (mod k)
xy ≡ -z + k (mod k)
Let k - z = b
xy ≡ b (mod k)

现在您只需要求解线性同余方程即可。
解决你给定的例子看起来像

x * 344 + 344 ≡ 0 (mod 728)
x * 344 ≡ -344 (mod 728)
x * 344 ≡ -344 + 728 (mod k)
x * 344 ≡ 384 (mod 728)

首先通过减少到 x * 43 ≡ 48 (mod 91) 解决这个问题，然后使用扩展欧几里德算法将给出一般形式的解决方案作为

90 + 91 * t
Solutions for x less than 728 : 90, 181, 272, 363, 454, 545, 636, 727.

这样你就可以找到 x 的所有可能的解决方案。