Русская Википедия:Алгоритм Барретта
Алгоритм Барретта — это алгоритм приведения, который в 1986 году предложил П. Д. БарреттШаблон:Sfn. Обычный способ вычисления
- <math>c = a \,\bmod\, n \, </math>
использовал бы быстрый алгоритм деления. Приведение Баррета разработано для оптимизации этой операции путём замены делений на умножения в предположении, что <math>n</math> является постоянной величиной, а <math>a<n^2</math>.
Основная идея
Пусть <math>s=1/n</math> будет обратным числом для <math>n</math> как число с плавающей запятой. Тогда
- <math>a \,\bmod\, n = a-\lfloor a s\rfloor n, </math>
где <math>\lfloor x \rfloor</math> означает округление до ближайшего целого в сторону уменьшения. Результат будет точным, если <math>s</math> вычислено с достаточной точностью.
Приведение Барретта для одного слова
Барретт первоначально рассматривал целочисленную версию алгоритма выше, когда значения помещаются в машинное слово.
При вычислении <math>a \,\bmod\, n</math> с помощью вышеуказанного метода, но с целыми числами, очевидной аналогией было бы деление на <math>n</math>:
func reduce(a uint) uint {
q := a / n // Деление в неявной форме возвращает результат, округлённый до ближайшего целого вниз.
return a - q * n
}
Однако деление может стоить дорого и в условиях задач криптографии может не иметь постоянного времени выполнения на некоторых ЦПУ. В этом случае приведение Барретта аппроксимирует <math>1/n</math> значением <math>m/2^k</math>, поскольку деление на <math>2^k</math> является просто сдвигом вправо и выполняется быстро.
Чтобы вычислить лучшее значение величины <math>m</math> для заданного <math>2^k</math>, рассмотрим
- <math>\frac{m}{2^k} = \frac{1}{n} \;\Longleftrightarrow\; m = \frac{2^k}{n}</math>
Чтобы <math>m</math> было целым, нам нужно округлить как-то <math>{2^k}/{n}</math>. Округление до ближайшего целого даст лучшее приближение, но может привести к тому, что <math>m/2^k</math> будет больше <math>1/n</math>, что может привести к обнулению. Поэтому обычно используется <math>m = \lfloor {2^k}/{n} \rfloor</math>.
Теперь мы можем аппроксимировать функцию выше так:
func reduce(a uint) uint {
q := (a * m) >> k // ">> k" означает сдвиг на k позиций.
return a - q * n
}
Однако, поскольку <math>m/2^k \leqslant 1/n</math>, значение q в этой функции может оказаться слишком мало, а тогда a гарантированно будет только в интервале <math>[0, 2n)</math>, а не в <math>[0, n)</math>, как обычно требуется. Вычитание по условию может исправить ситуацию:
func reduce(a uint) uint {
q := (a * m) >> k
a -= q * n
if n <= a {
a -= n
}
return a
}
Поскольку <math>m/2^k</math> является лишь приближением, следует рассматривать правильные границы <math>a</math>. Ошибка приближения к <math>1/n</math> равна
- <math>e = \frac{1}{n} - \frac{m}{2^k}</math>
Тогда ошибка значения q равна <math>ae</math>. Поскольку <math>ae < 1</math>, то приведение будет верным, поскольку <math>a < 1/e</math>. Функция приведения может не сразу дать неверный ответ при <math>a \geqslant 1/e</math>, но границы <math>a</math> следует соблюдать, чтобы обеспечить правильный ответ в общем случае.
При выборе бо́льших значений <math>k</math> область значений <math>a</math>, для которых приведение верно, может быть увеличена, но бо́льшие значения <math>k</math> могут вызвать проблемы переполнения в другом месте.
Пример
Рассмотрим случай <math>n = 101</math> при работе с 16-битными целыми числами.
Наименьшее имеющее смысл значение <math>k</math> равно <math>k = 7</math>, поскольку при <math>2^k < n</math> приведение будет верно для значений, которые уже минимальны! Для значения семь <math>m = \lfloor 2^k / n \rfloor = \lfloor 128 / 101 \rfloor = 1</math>. Для значения восемь <math>m = \lfloor 256 / 101 \rfloor = 2</math>. Тогда значение <math>k = 8</math> не даёт никаких преимуществ, поскольку приближение <math>1/101</math> в этом случае (<math>2/256</math>) будет тем же самым, что и для <math>1/128</math>. Для <math>k = 9</math> мы получаем <math>m = \lfloor 512 / 101 \rfloor = 5</math>, что является лучшим приближением.
Теперь рассмотрим границы входных данных для <math>k = 7</math> и <math>k = 9</math>. В первом случае <math>e = 1/n - m/2^k = 1/101 - 1/128 = 27/12928</math>, так что из <math>a < 1/e</math> вытекает <math>a < 478{,}81</math>. Поскольку число <math>a</math> целое, эффективное максимальное значение равно 478. (На самом деле функция будет работать со значениями вплоть до 504.)
Если мы возьмём <math>k = 9</math>, то <math>e = 1/101 - 5/512 = 7/51712</math> и тогда максимальное значение <math>a</math> равно 7387. (Функция будет работать до значения 7473.)
Следующее значение <math>k</math>, которое приводит к лучшему приближению, равно 13, что даёт <math>81/8192</math>. Однако заметим, что промежуточное значение <math>ax</math> при вычислениях приведёт к переполнению 16-битного значения, когда <math>810 \leqslant a</math>, так что <math>k = 7</math> в этой ситуации работает лучше.
Доказательство для границ для конкретного k
Пусть <math>k_0</math> будет наименьшим целым, таким что <math>2^{k_0}>n</math>. Возьмём <math>k_0+1</math> в качестве приемлемого значения <math>k</math> в равенствах выше. Как и в выше приведённом коде, положим
- <math>q = \left\lfloor \frac{m a}{2^k} \right\rfloor </math> и
- <math>r = a - q n</math>.
Поскольку осуществляется округление до целого вниз, <math>q</math> является целым числом и <math>r \equiv a \pmod{n}</math>. Также, если <math>a < 2 ^ k</math>, то <math>r < 2n</math>. В этом случае переписываем отрывок кода выше:
- <math>a \,\bmod\, n = \begin{cases} r & \text{если } r<n \\ r-n & \text{иначе} \end{cases}</math>
Доказательство неравенства <math>r < 2n</math>:
Если <math>a < 2 ^ k</math>, то
- <math>\frac{a}{2 ^ k} \cdot (2 ^ k \mod n) < n</math>
Поскольку <math>n\cdot\frac{m a \mod 2^k}{2^k} < n</math> независимо от <math>a</math>, отсюда следует, что
- <math> \frac{a\cdot (2 ^ k \mod n)}{2 ^ k} + n\cdot\frac{m a \mod 2^k}{2^k} < 2n</math>
- <math> a - \left(a - \frac{a\cdot (2 ^ k \mod n)}{2 ^ k}\right) + \frac{n \cdot (m a \mod 2^k)}{2^k} < 2n</math>
- <math> a - \frac{a}{2^k} \cdot \left(2^k - (2^k \mod n)\right) + \frac{n \cdot (m a \mod 2^k)}{2^k} < 2n</math>
- <math> a - \frac{na}{2^k} \cdot \left(\frac{2^k - (2^k \mod n)}{n}\right) + \frac{n \cdot (m a \mod 2^k)}{2^k} < 2n</math>
- <math> a - \frac{n a}{2^k} \cdot \left\lfloor\frac{2^k}{n}\right\rfloor\ + \frac{n \cdot (m a \mod 2^k)}{2^k} < 2n</math>
- <math> a - \frac{n m a}{2 ^ k} + \frac{n \cdot (m a \mod 2^k)}{2^k} < 2n</math>
- <math> a - \left(\frac{m a - (m a \mod 2^k)}{2^k}\right)\cdot n < 2n</math>
- <math> a - \left\lfloor\frac{m a}{2 ^ k}\right\rfloor\cdot n < 2n</math>
- <math> a - q n < 2n</math>
- <math>r < 2n</math>
Приведение Барретта к нескольким машинным словам
Основной причиной для Баррета обратиться к приведению была работа с реализацией алгоритма RSA, где значения чисел почти наверняка выйдут за границы машинного слова. В этой ситуации Барретт представил алгоритм, который аппроксимирует числа, размещённые в нескольких машинных словах. Детали см. в разделе 14.3.3 книги Handbook of Applied CryptographyШаблон:Sfn.
См. также
- Алгоритм Монтгомери является другим алгоритмом, похожим на алгоритм Барретта.
Примечания
Литература
