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

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

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

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

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

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

Общая идея

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

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

Обычными вариантами являются функции пола , потолка и округления . ${\displaystyle \left[\,\right]}$

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

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

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

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

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

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

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

func reduce ( a uint ) uint { q := a / n // Деление неявно возвращает нижнюю часть результата. return a - q * n }               

Однако деление может быть дорогим и, в криптографических настройках, может не быть постоянной по времени инструкцией на некоторых процессорах, подвергая операцию атаке по времени . Таким образом, сокращение Барретта приближается к значению, поскольку деление на — это просто сдвиг вправо, и поэтому оно дешево. ${\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 m=\lfloor {2^{k}}/{n}\rfloor }$

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

func reduce ( a uint ) uint { q := ( a * m ) >> k // ">> k" обозначает сдвиг бита на k. return a - q * n }                  

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

функция reduce ( a uint ) uint { q := ( a * m ) >> k a -= q * n если a >= n { a -= n } вернуть a }                           

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle 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]

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

Мы связали вывод с . ${\displaystyle 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)}$

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

${\displaystyle \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]

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

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

Ссылки

1. Barrett, P. (1986). "Реализация алгоритма шифрования с открытым ключом Ривеста Шамира и Адлемана на стандартном цифровом сигнальном процессоре". Advances in Cryptology – CRYPTO' 86. Lecture Notes in Computer Science. Vol. 263. pp. 311–323. doi :10.1007/3-540-47721-7_24. ISBN 978-3-540-18047-0.
2. Шуп, Виктор. «Библиотека теории чисел».
3. Беккер, Ханно; Хванг, Винсент; Каннвишер, Маттиас Дж.; Ян, Бо-Инь; Ян, Шан-И (2021), «Neon NTT: более быстрые Dilithium, Kyber и Saber на Cortex-A72 и Apple M1», Труды по криптографическому оборудованию и встраиваемым системам , 2022 (1): 221–244, doi :10.46586/tches.v2022.i1.221-244
4. Менезес, Альфред; Ооршот, Пол; Ванстоун, Скотт (1997). Справочник по прикладной криптографии (5-е изд.). CRC Press. doi :10.1201/9780429466335. ISBN 0-8493-8523-7.
5. "Снижение Барретта для полиномов". www.corsix.org . Получено 2022-09-07 .

Источники

• Bosselaers, A.; Govaerts, R.; Vandewalle, J. (1993). "Сравнение трех функций модулярной редукции". В Stinson, Douglas R. (ред.). Advances in Cryptology – Crypto'93 . Lecture Notes in Computer Science. Vol. 773. Springer. pp. 175–186. CiteSeerX  10.1.1.40.3779 . ISBN 3540483292.
• Hasenplaugh, W.; Gaubatz, G.; Gopal, V. (2007). "Быстрое модульное сокращение" (PDF) . 18-й симпозиум IEEE по компьютерной арифметике (ARITH'07) . стр. 225–229. doi :10.1109/ARITH.2007.18. ISBN 978-0-7695-2854-0. S2CID  14801112.