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

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

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

Діленння:

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

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

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