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

479

10 августа 2017, 21:09

Добрый день. Реализовал вероятностный алгоритм определение простоты числа на основе малой теоремы Ферма. Однако, есть проблема, что тип при даже 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; 
    }

Answer 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, если тебе просто не хватает разрядов для входных значений.