如何找到 f(x)=(6x mod 13) 的反转？

Question

找到更简单的函数的反转很简单。我通过翻转方程中的 x 和 y 并求解 y 来找到这样做的方法。但是我卡在了某个部分。

y = (6*x) mod 13

x = (6*y) mod 13

Answer 1

该函数的反函数将只定义为 0 到 12 之间的值。此外，对于每个可能的 y（在 0 到 12 之间），将有无数个可能的 x 满足等式。

让我们尝试求解 y

x = (6*y) mod 13
x + n*13 = (6*y)
y = (x + n*13)/6 | x ∈ {0,…,12}, n ∈ ℕ

其中 n 是一个未知的正整数，可以是任意值

Answer 2

为了计算 y = 6 * x mod 13 的倒数，我首先要求解 x 并稍后用 y 替换 x（反之亦然）。

因为 y = 6 * x mod 13、x = 6^(-1) * y mod 13，其中 6^(-1) 是 6 的 modular multiplicative inverse 的模数 13。您的任务现在变成寻找 6^(-1) mod 13。换句话说，您必须找到 m 使得 6 * m = 1 mod 13.

注意6 * 2 = 12 = -1 mod 13。两边均方，6 * 6 * 2 * 2 = 1 mod 13，或6 * 24 = 1 mod 13。由于 24 = 11 mod 13，因此 6 * 11 = 1 mod 13 和 11 = 6^(-1) mod 13.

因此，我们 x 的等式现在变成了 x = 11 * y mod 13。替换 y -> x 和 x -> y，给定函数的反函数由 y = 11 * x mod 13.

给出

这个漂亮的 Python 脚本可以用来测试我们结果的有效性：

def f(x):
    return (6 * x) % 13

def f_inv(x):
    return (11 * x) % 13

for x in range(13):
    print x, f_inv(f(x)), x == f_inv(f(x))

当运行时，输出如下：

0 0 True
1 1 True
2 2 True
3 3 True
4 4 True
5 5 True
6 6 True
7 7 True
8 8 True
9 9 True
10 10 True
11 11 True
12 12 True

从而验证前提f^(-1)(x) = 11 * x mod 13满足要求的前提f^(-1)(f(x)) = x.

如何找到 f(x)=(6x mod 13) 的反转？

How to find the inversion of f(x)=(6x mod 13)?

math

discrete-mathematics

modular-arithmetic