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

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

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

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

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

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

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

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

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

При вычислении ${\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}\leqslant 1/n}$ , значение q в этой функции может оказаться слишком мало, а тогда a гарантированно будет только в интервале ${\displaystyle [0,2n)}$ , а не в ${\displaystyle [0,n)}$ , как обычно требуется. Вычитание по условию может исправить ситуацию:

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle a-qn<2n}$

${\displaystyle r<2n}$

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

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

См. также

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

Примечания

Литература