Блог

В моем c-коде я должен выполнить ряд рекурсивных модульных операций. В частности, я должен выполнять такие операции, как (A * B) MoDC, с C ~ 2 ^ 126 и A,B, которые, в принципе, могут быть очень большими числами (от 0 до 2 ^ 128 — 1) (я работаю со 128-битными unsigned __int128 переменными).
Проблема в том, как выполнить модуль во время процесса умножения. Мне это нужно, потому что, если модуль выполняется после умножения, я могу превысить 2 ^ 128 (если A и B очень большие) во время умножения и повредить последовательную модульную операцию.
Итак, я хотел бы выполнить умножение, которое перезапускается с 0 каждый раз, когда я передаю C (во время процесса умножения), а не каждый раз, когда я передаю 2 ^ 128 — 1.
Как мне это сделать?

Наивное решение состоит в том, чтобы реализовать умножение как цикл по битам, сдвигая на единицу и добавляя каждый раз. Таким образом, вы можете вычислять модуль промежуточного результата при каждом проходе через цикл.

Для этого требуется 128 сдвигов, 128 дополнений и 128 операций по модулю. Если это слишком медленно для вас, то какой-нибудь специалист, вероятно, может подсказать вам оптимизацию (но все знают, что вам следует рассматривать оптимизацию только после того, как вы уверены, что самое простое решение недостаточно быстрое).