Сокращение Барретта

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

Наивный способ вычислений

c=a\,{\bmod {\,}}n\,

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

Исторически для ценностей $a,b<n$ , один вычисленный $ab\,{\bmod {\,}}n\,$ применяя Приведение Барретта к полному произведению $ab$ . Недавно было показано, что полное произведение не является необходимым, если мы можем выполнить предварительные вычисления для одного из операндов. ^[2]^[3]

Общая идея

Мы вызываем функцию $\left[\,\right]:\mathbb {R} \to \mathbb {Z}$ целочисленное приближение, если $|\left[z\right]-z|\leq 1$ . Для модуля $n$ и целочисленное приближение $\left[\,\right]$ , мы определяем ${\text{mod}}^{\left[\,\right]}\,n:\mathbb {Z} \to (\mathbb {Z} /n\mathbb {Z} )$ как

a\,{\text{mod}}^{\left[\,\right]}\,n=a-\left[a/n\right]n

.

Распространенный выбор $\left[\,\right]$ — это функции Floor , потолок и округление .

Обычно умножение Барретта начинается с указания двух целочисленных приближений. $\left[\,\right]_{0},\left[\,\right]_{1}$ и вычисляет достаточно близкое приближение $ab\,{\bmod {\,}}n$ как

ab-\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}n

,

где $R$ — фиксированная константа, обычно степень 2, выбранная так, чтобы умножение и деление на $R$ может выполняться эффективно.

Дело $b=1$ был представлен П.Д. Барреттом ^[1] для случая напольной функции $\left[\,\right]_{0}=\left[\,\right]_{1}=\lfloor \,\rfloor$ . Общий случай для $b$ можно найти в NTL . ^[2] Представление целочисленной аппроксимации и соответствие между умножением Монтгомери и умножением Барретта были обнаружены Ханно Беккером, Винсентом Хвангом, Матиасом Дж. Каннвишером, Бо-Инь Яном и Шан-И Яном. ^[3]

Сокращение Барретта одним словом

Первоначально Барретт рассматривал целочисленную версию приведенного выше алгоритма, когда значения укладываются в машинные слова. Проиллюстрируем идею для случая функции пола с помощью $b=1$ и $R=2^{k}$ .

При расчете $a\,{\bmod {\,}}n$ для беззнаковых целых чисел очевидным аналогом было бы использование деления на $n$ :

func reduce(a uint) uint {
    q:= a / n  // Division implicitly returns the floor of the result.
    return a - q * n
}

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

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

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

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

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

func reduce(a uint) uint {
    q := (a * m) >> k // ">> k" denotes bitshift by k.
    return a - q * n
}

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

func reduce(a uint) uint {
    q := (a * m) >> k
    a -= q * n
    if a >= n {
        a -= n
    }
    return a
}

Умножение Барретта одним словом

Предполагать $b$ известно. Это позволяет нам предварительно вычислить $\left\lfloor {\frac {bR}{n}}\right\rfloor$ прежде чем мы получим $a$ . Вычисления умножения Барретта $ab$ , приближается к верхней части $ab$ с $\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n$ , и вычитает приближение. С $\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n$ кратно $n$ , результирующее значение $ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n$ является представителем $ab\,{\bmod {\,}}n$ .

Соответствие между умножениями Барретта и Монтгомери

Напомним, что беззнаковое умножение Монтгомери вычисляет представителя $ab\,{\bmod {\,}}n$ как

{\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}

.

Фактически это значение равно $ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n$ .

Докажем это утверждение следующим образом.

{\begin{aligned}&&&ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n\\&=&&ab-{\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor -\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)}{R}}\,n\\&=&&\left({\frac {abR}{n}}-a\left\lfloor {\frac {bR}{n}}\right\rfloor +\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {abR}{n}}-a{\frac {bR-\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {a\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {a\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&{\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}.\end{aligned}}

Обычно для целочисленных приближений $\left[\,\right]_{0},\left[\,\right]_{1}$ , у нас есть

ab-\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}\,n={\frac {a\left(bR\,{\text{mod}}^{\left[\,\right]_{0}}\,n\right)+\left(a\left(-bR\,{\text{mod}}^{\left[\,\right]_{0}}\,q\right)n^{-1}\,{\text{mod}}^{\left[\,\right]_{1}}\,R\right)n}{R}}

. ^[3]

Диапазон умножения Барретта

Мы связали вывод с помощью $ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n={\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}\leq {\frac {an+Rn}{R}}=n\left(1+{\frac {a}{R}}\right)$ .

Аналогичные оценки справедливы и для других видов функций целочисленной аппроксимации. Например, если мы выберем $\left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil$ , функция округления в большую сторону , тогда у нас есть

\left|ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rceil }{R}}\right\rceil \,n\right|=\left|{\frac {a\left(bR\,{\text{mod}}^{\pm }\,n\right)+\left(a\left(-bR\,{\text{mod}}^{\pm }\,n\right)n^{-1}\,{\text{mod}}^{\pm }\,R\right)n}{R}}\right|\leq \left|{\frac {a{\frac {n}{2}}+{\frac {R}{2}}n}{R}}\right|={\frac {n}{2}}\left(1+{\frac {|a|}{R}}\right).

