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

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

Алгоритм

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

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

Обчислення залишку за модулем:

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

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

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

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

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

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