В модульной арифметики , снижение Барретта является снижение алгоритма введена в 1986 году PD Barrett. [1] Наивный способ вычисления
было бы использовать алгоритм быстрого деления . Редукция Барретта - это алгоритм, разработанный для оптимизации этой операции, предполагая, что постоянно, и , заменяя деления умножением.
Главная идея
Позволять быть инверсией как число с плавающей запятой . потом
где обозначает функцию пола . Результат точный, пока вычисляется с достаточной точностью.
Редукция Барретта одним словом
Барретт изначально рассматривал целочисленную версию вышеупомянутого алгоритма, когда значения помещаются в машинные слова.
При расчете используя метод выше, но с целыми числами, очевидным аналогом было бы использование деления на :
func reduce ( a uint ) uint { q : = a / n // Деление неявно возвращает нижний предел результата. вернуть a - q * n }
Однако деление может быть дорогостоящим и в криптографических настройках может не быть инструкцией с постоянным временем на некоторых процессорах. Таким образом, редукция Барретта приближает со значением потому что деление на это просто сдвиг вправо, поэтому он дешевый.
Чтобы рассчитать наилучшее значение для дано рассмотреть возможность:
Для того чтобы чтобы быть целым числом, нам нужно округлить как-то. Округление до ближайшего целого числа даст наилучшее приближение, но может привести к быть больше, чем , что может вызвать переполнение. Таким образом обычно используется.
Таким образом, мы можем аппроксимировать приведенную выше функцию с помощью:
func reduce ( a uint ) uint { q : = ( a * m ) >> k // ">> k" обозначает битовый сдвиг на k. вернуть a - q * n }
Однако, поскольку , значение q
в этой функции может оказаться слишком маленьким и, следовательно, a
будет гарантировано только в пределах скорее, чем как обычно требуется. Условное вычитание исправит это:
func reduce ( a uint ) uint { q : = ( a * m ) >> k a - = q * n if n <= a { a - = n } return a }
С это только приближение, допустимый диапазон необходимо учитывать. Ошибка приближения является:
Таким образом, ошибка в значении q
составляет. Так долго как то сокращение действительно таким образом . Функция редукции может не сразу дать неправильный ответ, когда но границы необходимо соблюдать, чтобы гарантировать правильный ответ в общем случае.
Выбирая большие значения , диапазон значений для которых допустимо сокращение, можно увеличить, но при больших значениях может вызвать проблемы с переполнением в другом месте.
Пример
Рассмотрим случай при работе с 16-битными целыми числами.
Наименьшее значение это имеет смысл потому что, если тогда уменьшение будет справедливо только для значений, которые уже минимальны! Для значения семь,. По стоимости восемь. Таким образом не дает преимущества, потому что приближение в этом случае () точно так же, как . Для, мы получили , что является лучшим приближением.
Теперь мы рассмотрим допустимые диапазоны ввода для а также . В первом случае так подразумевает . С является целым числом, максимальное значение - 478. (На практике функция работает для значений до 504.)
Если мы возьмем тогда и поэтому максимальное значение - 7387. (На практике функция работает до 7473.)
Следующее значение что приводит к лучшему приближению, равно 13, что дает . Однако обратите внимание, что промежуточное значение в вычислении затем переполнится 16-битное значение без знака, когда , таким образом работает лучше в этой ситуации.
Доказательство диапазона для конкретного k
Позволять быть наименьшим целым таким, что . Брать как разумное значение для в приведенных выше уравнениях. Как и в приведенных выше фрагментах кода, пусть
- а также
- .
Благодаря функции пола , целое число и . Кроме того, если тогда . В этом случае запишите приведенные выше фрагменты в виде выражения:
Доказательство того, что следует:
Если , тогда
С независимо от того , следует, что
Редукция Барретта из нескольких слов
Первичной мотивацией Барретта рассмотреть возможность сокращения была реализация RSA , где рассматриваемые значения почти наверняка будут превышать размер машинного слова. В этой ситуации Барретт предоставил алгоритм, который аппроксимирует версию из одного слова выше, но для значений из нескольких слов. Подробнее см. Раздел 14.3.3 Справочника по прикладной криптографии . [2]
Смотрите также
- Редукция Монтгомери - еще один похожий алгоритм.
Рекомендации
- ^ Барретт, П. (1986). «Реализация алгоритма шифрования открытого ключа Rivest Shamir и Adleman на стандартном цифровом сигнальном процессоре». Достижения в криптологии - CRYPTO '86 . Конспект лекций по информатике. 263 . С. 311–323. DOI : 10.1007 / 3-540-47721-7_24 . ISBN 978-3-540-18047-0.
- ^ Менезеш, Альфред; Оршот, Пол; Ванстон, Скотт (1997). Справочник по прикладной криптографии . ISBN 0-8493-8523-7.
Источники
- Bosselaers, A .; Govaerts, R .; Вандевалле, Дж. (1993). «Сравнение трех модульных функций редукции» . В Стинсоне, Дуглас Р. (ред.). Достижения в криптологии - Crypto'93 . Конспект лекций по информатике. 773 . Springer. С. 175–186. CiteSeerX 10.1.1.40.3779 . ISBN 3540483292.
- Hasenplaugh, W .; Gaubatz, G .; Гопал, В. (2007). «Быстрое модульное сокращение» (PDF) . 18-й симпозиум IEEE по компьютерной арифметике (ARITH'07) . С. 225–9. DOI : 10,1109 / ARITH.2007.18 . ISBN 978-0-7695-2854-0. S2CID 14801112 .