模运算符(%)为C#中的不同.N​​ET版本提供了不同的结果

Question

我正在加密用户的输入以生成密码字符串.但是一行代码在不同版本的框架中给出了不同的结果.用户按下的键值的部分代码:

按下键:1.变量ascii为49.经过一些计算后,'e'和'n'的值:

e = 103, 
n = 143,

Math.Pow(ascii, e) % n

上述代码的结果:

• 在.NET 3.5(C#)中

  Math.Pow(ascii, e) % n
  

  给9.0.

• 在.NET 4(C#)中

  Math.Pow(ascii, e) % n
  

  给77.0.

Math.Pow() 在两个版本中给出正确(相同)的结果.

原因是什么,是否有解决方案？

Answer 1

Math.Pow适用于双精度浮点数; 因此,您不应期望结果的前15-17位数更准确:

所有浮点数也具有有限数量的有效数字,这也决定了浮点值近似于实数的准确度.甲Double值具有高达15个精度十进制数字,尽管最大的17位在内部保持.

但是,模运算要求所有数字都是准确的.在你的情况下,你正在计算49 ¹⁰³,其结果由175个数字组成,使得模数运算在你的答案中都毫无意义.

要计算出正确的值,您应该使用由BigInteger类(.NET 4.0中引入)提供的任意精度算术.

int val = (int)(BigInteger.Pow(49, 103) % 143);   // gives 114

编辑:正如Mark Peters在下面的评论中指出的那样,您应该使用BigInteger.ModPow专门用于此类操作的方法:

int val = (int)BigInteger.ModPow(49, 103, 143);   // gives 114

Answer 2

除了你的散列函数不是很好^*之外,你的代码最大的问题并不是它根据.NET的版本返回不同的数字,但在这两种情况下它都会返回一个完全没有意义的数字:这个问题的正确答案是

49 ¹⁰³ mod 143 = 114.(链接到Wolfram Alpha)

您可以使用此代码计算此答案:

private static int PowMod(int a, int b, int mod) {
    if (b == 0) {
        return 1;
    }
    var tmp = PowMod(a, b/2, mod);
    tmp *= tmp;
    if (b%2 != 0) {
        tmp *= a;
    }
    return tmp%mod;
}

你的计算产生不同结果的原因是,为了产生答案,你使用一个中间值,它会丢弃49 ¹⁰³号码的大部分有效数字:只有175个数字中的前16个是正确的!

1230824813134842807283798520430636310264067713738977819859474030746648511411697029659004340261471771152928833391663821316264359104254030819694748088798262075483562075061997649

其余的159位数都是错误的.然而,mod操作寻求一个结果,要求每个数字都是正确的,包括最后一个数字.因此,即使是Math.Pow在.NET 4中实现的最精确的改进,也会导致计算的巨大差异,从而产生任意结果.

^*由于这个问题涉及在密码散列的情况下将整数提升为高权,因此在决定是否应针对可能更好的方法更改当前方法之前,阅读此答案_链接可能是一个非常好的主意.

Answer 3

你看到的是双倍舍入错误.Math.Pow使用double,差异如下:

.NET 2.0和3.5 => var powerResult = Math.Pow(ascii, e);返回:

1.2308248131348429E+174

.NET 4.0和4.5 => var powerResult = Math.Pow(ascii, e);返回:

1.2308248131348427E+174

注意之前的最后一位数字E,这会导致结果的差异.它不是模数运算符 (%).

Answer 4

浮点精度因机器而异,甚至在同一台机器上也不同.

但是,.NET为您的应用程序创建了一个虚拟机......但是从版本到版本都有变化.

因此,您不应该依赖它来产生一致的结果.对于加密,请使用Framework提供的类,而不是自己编写.

Answer 5

关于代码坏的方式有很多答案.但是,为什么结果不同......

英特尔的FPU在内部使用80位格式,以获得更高的中间结果精度.因此,如果一个值在处理器寄存器中,它将获得80位,但是当它被写入堆栈时,它将以64位存储.

我希望较新版本的.NET在其即时(JIT)编译中有一个更好的优化器,因此它将一个值保存在寄存器中,而不是将其写入堆栈然后从堆栈中读回.

可能JIT现在可以在寄存器中而不是在堆栈上返回值.或者将值传递给寄存器中的MOD函数.

另请参阅堆栈溢出问题80位扩展精度数据类型的应用程序/优点是什么？

其他处理器(例如ARM)将为此代码提供不同的结果.

Answer 6

也许最好只使用整数运算来计算它.就像是:

int n = 143;
int e = 103;
int result = 1;
int ascii = (int) 'a';

for (i = 0; i < e; ++i) 
    result = result * ascii % n;

您可以将性能与其他答案中发布的BigInteger解决方案的性能进行比较.