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

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

Scroll to Top