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

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

Алгоритм

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

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

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

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

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

Примітки

1. Barrett, P. (2006). Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. Т. 263. с. 311—323. doi:10.1007/3-540-47721-7_24. ISBN .
2. Кабір Лабіб Ахмед (11.06.2022). Метод прискореного модулярного множення для систем криптографічного захисту даних (PDF). Дипломний проєкт. Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського».