Редукція Барретта

У модульній арифметиці, зведення Барретта — це алгоритм знайдення лишку за модулем запропонований Барреттом у 1986. Наївний спосіб обчислення

$c=a\,{\bmod {\,}}n.\,$

полягає у використанні швидкого алгоритму ділення. Зведення Барретта є алгоритмом спроектованим для оптимізації цієї операції за умов сталості $n$ і $a<n^{2}$ заміняючи ділення на множеннями.

Алгоритм

Попередні обчислення:

1. Нехай $n\in N,n\geq 3$ і $n$ це не степінь 2. (Це необхідно для наступного доведення і, тому що ділення за модулем, що дорівнює степені 2 є тривіальним.)
2. Обрати $k\in N$ таке, що $2^{k}>n.$ (Найменше таке $k$ дорівнює $\left\lfloor \log _{2}n\right\rfloor .$)
3. Обчислимо $r=\left\lfloor {\frac {4^{k}}{n}}\right\rfloor .$ (Це є наш наперед обчислений множник.)

Зведення:

1. Маємо $x\in N$ таке, що $0\leq x<n^{2},$ залишок від ділення на $n$ якого нам потрібно знайти.
2. Обчислюємо $t=x-\left\lfloor {\frac {xr}{4^{k}}}\right\rfloor n.$
3. Якщо $t<n$ тоді повернути $t$ інакше $t-n$. Цей результат дорівнює $x\mod n.$

Доведення правильності

1. Оскільки $n$ не є степенем 2, то ми знаємо, що $4^{k}/n$ не ціле. Отже, $4^{k}/n-1<r<4^{k}/n.$
2. Множення на $x\ (x\geq 0):x(4^{k}/n-1)\leq xr\leq x4^{k}/n.$
3. Ділення на $4^{k}:x/n-x/4^{k}\leq xr/4^{k}\leq x/n.$
4. З того, що $x<n^{2}<4^{k}$ випливає, що $x/4^{k}<1.$ Тому: $x/n-1<xr/4^{k}\leq x/n.$
5. Також: $xn-2<\left\lfloor xn-1\right\rfloor$ і $\left\lfloor xn-1\right\rfloor \leq xr/4^{k}.$ Разом маємо: $xn-2<\left\lfloor xn-1\right\rfloor \leq xr/4^{k}.$
6. Множимо на $n\ (n>0):x-2n<\left\lfloor xr/4^{k}\right\rfloor n\leq x.$
7. Множимо на $-1:-x\leq \left\lfloor xr/4^{k}\right\rfloor n<2n-x.$
8. Додаємо $x:0\leq x-\left\lfloor xr/4^{k}\right\rfloor n<2n.$
9. Очевидно, що $x\equiv x-\left\lfloor xr/4^{k}\right\rfloor n\mod n,$ оскільки $\left\lfloor xr/4^{k}n\right\rfloor$ це число кратне $n.$

Тут ми отримали результат зведення $x$ з діапазону $[0,n^{2})$ до $t$ в діапазоні $[0,2n)$ без зміни конгруентності за модулем $n.$ Останній крок простий, необхідно отримати результат в діапазоні $[0,n).$