Итак, я недавно работал над реализацией теста примитивности Миллера-Рабина. Я ограничиваю его в объеме всех 32-битных чисел, потому что это проект для забавы, который я делаю, чтобы познакомиться с С++, и я не хочу работать с чем-либо 64-битным для какое-то время. Дополнительный бонус заключается в том, что алгоритм детерминирован для всех 32-битных чисел, поэтому я могу значительно повысить эффективность, потому что я точно знаю, какие свидетели должны тестировать.
Итак, для низких чисел алгоритм работает исключительно хорошо. Однако часть процесса зависит от модульного возведения в степень, то есть (num ^ pow)% mod. так, например,
3 ^ 2 % 5 =
9 % 5 =
4
вот код, который я использовал для этого модульного возведения в степень:
unsigned mod_pow(unsigned num, unsigned pow, unsigned mod)
{
unsigned test;
for(test = 1; pow; pow >>= 1)
{
if (pow & 1)
test = (test * num) % mod;
num = (num * num) % mod;
}
return test;
}
Как вы, возможно, уже догадались, проблемы возникают, когда аргументы являются исключительно большими числами. Например, если я хочу проверить число 673109 для простоты, мне нужно в какой-то момент найти:
(2 ^ 168277)% 673109
теперь 2 ^ 168277 является исключительно большим числом, и где-то в процессе он переполняет тест, что приводит к неправильной оценке.
на обратной стороне, такие аргументы, как
4000111222 ^ 3% 1608
также неверно оценивают по той же причине.
Есть ли у кого-нибудь предложения по модульной возведения в степень, которые могут предотвратить это переполнение и/или манипулировать им для получения правильного результата? (как я его вижу, переполнение - это еще одна форма модуляции, то есть num% (UINT_MAX + 1))