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

Редукція Барретта — алгоритм обчислення лишку за модулем, запропонований Барреттом 1986 року.
Наївний спосіб обчислення виразу $c=a\,{\bmod {\,}}n\,$ полягає в застосуванні ділення з остачею, яке в довгій арифметиці є складною операцією (зазвичай, зводиться до кількох операцій множення та віднімання). Алгоритм Барретта розроблено для оптимізації цієї операції за умов $a<n^{2}$ та сталого $n$. У ньому ділення замінено двома множеннями, зсувом та відніманням.

Алгоритм

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

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

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

Застосування

Редукція Барретта застосовується для обчислення залишку за модулем в операціях модульного множення й модульної експоненти, які широко застосовуються в системах криптографічного захисту інформації.