Сокращение Барретта из нескольких слов

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

Алгоритм Барретта для полиномов

Также можно использовать алгоритм Барретта для деления полиномов, обращая полиномы и используя X-адическую арифметику. ^[5]

См. также

Сокращение Монтгомери — еще один похожий алгоритм.

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Барретт, П. (1986). «Реализация алгоритма шифрования с открытым ключом Ривеста Шамира и Адлемана на стандартном процессоре цифровых сигналов». Достижения криптологии – КРИПТО' 86 . Конспекты лекций по информатике. Том. 263. С. 311–323. дои : 10.1007/3-540-47721-7_24 . ISBN 978-3-540-18047-0 .
^ Jump up to: Перейти обратно: ^а ^б Шуп, Виктор. «Библиотека теории чисел» .
^ Jump up to: Перейти обратно: ^а ^б ^с Беккер, Ханно; Хван, Винсент; Канвишер, Маттиас Дж.; Ян, Бо-Инь; Ян, Шан-И, «Neon NTT: более быстрый дилитий, Kyber и Sabre на Cortex-A72 и Apple M1» , Транзакции по криптографическому оборудованию и встроенным системам , 2022 (1): 221–244
^ Менезес, Альфред; Ооршот, Пол; Ванстон, Скотт (1997). Справочник по прикладной криптографии . ISBN 0-8493-8523-7 .
^ «Редукция Барретта для полиномов» . www.corsix.org . Проверено 7 сентября 2022 г.

Источники

Босселерс, А.; Говертс, Р.; Вандевалле, Дж. (1993). «Сравнение трех модульных функций приведения» . В Стинсоне, Дуглас Р. (ред.). Достижения криптологии – Крипто'93 . Конспекты лекций по информатике. Полный. 773. Спрингер. стр. 175–186. CiteSeerX 10.1.1.40.3779 . ISBN 3540483292 .
Хазенплау, В.; Гаубац, Г.; Гопал, В. (2007). «Быстрое модульное сокращение» (PDF) . 18-й симпозиум IEEE по компьютерной арифметике (ARITH'07) . стр. 225–229. дои : 10.1109/ARITH.2007.18 . ISBN 978-0-7695-2854-0 . S2CID 14801112 .

[Barrett1986-1] Jump up to: Перейти обратно: ^а ^б Барретт, П. (1986). «Реализация алгоритма шифрования с открытым ключом Ривеста Шамира и Адлемана на стандартном процессоре цифровых сигналов». Достижения криптологии – КРИПТО' 86 . Конспекты лекций по информатике. Том. 263. С. 311–323. дои : 10.1007/3-540-47721-7_24 . ISBN 978-3-540-18047-0 .

[ShoupNTL-2] Jump up to: Перейти обратно: ^а ^б Шуп, Виктор. «Библиотека теории чисел» .

[NeonNTT2022-3] Jump up to: Перейти обратно: ^а ^б ^с Беккер, Ханно; Хван, Винсент; Канвишер, Маттиас Дж.; Ян, Бо-Инь; Ян, Шан-И, «Neon NTT: более быстрый дилитий, Kyber и Sabre на Cortex-A72 и Apple M1» , Транзакции по криптографическому оборудованию и встроенным системам , 2022 (1): 221–244

[4] Менезес, Альфред; Ооршот, Пол; Ванстон, Скотт (1997). Справочник по прикладной криптографии . ISBN 0-8493-8523-7 .

[5] «Редукция Барретта для полиномов» . www.corsix.org . Проверено 7 сентября 2022 г.

[1]

[2]

[3]

[4]

[5]