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



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

我有AB(将其作为客户端和服务器设置(A执行以下操作CCD_ 1。

然后将值12发送到B

现在,B具有方程12 = (2^x) mod 23。(它有模量和基本值(。如何找到值10?我尝试了反向mod,但这似乎只适用于-1的幂。谷歌似乎也帮不了什么忙。仅仅是数学上的帮助就很好了,但如果有一个Java函数,那就更好了。

我们可以用来解决这个问题的属性是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应该作为输入的唯一值。

很抱歉添加以下内容:

基本上在由于2^11 mod 23 = 1(a * b) mod c = (a mod c) * (b mod c) mod c的某个循环之后,这是模乘法规则。

因此,我们可以肯定地使用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,有一个教程很好地解释了数学解决程序问题。也许会有帮助。

您有时可以通过尝试第一个值来找到解决方案,然后看看会发生什么:

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
  • (2^10) mod 23 = 120时,结果是12*2 mod 23=24 mod 23=1,然后进行新的循环1、2、4等

因此,答案是,除非你在前10次尝试中找到相应的值,否则你永远找不到。尝试查找57的值将以无限循环结束。

最新更新