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

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

$c=amodn$

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

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

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

$amodn=a-\lfloor as\rfloor n,$

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

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

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

При вычислении $amodn$ с помощью вышеуказанного метода, но с целыми числами, очевидной аналогией было бы деление на $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}⟺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⩽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⩾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⩽a$, так что $k=7$ в этой ситуации работает лучше.

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

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

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

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

$amodn=\{\begin{array}{cc}r& \text{если }r<n\\ r-n& \text{иначе}\end{array}$

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

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

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

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

$\frac{a\cdot (2^{k}modn)}{2^k}+n\cdot \frac{mamod{2}^k}{2^k}<2n$

$a-(a-\frac{a\cdot (2^{k}modn)}{2^k})+\frac{n\cdot (mamod{2}^k)}{2^k}<2n$

$a-\frac{a}{2^k}\cdot (2^k-(2^{k}modn))+\frac{n\cdot (mamod{2}^k)}{2^k}<2n$

$a-\frac{na}{2^k}\cdot \left(\frac{2^k-(2^{k}modn)}{n}\right)+\frac{n\cdot (mamod{2}^k)}{2^k}<2n$

$a-\frac{na}{2^k}\cdot \lfloor \frac{2^k}{n}\rfloor +\frac{n\cdot (mamod{2}^k)}{2^k}<2n$

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

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

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

$a-qn<2n$

$r<2n$

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга