Деление целых чисел — это долго и сложно. Вычислять остаток от деления — нисколько не проще. При этом в спортивном программировании, да и в прикладной математике типа криптографии, задача умножения чисел по модулю встречается повсеместно.
Один из вариантов эффективного решения — умножать по модулю, вообще при этом не используя операции деления, с помощью алгоритма Монтгомери.
Про него я и хотел бы поговорить.
Постановка задачи
Для простоты изложения, я буду приводить алгоритм для 32-битных целых чисел. Про более широкие числа тоже будут определённые заметки, просто без кода.