(java / math)如何在mod中找到商?

问题描述 投票:-2回答:3

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

我有A和B(把它作为客户端和服务器设置)。 A执行以下(2^10) mod 23 = 12

然后它将值12发送到B

现在,B有等式12 = (2^x) mod 23。 (它具有模数和基值)。我怎样才能找到10的值?我试过逆mod,但这似乎只适用于-1的幂。谷歌似乎也没什么帮助。只是数学帮助会很棒,但如果有一个Java函数,它会更好。

java math cryptography discrete-mathematics modulus
3个回答
0
投票

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

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

结果如下:

0 : 1
1 : 2
2 : 4
3 : 8
4 : 16
5 : 9
6 : 18
7 : 13
8 : 3
9 : 6
10 : 12
11 : 1
12 : 2
13 : 4
14 : 8
15 : 16
16 : 9
17 : 18
18 : 13
19 : 3
20 : 6
21 : 12
22 : 1
23 : 2
24 : 4
25 : 8
26 : 16
27 : 9
28 : 18
29 : 13
30 : 3
31 : 5
32 : 5
33 : 5

我切断了输出,但对于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次尝试中找到相应的值,否则您将永远找不到它。试图找到57的值将以无限循环结束。


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应该作为输入的唯一值。


1
投票

抱歉添加这个:

基本上由于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解释了数学解决方案问题。可能有帮助。

© www.soinside.com 2019 - 2024. All rights reserved.