Big Integers in C#

What is the equivalent of bigint in C#?

That corresponds to the long (or Int64), a 64-bit integer.

Although if the number from the database happens to be small enough, and you accidentally use an Int32, etc., you'll be fine. But the Int64 will definitely hold it.

And the error you get if you use something smaller and the full size is needed? A stack overflow! Yay!

Big integers in C#

As of .NET 4.0 you can use the System.Numerics.BigInteger class. See documentation here: http://msdn.microsoft.com/en-us/library/system.numerics.biginteger(v=vs.110).aspx

Another alternative is the IntX class.

IntX is an arbitrary precision
integers library written in pure C#
2.0 with fast - O(N * log N) - multiplication/division algorithms
implementation. It provides all the
basic operations on integers like
addition, multiplication, comparing,
bitwise shifting etc.

Handling Big Integers in C#

If you're only looking at the last four digits, you don't need anything larger than an integer. Consider this:

When multiplying two numbers, if you are only interested in the least significant digits (i.e. the last four digits), then the upper-most digits will not have an effect on lowest digits of the outcome... so you can just "throw out" the most significant (right-side) digits before you multiply.

For example: I want to multiply two large numbers but I only need the last two digits:

int num1 = 123456789;
int num2 = 987654321;

int result = num1 * num2; // Last two digits would be "69" but this OVERFLOWS

but if we multiply only the last two digits...

int result = (num1 % 100) * (num2 % 100);  // result = 89 * 21

89 * 21 = 1869 (the last two digits are still "69" but we have not overflowed).

I used this technique to calculate the Six Right-Most Digits of 1,000,000 factorial.

How to compare big integers stored in int array?

OK, let's implement the comparisons; the typical way uses universal comparison (in some languages it's even has a special operator <=>)

  class HugeInteger {
    ...

    // Universal comparator
    //  +1 left > right
    //   0 left == right
    //  -1 left < right
    public static int Compare(HugeInteger left, HugeInteger right) {
      // first, we should deal with null's; let null be the leaset possible value

      // left and right are just the references of one inctance?
      if (Object.ReferenceEquals(left, right)) 
        return 0;
      else if (left == null)
        return -1;
      else if (right == null)
        return 1;

      // Now we checked for null, let's compare both arrays  

      //DONE: no 39, 40 or other magic numbers, but Length 
      for (int i = 0; i < left.array.Length; ++i)
        if (left.array[i] < right.array[i])
          return -1;
        else if (left.array[i] > right.array[i])
          return 1;

      return 0; // no differences found, so left equals to right
    }

Having comparator implemented it's very easy to write isLessThan, isGreaterThan:

    public bool isLessThan(HugeInteger other) {
      return Compare(this, other) < 0;
    }

    public bool isGreaterThan(HugeInteger other) {
      return Compare(this, other) > 0;
    }
    ....

How can I use bigint with C#?

You can use System.Numerics.BigInteger (add a reference to System.Numerics assembly). As mentioned in the comments this might not be the right approach though.

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

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.)

multiply very big integer in .NET

You need to use BigInteger.Parse.

BigInteger num = BigInteger.Parse("1253999939979969998746");

If you try to use an integer value like below

BigInteger num = 1253999939979969998746;

the right hand side needs to have a type, which by default will be an Int32 or a long. But since the number is too large to be an Int32 or a long, the conversion fails, hence the error you get.

As Tim Schmelter pointed out in a comment, to then do your multiplication, you can do the following:

BigInteger num = BigInteger.Multiply(BigInteger.Parse("1253999939979969998746"), 
                                     BigInteger.Parse("9999999999"));