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

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

[math]\displaystyle{ c = a \,\bmod\, n \, }[/math]

использовал бы быстрый алгоритм деления. Приведение Баррета разработано для оптимизации этой операции путём замены делений на умножения в предположении, что [math]\displaystyle{ n }[/math] является постоянной величиной, а [math]\displaystyle{ a\lt n^2 }[/math].

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

Пусть [math]\displaystyle{ s=1/n }[/math] будет обратным числом для [math]\displaystyle{ n }[/math] как число с плавающей запятой. Тогда

[math]\displaystyle{ a \,\bmod\, n = a-\lfloor a s\rfloor n, }[/math]

где [math]\displaystyle{ \lfloor x \rfloor }[/math] означает округление до ближайшего целого в сторону уменьшения. Результат будет точным, если [math]\displaystyle{ s }[/math] вычислено с достаточной точностью.

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

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

При вычислении [math]\displaystyle{ a \,\bmod\, n }[/math] с помощью вышеуказанного метода, но с целыми числами, очевидной аналогией было бы деление на [math]\displaystyle{ n }[/math]:

func reduce(a uint) uint {
    q := a / n  // Деление в неявной форме возвращает результат, округлённый до ближайшего целого вниз.
    return a - q * n
}

Однако деление может стоить дорого и в условиях задач криптографии может не иметь постоянного времени выполнения на некоторых ЦПУ. В этом случае приведение Барретта аппроксимирует [math]\displaystyle{ 1/n }[/math] значением [math]\displaystyle{ m/2^k }[/math], поскольку деление на [math]\displaystyle{ 2^k }[/math] является просто сдвигом вправо и выполняется быстро.

Чтобы вычислить лучшее значение величины [math]\displaystyle{ m }[/math] для заданного [math]\displaystyle{ 2^k }[/math], рассмотрим

[math]\displaystyle{ \frac{m}{2^k} = \frac{1}{n} \;\Longleftrightarrow\; m = \frac{2^k}{n} }[/math]

Чтобы [math]\displaystyle{ m }[/math] было целым, нам нужно округлить как-то [math]\displaystyle{ {2^k}/{n} }[/math]. Округление до ближайшего целого даст лучшее приближение, но может привести к тому, что [math]\displaystyle{ m/2^k }[/math] будет больше [math]\displaystyle{ 1/n }[/math], что может привести к обнулению. Поэтому обычно используется [math]\displaystyle{ m = \lfloor {2^k}/{n} \rfloor }[/math].

Теперь мы можем аппроксимировать функцию выше так:

func reduce(a uint) uint {
    q := (a * m) >> k // ">> k" означает сдвиг  на k позиций.
    return a - q * n
}

Однако, поскольку [math]\displaystyle{ m/2^k \leqslant 1/n }[/math], значение q в этой функции может оказаться слишком мало, а тогда a гарантированно будет только в интервале [math]\displaystyle{ [0, 2n) }[/math], а не в [math]\displaystyle{ [0, n) }[/math], как обычно требуется. Вычитание по условию может исправить ситуацию:

func reduce(a uint) uint {
    q := (a * m) >> k
    a -= q * n
    if n <= a {
        a -= n
    }
  return a
}

Поскольку [math]\displaystyle{ m/2^k }[/math] является лишь приближением, следует рассматривать правильные границы [math]\displaystyle{ a }[/math]. Ошибка приближения к [math]\displaystyle{ 1/n }[/math] равна

[math]\displaystyle{ e = \frac{1}{n} - \frac{m}{2^k} }[/math]

Тогда ошибка значения q равна [math]\displaystyle{ ae }[/math]. Поскольку [math]\displaystyle{ ae \lt 1 }[/math], то приведение будет верным, поскольку [math]\displaystyle{ a \lt 1/e }[/math]. Функция приведения может не сразу дать неверный ответ при [math]\displaystyle{ a \geqslant 1/e }[/math], но границы [math]\displaystyle{ a }[/math] следует соблюдать, чтобы обеспечить правильный ответ в общем случае.

При выборе бо́льших значений [math]\displaystyle{ k }[/math] область значений [math]\displaystyle{ a }[/math], для которых приведение верно, может быть увеличена, но бо́льшие значения [math]\displaystyle{ k }[/math] могут вызвать проблемы переполнения в другом месте.

Пример

Рассмотрим случай [math]\displaystyle{ n = 101 }[/math] при работе с 16-битными целыми числами.

Наименьшее имеющее смысл значение [math]\displaystyle{ k }[/math] равно [math]\displaystyle{ k = 7 }[/math], поскольку при [math]\displaystyle{ 2^k \lt n }[/math] приведение будет верно для значений, которые уже минимальны! Для значения семь [math]\displaystyle{ m = \lfloor 2^k / n \rfloor = \lfloor 128 / 101 \rfloor = 1 }[/math]. Для значения восемь [math]\displaystyle{ m = \lfloor 256 / 101 \rfloor = 2 }[/math]. Тогда значение [math]\displaystyle{ k = 8 }[/math] не даёт никаких преимуществ, поскольку приближение [math]\displaystyle{ 1/101 }[/math] в этом случае ([math]\displaystyle{ 2/256 }[/math]) будет тем же самым, что и для [math]\displaystyle{ 1/128 }[/math]. Для [math]\displaystyle{ k = 9 }[/math] мы получаем [math]\displaystyle{ m = \lfloor 512 / 101 \rfloor = 5 }[/math], что является лучшим приближением.

