Умножение Кочанского

Умножение Кочанского ^[1] — это алгоритм , который позволяет модульную арифметику (умножение или операции на его основе, такие как возведение в степень эффективно выполнять ), когда модуль велик (обычно несколько сотен бит). Это имеет особое применение в теории чисел и криптографии : например, в криптосистеме RSA и обмене ключами Диффи-Хеллмана .

Самый распространенный способ реализации умножения больших целых чисел в аппаратном обеспечении — это выразить множитель в двоичном виде и перечислить его биты, по одному биту за раз, начиная со старшего бита, выполнить следующие операции с аккумулятором :

Удвойте содержимое аккумулятора (если аккумулятор хранит числа в двоичном формате, как это обычно бывает, это простой «сдвиг влево», не требующий реальных вычислений).
Если текущий бит множителя равен 1, добавьте множимое в аккумулятор; если он равен 0, ничего не делайте.

Для n -битного умножителя это займет n тактов (где каждый цикл выполняет либо сдвиг, либо сдвиг и сложение).

Чтобы преобразовать это в алгоритм модульного умножения с модулем r , необходимо условно вычитать r на каждом этапе:

Удвойте содержимое аккумулятора.
Если результат больше или равен r , вычтите r . (Аналогично, вычтите r из аккумулятора и сохраните результат обратно в аккумулятор тогда и только тогда, когда он неотрицательен).
Если текущий бит множителя равен 1, добавьте множимое в аккумулятор; если он равен 0, ничего не делайте.
Если результат сложения больше или равен r , вычтите r . Если никакого добавления не произошло, ничего не делайте.

Этот алгоритм работает. Однако это критически зависит от скорости сложения.

Сложение длинных целых чисел связано с проблемой, заключающейся в том, что переносы должны распространяться справа налево, и окончательный результат неизвестен, пока этот процесс не будет завершен. Распространение переноса можно ускорить с помощью логики просмотра вперед , но это все равно делает сложение намного медленнее, чем необходимо (для 512-битного сложения сложение с просмотром переноса происходит в 32 раза медленнее, чем сложение без переноса вообще). .

В немодульном умножении можно использовать сумматоры с сохранением переноса , которые экономят время, сохраняя переносы из каждой позиции цифр и используя их позже: например, вычисляя 111111111121 вместо того, чтобы ждать, пока перенос распространится по всему целому числу. число, чтобы получить истинное двоичное значение 1000000000001. Это окончательное распространение все еще необходимо выполнить, чтобы получить двоичный результат, но это нужно сделать только один раз в самом конце умножения.

К сожалению, метод модульного умножения, описанный выше, должен знать величину накопленного значения на каждом шаге, чтобы решить, вычитать ли r : например, если ему нужно знать, больше ли значение в аккумуляторе 1000000000000, Представление переноса-сохранения 111111111121 бесполезно, и его необходимо преобразовать в истинное двоичное значение для проведения сравнения.

Поэтому кажется, что можно иметь либо скорость переноса-сохранения , либо модульное умножение, но не то и другое.

Краткое описание алгоритма

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

Вычитание могло не быть произведено, когда оно было необходимо. В этом случае результат в аккумуляторе больше r (хотя алгоритм еще не знает об этом), и поэтому после следующего сдвига влево из 2 r . аккумулятора необходимо будет вычесть
Вычитание могло быть произведено, когда оно не требовалось. В этом случае результат в аккумуляторе меньше 0 (хотя алгоритм еще не знает об этом), и поэтому после следующего сдвига влево r или даже 2 r необходимо будет добавить обратно в аккумулятор, чтобы сделать его положительным. снова.

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

Оказывается ^[2] что проверки четырех наиболее значимых битов аккумулятора достаточно, чтобы удержать ошибки в определенных пределах, и что единственные значения, которые необходимо добавить в аккумулятор, — это −2 r , − r , 0, + r и +2 r , все из которых могут быть созданы мгновенно простыми сдвигами и отрицаниями.

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

Альтернативы

Брикелл ^[3] опубликовал аналогичный алгоритм, который требует большей сложности электроники для каждой цифры аккумулятора.

Умножение Монтгомери - это альтернативный алгоритм, который обрабатывает множитель «назад» (сначала наименее значащая цифра) и использует наименее значащую цифру аккумулятора для управления тем, следует ли добавлять модуль. Это позволяет избежать необходимости распространения переносов. Однако алгоритм непрактичен для одиночных модульных умножений, поскольку необходимо выполнить два или три дополнительных шага Монтгомери, чтобы преобразовать операнды в специальную форму перед обработкой и в конце преобразовать результат обратно в обычный двоичный формат.

Ссылки

^ Кочански, Мартин Дж. (1985). «Разработка чипа RSA». Достижения в криптологии – Труды CRYPTO 85 . Берлин: Springer-Verlag. стр. 350–357. дои : 10.1007/3-540-39799-X_25 . ISBN 3-540-16463-4 . S2CID 35095400 .
^ Кочански, Мартин Дж. (19 августа 2003 г.). «Новый метод последовательного модульного умножения» (PDF) . Архивировано из оригинала (PDF) 16 июля 2018 г. Подробно описан алгоритм.
^ Брикелл, Эрнест Ф. (1983). «Быстрый модульный алгоритм умножения с применением к двухключевой криптографии». Достижения в криптологии – Труды CRYPTO '82 . Нью-Йорк: Пленум. стр. 51–60. дои : 10.1007/978-1-4757-0602-4_5 . ISBN 0-306-41366-3 .

Кочански, Мартин. «Создание чипа FAP4» . Архивировано из оригинала 9 мая 2018 г. Неформальное объяснение и мотивация алгоритма с подробностями реальной аппаратной реализации.

[1] Кочански, Мартин Дж. (1985). «Разработка чипа RSA». Достижения в криптологии – Труды CRYPTO 85 . Берлин: Springer-Verlag. стр. 350–357. дои : 10.1007/3-540-39799-X_25 . ISBN 3-540-16463-4 . S2CID 35095400 .

[2] Кочански, Мартин Дж. (19 августа 2003 г.). «Новый метод последовательного модульного умножения» (PDF) . Архивировано из оригинала (PDF) 16 июля 2018 г. Подробно описан алгоритм.

[3] Брикелл, Эрнест Ф. (1983). «Быстрый модульный алгоритм умножения с применением к двухключевой криптографии». Достижения в криптологии – Труды CRYPTO '82 . Нью-Йорк: Пленум. стр. 51–60. дои : 10.1007/978-1-4757-0602-4_5 . ISBN 0-306-41366-3 .

[1]

[2]

[3]