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

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

${\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[2].

См. также

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

Примечания

1. Barrett, 1986, с. 311–323.
2. Menezes, Oorschot, Vanstone, 1997.

Литература

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