math - 如何求 f(x)=(6x mod 13) 的反演？

Question

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

y = (6*x) mod 13

x = (6*y) mod 13

标签： mathdiscrete-mathematicsmodular-arithmetic

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 是一个未知的正整数，可以有任意值