(java/math) 如何求 mod 中的商？

Question

这可能是一个相当简单的问题。我举个例子。

我有A和B（将其作为客户端和服务器设置）。 A 执行以下操作 (2^10) mod 23 = 12.

然后将值 12 发送到 B

现在，B 有等式 12 = (2^x) mod 23。（它有 modulus 和基值）。我如何找到值 10？我试过反 mod，但这似乎只适用于 -1 的幂。 Google 似乎也没什么用。只是数学帮助会很棒，但如果有一个 Java 函数，那就更好了。

Answer 1

我们可以用来解决这个问题的属性是A只能有23个唯一的输出。因此，您可以预先计算可能传递到 B 左侧的所有值，并记录获得这些值的输入，直到获得完整列表：

2^0 % 23 == 1
2^1 % 23 == 2
2^2 % 23 == 4
2^3 % 23 == 8
2^4 % 23 == 16
2^5 % 23 == 9
2^6 % 23 == 18
2^7 % 23 == 13
2^8 % 23 == 3
2^9 % 23 == 6
2^10 % 23 == 12
   .
   .
   .

你会发现在第 10 个输出之后，上面的值有一个重复序列，所以这些是 B 应该作为输入的唯一值。

Answer 2

您有时可以通过尝试第一个值并查看会发生什么来找到解决方案：

public static void main(String[] args) {
    for(int i = 0; i< 100; i++) {
        System.out.println("" + i +" : " + (int)Math.pow(2, i) % 23);
    }
}

这是结果：

我切断了输出，但是对于 33 之后的每个值，结果将是 5，因为有些溢出。

但是你可以看到结果中有一个循环：1 2 4 8 16 9 18 13 3 6 12。

这是因为这个数学关系而解释的：

(2^(n+1)) mod 23 = ((2 ^ n) mod 23) * 2 mod 23

（英文，将前面的结果乘以 2 并在必要时应用 mod 23）

所以

当n = 10时，结果为12
当 n = 11 时，结果是 12 * 2 mod 23 = 24 mod 23 = 1 然后你进入新的循环 1、2、4 等

因此答案是，要么在前 10 次尝试中找到相应的值，要么永远找不到。试图找到 5 或 7 的值将以无限循环结束。

Answer 3

抱歉添加：

基本上由于2^11 mod 23 = 1和(a * b) mod c = (a mod c) * (b mod c) mod c的某个循环之后，即mod multiplication rule.

所以我们绝对可以使用 loop 只用一个简单的列表来获得最终结果（无论 i 有多大）如：

 int getMod(int i) {
     int[] ret = new int {1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12};
     return ret[i % 11];
 }

OP，有一个tutorial很好地解释了数学解决程序问题。可能会有帮助。

(java/math) 如何求 mod 中的商？

(java/math) how to find quotient in mod?

java

math

cryptography

discrete-mathematics

modulus