Алгоритм Барретта

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

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

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

Основная идея

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

a\,{\bmod {\,}}n=a-\lfloor as\rfloor n,

где $\lfloor x\rfloor$ означает округление до ближайшего целого в сторону уменьшения. Результат будет точным, если $s$ вычислено с достаточной точностью.

Приведение Барретта для одного слова

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

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

func reduce(a uint) uint {
    q := a / n  // Деление в неявной форме возвращает результат, округлённый до ближайшего целого вниз.
    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" означает сдвиг  на k позиций.
    return a - q * n
}

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

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

Поскольку $m/2^{k}$ является лишь приближением, следует рассматривать правильные границы $a$ . Ошибка приближения к $1/n$ равна

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

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

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

Пример

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

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

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

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

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

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

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

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

Поскольку осуществляется округление до целого вниз, $q$ является целым числом и $r\equiv a{\pmod {n}}$ . Также, если $a<2^{k}$ , то $r<2n$ . В этом случае переписываем отрывок кода выше:

a\,{\bmod {\,}}n={\begin{cases}r&{\text{если }}r<n\\r-n&{\text{иначе}}\end{cases}}

Доказательство неравенства $r<2n$ :

Если $a<2^{k}$ , то

{\frac {a}{2^{k}}}\cdot (2^{k}\mod n)<n

Поскольку $n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<n$ независимо от $a$ , отсюда следует, что

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

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

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

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

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

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

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

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

a-qn<2n

r<2n

Приведение Барретта к нескольким машинным словам

Основной причиной для Баррета обратиться к приведению была работа с реализацией алгоритма RSA, где значения чисел почти наверняка выйдут за границы машинного слова. В этой ситуации Барретт представил алгоритм, который аппроксимирует числа, размещённые в нескольких машинных словах. Детали см. в разделе 14.3.3 книги Handbook of Applied Cryptography^[2].

См. также

Алгоритм Монтгомери является другим алгоритмом, похожим на алгоритм Барретта.

Литература

Barrett P. Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor // Advances in Cryptology — CRYPTO' 86. — 1986. — Т. 263. — (Lecture Notes in Computer Science). — ISBN 978-3-540-18047-0. — doi:10.1007/3-540-47721-7_24.
Alfred Menezes, Paul Oorschot, Scott Vanstone. Handbook of Applied Cryptography. — 1997. — ISBN 0-8493-8523-7.
Bosselaers A., Govaerts R., Vandewalle J. Comparison of Three Modular Reduction Functions // Advances in Cryptology — Crypto'93 / (ed) Douglas R. Stinson. — Springer, 1993. — Т. 773. — С. 175–186. — (Lecture Notes in Computer Science). — ISBN 3540483292.
Hasenplaugh W., Gaubatz G., Gopal V. Fast Modular Reduction // 18th IEEE Symposium on Computer Arithmetic(ARITH'07). — 2007. — С. 225–9. — ISBN 978-0-7695-2854-0. — doi:10.1109/ARITH.2007.18.

[_5c0c4d3af70be8e9-1] Barrett, 1986, с. 311–323.

[_46b31a41a6412bf5-2] Menezes, Oorschot, Vanstone, 1997.

[1]

[2]