Алгоритм Барретта — это алгоритм приведения, предназначенный для оптимизации вычисления выражения без использования быстрого алгоритма деления, заменяющий операции деления на умножения в предположении, что является постоянной величиной, а , предложеный в 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.
См. также Алгоритм Монтгомери является другим алгоритмом, похожим на алгоритм Барретта.
Примечания
Литература
Категория:Компьютерная арифметика Категория:Модульная арифметика