Interested Article - Алгоритм Барретта
![](/images/006/454/6454786/1.jpg?rand=596631)
![](https://cdn.wafarin.com/avatars/0f65015d6407a6165630a4250ff4a4c5.jpg)
- 2020-01-25
- 1
Алгоритм Барретта — это алгоритм приведения, который в 1986 году предложил П. Д. Барретт . Обычный способ вычисления
использовал бы быстрый алгоритм деления . Приведение Баррета разработано для оптимизации этой операции путём замены делений на умножения в предположении, что является постоянной величиной, а .
Основная идея
Пусть будет обратным числом для как число с плавающей запятой . Тогда
где означает округление до ближайшего целого в сторону уменьшения . Результат будет точным, если вычислено с достаточной точностью.
Приведение Барретта для одного слова
Барретт первоначально рассматривал целочисленную версию алгоритма выше, когда значения помещаются в машинное слово .
При вычислении с помощью вышеуказанного метода, но с целыми числами, очевидной аналогией было бы деление на :
func reduce(a uint) uint {
q := a / n // Деление в неявной форме возвращает результат, округлённый до ближайшего целого вниз.
return a - q * n
}
Однако деление может стоить дорого и в условиях задач криптографии может не иметь постоянного времени выполнения на некоторых ЦПУ . В этом случае приведение Барретта аппроксимирует значением , поскольку деление на является просто сдвигом вправо и выполняется быстро.
Чтобы вычислить лучшее значение величины для заданного , рассмотрим
Чтобы было целым, нам нужно округлить как-то . Округление до ближайшего целого даст лучшее приближение, но может привести к тому, что будет больше , что может привести к обнулению. Поэтому обычно используется .
Теперь мы можем аппроксимировать функцию выше так:
func reduce(a uint) uint {
q := (a * m) >> k // ">> k" означает сдвиг на k позиций.
return a - q * n
}
Однако, поскольку
, значение
q
в этой функции может оказаться слишком мало, а тогда
a
гарантированно будет только в интервале
, а не в
, как обычно требуется. Вычитание по условию может исправить ситуацию:
func reduce(a uint) uint {
q := (a * m) >> k
a -= q * n
if n <= a {
a -= n
}
return a
}
Поскольку является лишь приближением, следует рассматривать правильные границы . Ошибка приближения к равна
Тогда ошибка значения
q
равна
. Поскольку
, то приведение будет верным, поскольку
. Функция приведения может не сразу дать неверный ответ при
, но границы
следует соблюдать, чтобы обеспечить правильный ответ в общем случае.
При выборе бо́льших значений область значений , для которых приведение верно, может быть увеличена, но бо́льшие значения могут вызвать проблемы переполнения в другом месте.
Пример
Рассмотрим случай при работе с 16-битными целыми числами.
Наименьшее имеющее смысл значение равно , поскольку при приведение будет верно для значений, которые уже минимальны! Для значения семь . Для значения восемь . Тогда значение не даёт никаких преимуществ, поскольку приближение в этом случае ( ) будет тем же самым, что и для . Для мы получаем , что является лучшим приближением.
Теперь рассмотрим границы входных данных для и . В первом случае , так что из вытекает . Поскольку число целое, эффективное максимальное значение равно 478. (На самом деле функция будет работать со значениями вплоть до 504.)
Если мы возьмём , то и тогда максимальное значение равно 7387. (Функция будет работать до значения 7473.)
Следующее значение , которое приводит к лучшему приближению, равно 13, что даёт . Однако заметим, что промежуточное значение при вычислениях приведёт к переполнению 16-битного значения, когда , так что в этой ситуации работает лучше.
Доказательство для границ для конкретного k
Пусть будет наименьшим целым, таким что . Возьмём в качестве приемлемого значения в равенствах выше. Как и в выше приведённом коде, положим
- и
- .
Поскольку осуществляется округление до целого вниз , является целым числом и . Также, если , то . В этом случае переписываем отрывок кода выше:
Доказательство неравенства :
Если , то
Поскольку независимо от , отсюда следует, что
Приведение Барретта к нескольким машинным словам
Основной причиной для Баррета обратиться к приведению была работа с реализацией алгоритма RSA , где значения чисел почти наверняка выйдут за границы машинного слова. В этой ситуации Барретт представил алгоритм, который аппроксимирует числа, размещённые в нескольких машинных словах. Детали см. в разделе 14.3.3 книги Handbook of Applied Cryptography .
См. также
- Алгоритм Монтгомери является другим алгоритмом, похожим на алгоритм Барретта.
Примечания
- , с. 311–323.
- .
Литература
- 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 : .
- Alfred Menezes, Paul Oorschot, Scott Vanstone. . — 1997. — ISBN 0-8493-8523-7 .
- Bosselaers A., Govaerts R., Vandewalle J. // 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. // 18th IEEE Symposium on Computer Arithmetic(ARITH'07). — 2007. — С. 225–9. — ISBN 978-0-7695-2854-0 . — doi : .
![](https://cdn.wafarin.com/avatars/0f65015d6407a6165630a4250ff4a4c5.jpg)
- 2020-01-25
- 1