c# – Data type overflow in the Farm primality test

Question:

Good afternoon. Implemented a probabilistic algorithm for determining the primality of a number based on Fermat's little theorem. However, there is a problem that the type, even with an 11-digit number, overflows. The question is how can this problem be elegantly solved without using BigInteger? The method itself

public static ulong IsPrimeNumb(ulong n, ulong a)
    {
        ulong e = 1, b=a;
        for (var i = n; i > 0;)
        {
            if (i % 2 == 1)
            {
                e = (e * b) % n;                    
            }

            b = (b * b) % n;
            i /= 2;
        }
        return e == a ? n : 0; 
    }

Answer:

e = (e * b) % n;
b = (b * b) % n;

The product of numbers when divided by some number gives the same remainder as the product of their remainders.

For example, let's calculate the remainder 107 * 207 modulo 4. The numbers 107 and 207, when divided by 4, give a remainder of 3, if you multiply these remainders, you get 9. And 9, when divided by 4, gives a remainder of 1, which means that 107 * 207 gives a remainder of 1.

e = ((e % n) * (b % n)) % n;
b = ((b % n) * (b % n)) % n;

Now there should be no overflow. As for data types, you can use decimal if you just don't have enough bits for the input values.