why power function giving negative value?

Question

Currently I am implementing RSA algorithm. Following function is for power which we need in RSA.

private long power2(long x, long y, long n)
{
    long temp = 1;
    while (y > 0)
    {
        var z = y & 1;
        if (z == 1)
        {
            temp = ((temp % n) * (x % n)) % n;
        }

        x = ((x % n) * (x % n)) % n;

        y = y >> 1;
    }
    return temp;
}

Here n is 9 character long(start with 6). If I increase value of n(start with 9) then this function giving me negative value for some value of x and y. I don't know why this is happening. As long can contain value upto 9223372036854775807 and In my power function there is no way multiplication go beyond this value.

And what data type I have to use if I want to take n longer(10-15 character) then currently I am using. I tried Decimal and double but its has same problem as above(giving negative value).

Answer 1

This is happening due to the so-called overflow.

Here is an article explaining why does that happen.

You may want to use BigInteger struct instead from System.Numerics.