Why am I getting a system overflow using big integer (System.Numerics)?

Question

I am getting this error: System.OverflowException: 'The value is not a number.' I was under the impression that big integer could store any sized value (500 ^ 500 in this case), so I don't understand why this is happening.

public int decode(int code)
{
   int totient = (p - 1) * (q - 1);
   int d = modInverse(e, totient);
   int pq = p * q;
   BigInteger decodedMessage = new BigInteger(Math.Pow(code, d) % pq);
   return (int)decodedMessage;
}

Answer 1

BigInteger decodedMessage = new BigInteger(Math.Pow(code, d) % pq);

Well, Math.Pow(code, d) % pq is not a BigInteger, it's an expression of type double. Converting the result to a BigInteger won't have an effect until the computation is complete (and has overflowed).

Math.Pow can easily overflow to Double.PositiveInfinity with large numbers, and Double.PositiveInfinity % someNumber yields Double.NaN. Calling new BigInteger(Double.NaN) yields the error you have described.

You need to do the computation in BigInteger. Fortunately, there's a method for exactly that purpose (BigInteger.ModPow):

BigInteger decodedMessage = BigInteger.ModPow(code, d, pq);

(BigInteger.ModPow requires BigInteger parameters, but there are implicit conversions from int to BigInteger.)

Answer 2

It seems that pq is 0, next throws the same exception:

new BigInteger(0.0 % 0);

Division of double by zero results in Double.NaN which is not a valid value to instantiate a BigInteger according to docs:

Exceptions

OverflowException

value is NaN, NegativeInfinity, or PositiveInfinity.

Or, as @Heinzi correctly mentioned in comments Math.Pow results in Infinity.