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

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

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

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

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

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

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

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

При вычислении с помощью вышеуказанного метода, но с целыми числами, очевидной аналогией было бы деление на :

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

См. также

Примечания

Литература

  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.