The modulo operator (%) gives a different result for different .NET versions in C#

Question

I am encrypting the user's input for generating a string for password. But a line of code gives different results in different versions of the framework. Partial code with value of key pressed by user:

Key pressed: 1. Variable ascii is 49. Value of 'e' and 'n' after some calculation:

e = 103, 
n = 143,

Math.Pow(ascii, e) % n

Result of above code:

• In .NET 3.5 (C#)

  Math.Pow(ascii, e) % n
  

  gives 9.0.

• In .NET 4 (C#)

  Math.Pow(ascii, e) % n
  

  gives 77.0.

Math.Pow() gives the correct (same) result in both versions.

What is the cause, and is there a solution?

Answer 1

Math.Pow works on double-precision floating-point numbers; thus, you shouldn't expect more than the first 15–17 digits of the result to be accurate:

All floating-point numbers also have a limited number of significant digits, which also determines how accurately a floating-point value approximates a real number. A Double value has up to 15 decimal digits of precision, although a maximum of 17 digits is maintained internally.

However, modulo arithmetic requires all digits to be accurate. In your case, you are computing 49¹⁰³, whose result consists of 175 digits, making the modulo operation meaningless in both your answers.

To work out the correct value, you should use arbitrary-precision arithmetic, as provided by the BigInteger class (introduced in .NET 4.0).

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

Edit: As pointed out by Mark Peters in the comments below, you should use the BigInteger.ModPow method, which is intended specifically for this kind of operation:

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

Answer 2

Apart from the fact that your hashing function is not a very good one ^*, the biggest problem with your code is not that it returns a different number depending on the version of .NET, but that in both cases it returns an entirely meaningless number: the correct answer to the problem is

49¹⁰³ mod 143 = is 114. (link to Wolfram Alpha)

You can use this code to compute this answer:

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;
}

The reason why your computation produces a different result is that in order to produce an answer, you use an intermediate value that drops most of the significant digits of the 49¹⁰³ number: only the first 16 of its 175 digits are correct!

1230824813134842807283798520430636310264067713738977819859474030746648511411697029659004340261471771152928833391663821316264359104254030819694748088798262075483562075061997649

The remaining 159 digits are all wrong. The mod operation, however, seeks a result that requires every single digit to be correct, including the very last ones. Therefore, even the tiniest improvement to the precision of Math.Pow that may have been implemented in .NET 4, would result in a drastic difference of your calculation, which essentially produces an arbitrary result.

^* Since this question talks about raising integers to high powers in the context of password hashing, it may be a very good idea to read this answer_link before deciding if your current approach should be changed for a potentially better one.

Answer 3

What you see is rounding error in double. Math.Pow works with double and the difference is as below:

.NET 2.0 and 3.5 => var powerResult = Math.Pow(ascii, e); returns:

1.2308248131348429E+174

.NET 4.0 and 4.5 => var powerResult = Math.Pow(ascii, e); returns:

1.2308248131348427E+174

Notice the last digit before E and that is causing the difference in the result. It's not the modulus operator (%).

Answer 4

Floating-point precision can vary from machine to machine, and even on the same machine.

However, the .NET make a virtual machine for your apps... but there are changes from version to version.

Therefore you shouldn't rely on it to produce consistent results. For encryption, use the classes that the Framework provides rather than rolling your own.

Answer 5

There are a lot of answers about the way the code is bad. However, as to why the result is different…

Intel's FPUs use the 80-bit format internally to get more precision for intermediate results. So if a value is in the processor register it gets 80 bits, but when it is written to the stack it gets stored at 64 bits.

I expect that the newer version of .NET has a better optimizer in its Just in Time (JIT) compilation, so it is keeping a value in a register rather than writing it to the stack and then reading it back from the stack.

It may be that the JIT can now return a value in a register rather than on the stack. Or pass the value to the MOD function in a register.

See also Stack Overflow question What are the applications/benefits of an 80-bit extended precision data type?

Other processors, e.g. the ARM will give different results for this code.

Answer 6

Maybe it's best to calculate it yourself using only integer arithmetic. Something like:

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

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

You can compare the performance with the performance of the BigInteger solution posted in the other answers.