代码中模乘的逆运算

Question

我已经阅读了很多关于这个主题的文章，关于欧几里得算法，我在这里找到了这个主题所需的所有参考资料：

（我的问题的最佳来源）-> Math Explanation

另一个很好的例子 -> Math Explanation 2

维基 -> Extended Euclidean

增加价值的好答案 -> Add Operation

这是我完全失去它的地方 -> AFFINE CIPHERS

然而，在所有这些资源中，我仍然无法理解如何通过代码（或伪代码）实现它，或者至少找到编写它的方法。

所以我会写基础知识，假设我有这个公式：

(x * key) % mod = result
0 <= X <= mod
0 <= key <= mod
0 <= result<= mod

key和mod是常量。
*表示乘法运算
% 表示剩余操作（编辑澄清）
x 和 result 是 dynamic.

我想创建一个公式，通过 Java 中的代码给我 x。

对我来说计算结果的函数是：

private int MultModulus(int num, int key, int mod)
{
    return (num * key) % mod;
}

我怎样才能找到 X？我应该写什么来计算它？这是我不明白的地方，假设我的函数签名是：

private int InverseMultModulus(int result, int key, int mod)
{
    x = ...
    return x;
}

Answer 1

运行通过 MultModulus，但是用 [0, mod] 中的 X 迭代到 return 答案并将它们存储在数组中。

for (int i=0;i<mod;i++){
    if (MultModulus(i, key, mod) == result){
       // store answer in array
    }
}

return array;

Answer 2

如果，如@ergonaut 的回答的评论中所述，您需要能够仅针对相对较少的原始值 x 和相对较小的值 [=11= 来解决此问题]，那么一个合理的方法是提前构建一个解码 table：对每个可能的 x 执行正向计算，并将起始 x 记录在数组中，索引在 result。然后您可以执行简单的数组查找以获得每个结果的 x。对于足够长的值序列（即足够长的加密消息中的字符）中的每个值，这肯定会优于单独计算 x 。当然，如果您本着 Vignere 密码的精神这样做，即使用多字节密钥，那么这将乘以预计算解码所需的输入长度 table 是一个胜利。

但是请注意，使用您描述的函数来定义可行的密码取决于每个有效输入值都会产生不同的结果。然而，正如我们已经讨论过的，key 和 mod 的某些组合提供了重复的结果。此外，如果可能结果值的 space 与可能输入值的 space 大小相同，则您必须选择 key 和 mod 的组合，从而导致所有可能的 result 值都被使用，否则你无法避免重复。

如果你想把字节加密成字节，如果你想能够处理一般的文件，那么唯一可能的mod就是256。如果您选择较小的一个，则必须至少有一对映射到相同密码字节的输入字节。另一方面，如果您选择更大的 mod，则结果值的范围无法映射 1:1 到类型 byte 的范围。您还必须确保选择与 256 互质的 key，但这很容易：因为 256 是 2 的幂，所以任何奇数键都可以。只要选择了这样的key，任何256个连续整数范围内的两个输入值都不会映射到相同的结果。

代码中模乘的逆运算

The inverse of modular multiplication in code

java

multiplication

modulus

inverse