Теперь рассмотрим границы входных данных для [math]\displaystyle{ k = 7 }[/math] и [math]\displaystyle{ k = 9 }[/math]. В первом случае [math]\displaystyle{ e = 1/n - m/2^k = 1/101 - 1/128 = 27/12928 }[/math], так что из [math]\displaystyle{ a \lt 1/e }[/math] вытекает [math]\displaystyle{ a \lt 478{,}81 }[/math]. Поскольку число [math]\displaystyle{ a }[/math] целое, эффективное максимальное значение равно 478. (На самом деле функция будет работать со значениями вплоть до 504.)

Если мы возьмём [math]\displaystyle{ k = 9 }[/math], то [math]\displaystyle{ e = 1/101 - 5/512 = 7/51712 }[/math] и тогда максимальное значение [math]\displaystyle{ a }[/math] равно 7387. (Функция будет работать до значения 7473.)

Следующее значение [math]\displaystyle{ k }[/math], которое приводит к лучшему приближению, равно 13, что даёт [math]\displaystyle{ 81/8192 }[/math]. Однако заметим, что промежуточное значение [math]\displaystyle{ ax }[/math] при вычислениях приведёт к переполнению 16-битного значения, когда [math]\displaystyle{ 810 \leqslant a }[/math], так что [math]\displaystyle{ k = 7 }[/math] в этой ситуации работает лучше.

Доказательство для границ для конкретного k

Пусть [math]\displaystyle{ k_0 }[/math] будет наименьшим целым, таким что [math]\displaystyle{ 2^{k_0}\gt n }[/math]. Возьмём [math]\displaystyle{ k_0+1 }[/math] в качестве приемлемого значения [math]\displaystyle{ k }[/math] в равенствах выше. Как и в выше приведённом коде, положим

• [math]\displaystyle{ q = \left\lfloor \frac{m a}{2^k} \right\rfloor }[/math] и
• [math]\displaystyle{ r = a - q n }[/math].

Поскольку осуществляется округление до целого вниз, [math]\displaystyle{ q }[/math] является целым числом и [math]\displaystyle{ r \equiv a \pmod{n} }[/math]. Также, если [math]\displaystyle{ a \lt 2 ^ k }[/math], то [math]\displaystyle{ r \lt 2n }[/math]. В этом случае переписываем отрывок кода выше:

[math]\displaystyle{ a \,\bmod\, n = \begin{cases} r & \text{если } r\lt n \\ r-n & \text{иначе} \end{cases} }[/math]

Доказательство неравенства [math]\displaystyle{ r \lt 2n }[/math]:

Если [math]\displaystyle{ a \lt 2 ^ k }[/math], то

[math]\displaystyle{ \frac{a}{2 ^ k} \cdot (2 ^ k \mod n) \lt n }[/math]

Поскольку [math]\displaystyle{ n\cdot\frac{m a \mod 2^k}{2^k} \lt n }[/math] независимо от [math]\displaystyle{ a }[/math], отсюда следует, что

[math]\displaystyle{ \frac{a\cdot (2 ^ k \mod n)}{2 ^ k} + n\cdot\frac{m a \mod 2^k}{2^k} \lt 2n }[/math]

[math]\displaystyle{ a - \left(a - \frac{a\cdot (2 ^ k \mod n)}{2 ^ k}\right) + \frac{n \cdot (m a \mod 2^k)}{2^k} \lt 2n }[/math]

[math]\displaystyle{ a - \frac{a}{2^k} \cdot \left(2^k - (2^k \mod n)\right) + \frac{n \cdot (m a \mod 2^k)}{2^k} \lt 2n }[/math]

[math]\displaystyle{ 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} \lt 2n }[/math]

[math]\displaystyle{ 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} \lt 2n }[/math]

[math]\displaystyle{ a - \frac{n m a}{2 ^ k} + \frac{n \cdot (m a \mod 2^k)}{2^k} \lt 2n }[/math]

[math]\displaystyle{ a - \left(\frac{m a - (m a \mod 2^k)}{2^k}\right)\cdot n \lt 2n }[/math]

[math]\displaystyle{ a - \left\lfloor\frac{m a}{2 ^ k}\right\rfloor\cdot n \lt 2n }[/math]

[math]\displaystyle{ a - q n \lt 2n }[/math]

[math]\displaystyle{ r \lt 2n }[/math]

Приведение Барретта к нескольким машинным словам

Основной причиной для Баррета обратиться к приведению была работа с реализацией алгоритма RSA, где значения чисел почти наверняка выйдут за границы машинного слова. В этой ситуации Барретт представил алгоритм, который аппроксимирует числа, размещённые в нескольких машинных словах. Детали см. в разделе 14.3.3 книги Handbook of Applied Cryptography.

См. также

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