java - 代码中模乘的逆运算

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 和结果是动态。

我想创建一个公式，通过 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

如果，如 @ergonaut 答案的评论中所述，您只需要能够针对相对较少的原始值 x 和相对较小的 值来解决此问题mod，那么一种合理的做法是提前构建一个解码表:对每个可能的x进行前向计算，并将起始的x记录在一个数组，在结果上索引。然后，您可以执行简单的数组查找来获取每个结果的 x。对于足够长的值序列(即足够长的加密消息中的字符)中的每个值，这肯定会优于单独计算 x 。当然，如果您本着 Vignere 密码的精神(即使用多字节 key )来执行此操作，那么这将增加预先计算解码表所需的输入长度，从而获胜。

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

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