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

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

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

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

Основная идеяПравить

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

$amodn=a-<!--\; -\; -->\lfloor <!--\; \lfloor \; -->as\rfloor <!--\; \rfloor \; -->n,$$a\,{\bmod {\,}}n=a-\lfloor as\rfloor n,$ 

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

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

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

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

func reduce(a uint) uint {
    q := a / n  // Деление в неявной форме возвращает результат, округлённый до ближайшего целого вниз.
    return a - q * n
}

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

Чтобы вычислить лучшее значение величины $m$$m$  для заданного $2^k$$2^k$ , рассмотрим

$\frac{m}{2^k}=\frac{1}{n}⟺<!--\; ⟺\; -->m=\frac{2^k}{n}$${\frac {m}{2^{k}}}={\frac {1}{n}}\;\Longleftrightarrow \;m={\frac {2^{k}}{n}}$ 

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

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

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

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

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

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

$e=\frac{1}{n}-<!--\; -\; -->\frac{m}{2^k}$$e={\frac {1}{n}}-{\frac {m}{2^{k}}}$ 

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

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

ПримерПравить

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

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

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

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

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

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

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

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

Поскольку осуществляется округление до целого вниз, $q$$q$  является целым числом и $r\equiv <!--\; \equiv \; -->a(\mathrm{mod}n)$$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$$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.

См. такжеПравить

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