Переполнение типа данных в тесте Ферма на простоту

#c_sharp #алгоритм #простые_числа

Добрый день. Реализовал вероятностный алгоритм определение простоты числа на основе
малой теоремы Ферма. Однако, есть проблема, что тип при даже 11-значном числе, переполняется.
Вопрос как можно элегантно решить эту проблему не используя BigInteger? 
Сам метод

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

    

Ответы

Ответ 1

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



  Произведение чисел  при делении на некоторое число дает тот же
  остаток, что и произведение их остатков.
  
  Например, посчитаем остаток 107*207 по модулю 4. Числа 107 и 207 при
  делении на 4 дают  остаток 3, если перемножить эти остатки получится
  9. А 9 при делении на 4 дает остаток 1, значит,  и 107*207 дает остаток 1.


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


Теперь переполнения быть не должно.
Что касается типов данных, то можно использовать decimal, если тебе просто не хватает
разрядов для входных значений.