有没有办法在 y = (k1 + k2 × x) mod (s) 中指定 X？

Question

我正在用 c# 编写程序，它需要找到 X，其中 k2 和 s 的最大公约数为 1，x 小于 s 并且 k1、k2、y、s 是常量。现在，我正在通过测试 X 的每个值并检查它们是否正确来完成此操作，但是当我有 40000 多个值时，这是非常耗时的。或者，如果这对您来说更容易，您可以尝试从 y=x mod(s) 指定 X。

我现在正在使用代码来解决它：

if (GCD(k2, k) == 1)
        {
            for (int i = 0; i < k; i++)
            {
                n1 = 0;
                n = 0;
                while(n < 1)
                {
                    if(i == (k1 + k2 * n1) % k){
                        s1[n1] = s[i];
                        n++;
                    }
                    n1++;
                }
            }
        }

提前致谢。

P.S。如果有什么不清楚的地方，请告诉我，我很难解释这一切 :P

Answer 1

让我们来看一个示例问题：

Solve for X:
17395 = (100 + 43 * X ) % 633424

从消除加法开始：

17395 - 100 = (43 * X) % 633424
17294 = (43 * X) % 633424

现在，假设存在一个数 Y 使得

1 = ( Y * 43 ) % 633424

（旁白：我们怎么知道 Y 存在？它存在当且仅当 43 和 633424 是互质的，它们是互质的。这是 Bézout 恒等式的一个特例。）

Y 是 43 关于 633424 的 乘法逆元 。

这有什么帮助？我们可以将两边都乘以 17294:

17294 = ( Y * 43 * 17294 ) % 633424

现在我们可以读出我们的解决方案：X 是 Y * 17294。

因此问题简化为计算乘法逆元。你能看出如何找到满足 1 = ( Y * 43 ) % 633424 的数字 Y 吗？如果你能找到那个数字，那么你就能找到 X。

您可以使用欧几里得算法快速找到乘法逆元。参见 https://en.wikipedia.org/wiki/Modular_multiplicative_inverse or my page on the subject https://ericlippert.com/2013/11/12/math-from-scratch-part-thirteen-multiplicative-inverses/

有没有办法在 y = (k1 + k2 × x) mod (s) 中指定 X？

Is there a way to designate X in y = (k1 + k2 × x) mod (s)?

c#

math

modulo