Редукция Барретта - Barrett reduction

В модульная арифметика, Редукция Барретта это сокращение алгоритм представленный в 1986 году П.Д. Барретт.^[1] Наивный способ вычисления

${ Displaystyle с = а , { bmod {,}} п ,}$

было бы использовать быстрое алгоритм деления. Редукция Барретта - это алгоритм, разработанный для оптимизации этой операции, предполагая, что ${ displaystyle n}$ постоянно, и ${ Displaystyle а <п ^ {2}}$, заменяя деления умножением.

Главная идея

Позволять ${ displaystyle s = 1 / n}$ быть инверсией ${ displaystyle n}$ как плавающая точка номер. потом

${ displaystyle a , { bmod {,}} n = a- lfloor как rfloor n}$

куда ${ displaystyle lfloor x rfloor}$ обозначает функция пола. Результат точный, пока ${ displaystyle s}$ вычисляется с достаточной точностью.

Редукция Барретта из одного слова

Барретт изначально рассматривал целочисленную версию вышеупомянутого алгоритма, когда значения помещаются в машинные слова.

При расчете ${ Displaystyle а , { bmod {,}} п}$ используя метод выше, но с целыми числами, очевидным аналогом было бы использование деления на ${ displaystyle n}$:

func уменьшать(а uint) uint {  q := а / п  // Деление неявно возвращает нижний предел результата.  возвращаться а - q * п}

Однако деление может быть дорогостоящим и в криптографических настройках может не быть инструкцией с постоянным временем на некоторых процессорах. Таким образом, редукция Барретта приближает ${ displaystyle 1 / n}$ со значением ${ displaystyle m / 2 ^ {k}}$ потому что деление на ${ displaystyle 2 ^ {k}}$ это просто сдвиг вправо, и поэтому он дешев.

Чтобы рассчитать наилучшее значение для ${ displaystyle m}$ данный ${ displaystyle 2 ^ {k}}$ учитывать:

${ displaystyle { frac {m} {2 ^ {k}}} = { frac {1} {n}} ; Longleftrightarrow ; m = { frac {2 ^ {k}} {n}} }$

Для того чтобы ${ displaystyle m}$ чтобы быть целым числом, нам нужно округлить ${ displaystyle {2 ^ {k}} / {n}}$ как-то. Округление до ближайшего целого числа даст наилучшее приближение, но может привести к ${ displaystyle m / 2 ^ {k}}$ быть больше, чем ${ displaystyle 1 / n}$, что может вызвать переполнение. Таким образом ${ Displaystyle м = lfloor {2 ^ {k}} / {n} rfloor}$ обычно используется.

Таким образом, мы можем аппроксимировать приведенную выше функцию с помощью:

func уменьшать(а uint) uint {  q := (а * м) >> k // ">> k" обозначает битовый сдвиг на k.  возвращаться а - q * п}

Однако, поскольку ${ Displaystyle м / 2 ^ {к} leq 1 / п}$, значение q в этой функции может оказаться слишком мало, и, следовательно, а только гарантировано быть в пределах ${ displaystyle [0,2n)}$ скорее, чем ${ Displaystyle [0, п)}$ как обычно требуется. Условное вычитание исправит это:

func уменьшать(а uint) uint {  q := (а * м) >> k  а -= q * п  если п <= а {    а -= п  }  возвращаться а}

С ${ displaystyle m / 2 ^ {k}}$ является лишь приближением, допустимый диапазон ${ displaystyle a}$ необходимо учитывать. Ошибка приближения ${ displaystyle 1 / n}$ является:

${ displaystyle e = { frac {1} {n}} - { frac {m} {2 ^ {k}}}}$

Таким образом, ошибка в значении q является ${ displaystyle ae}$. Так долго как ${ displaystyle ae <1}$ то сокращение действительно таким образом ${ displaystyle a <1 / e}$. Функция сокращения может не сразу дать неправильный ответ, когда ${ displaystyle a geq 1 / e}$ но границы ${ displaystyle a}$ необходимо соблюдать, чтобы гарантировать правильный ответ в общем случае.

Выбирая большие значения ${ displaystyle k}$, диапазон значений ${ displaystyle a}$ для которых допустимо сокращение, можно увеличить, но при больших значениях ${ displaystyle k}$ может вызвать проблемы с переполнением в другом месте.

Пример

Рассмотрим случай ${ displaystyle n = 101}$ при работе с 16-битными целыми числами.

Наименьшее значение ${ displaystyle k}$ это имеет смысл ${ displaystyle k = 7}$ потому что, если ${ Displaystyle 2 ^ {к} <п}$ тогда уменьшение будет действительно только для значений, которые уже минимальны! Для значения семь, ${ Displaystyle м = lfloor 2 ^ {k} / n rfloor = lfloor 128/101 rfloor = 1}$. По стоимости восемь ${ displaystyle m = lfloor 256/101 rfloor = 2}$. Таким образом ${ displaystyle k = 8}$ не дает преимущества, поскольку приближение ${ displaystyle 1/101}$ в таком случае (${ displaystyle 2/256}$) точно так же, как ${ displaystyle 1/128}$. За ${ displaystyle k = 9}$, мы получили ${ displaystyle m = 512/101 = 5}$, что является лучшим приближением.

Теперь мы рассмотрим допустимые диапазоны ввода для ${ displaystyle k = 7}$ и ${ displaystyle k = 9}$. В первом случае ${ displaystyle e = 1 / n-m / 2 ^ {k} = 1 / 101–1 / 128 = 27/12928}$ так ${ displaystyle a <1 / e}$ подразумевает ${ displaystyle a <478.81}$. С ${ displaystyle a}$ является целым числом, максимальное значение - 478. (На практике функция работает для значений до 504.)

Если мы возьмем ${ displaystyle k = 9}$ тогда ${ displaystyle e = 1 / 101-5 / 512 = 7/51712}$ и поэтому максимальное значение ${ displaystyle a}$ - 7387. (На практике функция работает до 7473.)

Следующее значение ${ displaystyle k}$ что дает лучшее приближение - 13, что дает ${ displaystyle 81/8192}$. Однако обратите внимание, что промежуточное значение ${ displaystyle ax}$ при вычислении переполнится 16-битным значением без знака, когда ${ displaystyle 810 leq a}$, таким образом ${ displaystyle k = 7}$ работает лучше в этой ситуации.

Доказательство диапазона для конкретного k

Позволять ${ displaystyle k_ {0}}$ быть наименьшим целым таким, что ${ displaystyle 2 ^ {k_ {0}}> п}$. Брать ${ displaystyle k_ {0} +1}$ как разумное значение для ${ displaystyle k}$ в приведенных выше уравнениях. Как и в приведенных выше фрагментах кода, пусть

• ${ displaystyle q = left lfloor { frac {ma} {2 ^ {k}}} right rfloor}$ и
• ${ displaystyle r = a-qn}$.

Из-за функция пола, ${ displaystyle q}$ целое число и ${ Displaystyle г эквив { pmod {п}}}$. Кроме того, если ${ displaystyle a <2 ^ {k}}$ тогда ${ Displaystyle г <2n}$. В этом случае запишите приведенные выше фрагменты в виде выражения:

${ displaystyle a , { bmod {,}} n = { begin {case} r & { text {if}} r$

Доказательство того, что ${ Displaystyle г <2n}$ следует:

Если ${ displaystyle a <2 ^ {k}}$, тогда

${ displaystyle { frac {a} {2 ^ {k}}} cdot (2 ^ {k} mod n)$

С ${ Displaystyle п cdot { гидроразрыва {ma mod 2 ^ {k}} {2 ^ {k}}} <п}$ невзирая на ${ displaystyle a}$, следует, что

${ displaystyle { frac {a cdot (2 ^ {k} mod n)} {2 ^ {k}}} + n cdot { frac {ma mod 2 ^ {k}} {2 ^ { k}}} <2n}$

${ displaystyle a- left (a - { frac {a cdot (2 ^ {k} mod n)} {2 ^ {k}}} right) + { frac {n cdot (ma мод 2 ^ {k})} {2 ^ {k}}} <2n}$

${ displaystyle a - { frac {a} {2 ^ {k}}} cdot left (2 ^ {k} - (2 ^ {k} mod n) right) + { frac {n cdot (ma mod 2 ^ {k})} {2 ^ {k}}} <2n}$

${ displaystyle a - { frac {na} {2 ^ {k}}} cdot left ({ frac {2 ^ {k} - (2 ^ {k} mod n)} {n}} вправо) + { frac {n cdot (ma mod 2 ^ {k})} {2 ^ {k}}} <2n}$

${ displaystyle a - { frac {na} {2 ^ {k}}} cdot left lfloor { frac {2 ^ {k}} {n}} right rfloor + { frac {n cdot (ma mod 2 ^ {k})} {2 ^ {k}}} <2n}$

${ displaystyle a - { frac {nma} {2 ^ {k}}} + { frac {n cdot (ma mod 2 ^ {k})} {2 ^ {k}}} <2n}$

${ displaystyle a- left ({ frac {ma- (ma mod 2 ^ {k})} {2 ^ {k}}} right) cdot n <2n}$

${ displaystyle a- left lfloor { frac {ma} {2 ^ {k}}} right rfloor cdot n <2n}$

${ displaystyle a-qn <2n}$

${ Displaystyle г <2n}$

Редукция Барретта из нескольких слов

Первичной мотивацией Барретта рассмотреть возможность сокращения было внедрение ЮАР, где рассматриваемые значения почти наверняка будут превышать размер машинного слова. В этой ситуации Барретт предоставил алгоритм, который аппроксимирует версию из одного слова выше, но для значений из нескольких слов. Подробнее см. Раздел 14.3.3 Справочник по прикладной криптографии.^[2]

Смотрите также

• Редукция Монтгомери еще один похожий алгоритм.

Рекомендации

Источники