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

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

$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.

См. также

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