Java中的计算不等于预期结果

Question

我试图在Java中实现RSA算法.

当你看一下这个页面:http://en.wikipedia.org/wiki/RSA_(algorithm)#A_working_example你可以看到这个计算:

c = 65 ^ 17 mod 3233 = 2790

当我使用这个Java代码时:

double valc = Math.pow(65, 17) % 3233;
System.out.println("Expected = 2790, computed = " + valc);

结果是:

Expected = 2790, computed = 887.0

我究竟做错了什么？

Answer 1

您假设浮点计算精确到一个疯狂的数字位数,它们不是.pow不是正确的计算方法65^17.你真的想做

65 * 65 * 65 ...

所以

result = 1;
for(ii = 0; ii < 17; ii++) result *= 65;

这将导致精度损失(它具有比内置类型可以表示的更多的数字).

看一下模数计算可以显着简化这些计算的方式.例如,参见https://math.stackexchange.com/questions/36318/modulo-arithmetic-with-big-numbers

它表明您可以执行以下操作:

result = 1;
for(ii = 0; ii < 17; ii++) {
  result *= 65;
  result = result % 3233;
}

有比这更有效的方法 - 但这会给你正确的结果.见http://jdoodle.com/a/2l