Итак, я недавно работал над реализацией теста простоты Миллера-Рабина. Я ограничиваю его набором всех 32-битных чисел, потому что это проект для развлечения, который я делаю, чтобы познакомиться с C ++, и я не хочу работать с чем-то 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 - это исключительно большое число, и где-то в процессе оно переполняет test, что приводит к неправильной оценке.
с обратной стороны, такие аргументы, как
4000111222 ^ 3 % 1608
также оценивают неправильно по той же причине.
Есть ли у кого-нибудь предложения по модульному возведению в степень, которые могут предотвратить это переполнение и / или манипулировать им для получения правильного результата? (как я вижу, переполнение - это просто еще одна форма по модулю, то есть num% (UINT_MAX + 1))