Умножение Монтгомери на ПК с модулями размером в слово. Стоит ли оно того?

Я пишу код на C для исследовательского проекта по теории чисел, который требует выполнения множества операций модульной арифметики с множеством разных модулей. Проще говоря: мне нужно выполнить операцию (a * b) % n много-много раз.

Код предназначен для работы на ПК с 64-битными словами, и известно, что все модули меньше 2^64, поэтому все операнды реализованы беззнаковыми 64-битными целыми числами.

Мой вопрос: приведет ли использование модулярного умножения Монтгомери (использующего только сложение и умножение) вместо оператора по модулю C % (который преобразуется в a % n = a - n*(a / n) и также использует деление) к более быстрому выполнению?

Интуитивно я бы сказал, что ответ таков: нет, потому что деление (размером слова) на ПК не слишком затратно в вычислительном отношении, чем умножение (размером слова), а сокращение Монтгомери на самом деле вызовет накладные расходы.

Спасибо за любые предложения.

Обновление: с одной стороны, по словам Пола Огилви (см. его комментарий ниже), (a * b) % n требует 1 умножения и 1 деления. С другой стороны, умножение Монтгомери требует (игнорируя операции, необходимые для преобразования и обратного преобразования операндов в их представления Монтгомери, поскольку они выполняются один раз только для каждого модуля n; и двоичные сдвиги) 3 умножения. Таким образом, кажется, что Монтгомери быстрее, чем ``%'', поскольку умножение выполняется в два раза быстрее, чем деление...


c word modular-arithmetic
person Norian    schedule 20.01.2020    source источник
comment
Операция по модулю реализована на большинстве ЦП в виде инструкции. Я ожидаю, что это будет быстрее, чем последовательность инструкций. (Обратите внимание, что на уровне микрокода ЦП это может быть последовательность операций. Единственный способ быть абсолютно уверенным - это просмотреть данные синхронизации ЦП).   -  person Paul Ogilvie    schedule 20.01.2020
comment
На самом деле модуль реализован как инструкция DIV, в которой частное помещается в один регистр, а остаток — в другой.   -  person Paul Ogilvie    schedule 20.01.2020
comment
Насколько я понимаю, умножение Монтгомери часто используется из-за его операций с постоянным временем (которые важны в криптографических приложениях), а не из-за производительности. Однако, насколько я знаю, производительность выше, чем у других методов с постоянным временем, поэтому вы можете увидеть умножение Монтгомери, упомянутое для его производительности.   -  person Morten Jensen    schedule 20.01.2020
comment
Я не смог найти время выполнения инструкций в Intel 64-ia-32-architectures-software-developer-manual-325462   -  person Paul Ogilvie    schedule 20.01.2020
comment
@PaulOgilvie: время выполнения инструкций не относится к руководству по архитектуре, потому что в руководстве по архитектуре указан набор инструкций — какие функции выполняют инструкции. Насколько они быстры, зависит от реализации, которая варьируется от модели процессора к модели процессора. Сроки выполнения инструкций указаны в руководствах по процессору.   -  person Eric Postpischil    schedule 20.01.2020
comment
ОП: У меня нет особого опыта, но я видел, как умножение Карацубы рекламировалось как средство повышения производительности при работе с большими целыми числами. Насколько я понимаю, точка безубыточности может быть немного изменчивой, поэтому вам, возможно, придется сравнивать и измерять свой путь. См. этот ответ на crypto.se: crypto.stackexchange.com/a/6469/51068   -  person Morten Jensen    schedule 20.01.2020

Ответы (2)


arrow_upward
3
arrow_downward

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

Если вы выполняете целочисленное деление на константу, например, если вы знаете n во время компиляции, то компилятор может преобразовать это в последовательность умножений и сдвигов, возможно, даже делая то же самое, что и модульное умножение Монтгомери. Если n неизвестно во время компиляции, то, вероятно, стоит реализовать модульное умножение Монтгомери.

Однако лучший ответ вы получите, когда реализуете обе версии своего кода и сравните их.

person G. Sliepen    schedule 20.01.2020
comment
Тот факт, что деление во много раз медленнее, чем умножение, не доказывает, что реализация деления обязательно медленнее, чем реализация Монтгомери. Можете ли вы продемонстрировать, что хорошая реализация Монтгомери на текущих моделях процессоров Intel или AMD обязательно медленнее, чем хорошая реализация деления? - person Eric Postpischil; 20.01.2020
comment
@EricPostpischil Но вопрос не в этом. Вопрос в том, быстрее ли написанное вручную модульное умножение Монтгомери, чем наивное модульное умножение с использованием оператора по модулю. И я не утверждаю, что это будет быстрее, просто это может быть. - person G. Sliepen; 20.01.2020
comment
Этот ответ не представляет собой сбалансированное представление и не показывает данные для его поддержки. - person Eric Postpischil; 20.01.2020

arrow_upward
0
arrow_downward

известно, что все модули меньше 2^64, поэтому все операнды реализованы беззнаковыми 64-битными целыми числами.

Однако a * b — это 128 бит, что усложняет историю. div принимает 128-битное делимое, а a * b / n < n не может переполнить деление (что означало бы входные данные вне допустимого диапазона), так что это тривиально написать на ассемблере x64:

; compute (A * B) % N
; A: rax
; B: rdx
; N: rcx
; result: rdx
mul rdx
div rcx

А на C это написать невозможно, разве что с некоторыми специальными вещами типа __uint128_t или _mul128 и _div128. Как бы вы ни отображали этот код, эта форма div является самой медленной из возможных форм, ищите «:DIV r64 128/64b (полный)», например, в Дамп времени инструкций Haswell. Почти сотня циклов, на процессорах до IceLake это в основном хуже, чем что-либо еще, что вы можете сделать, кроме самостоятельной реализации побитового деления. Ice Lake отличается и, наконец, имеет приличное целочисленное деление на 18 циклов (добавить +4 за начальный mul за общий модуль) он по-прежнему не быстрый, но, по крайней мере, не на порядок выше нормы и, возможно, стоит рассмотреть (включая покупку нового оборудования), потому что:

с множеством различных модулей

Это может сломать все, в зависимости от того, сколько много. Умножение Монтгомери требует найти какой-нибудь забавный модульный обратный модуль по модулю степени двойки, поэтому вы можете по крайней мере использовать Подъем Hensel вместо расширенного евклидова, но все равно стоит дюжина умножений плюс кое-что еще, все последовательно. Точно так же редукция Барретта требует поиска некоторой забавной обратной аппроксимации с фиксированной точкой, что является причудливым способом говоря, что это требует дивизии впереди. При слишком большом количестве различных модулей уловки бесполезны.

person harold    schedule 21.01.2020