Barrett reduction

In modular arithmetic, Barrett reduction is an algorithm designed to optimize the calculation of ${\displaystyle a\,{\bmod {\,}}n\,}$ without needing a fast division algorithm. It replaces divisions with multiplications, and can be used when ${\displaystyle n}$ is constant and ${\displaystyle a<n^{2}}$. It was introduced in 1986 by P.D. Barrett.

Historically, for values ${\displaystyle a,b<n}$, one computed ${\displaystyle ab\,{\bmod {\,}}n\,}$ by applying Barrett reduction to the full product ${\displaystyle ab}$. In 2021, Becker et al. showed that the full product is unnecessary if we can perform precomputation on one of the operands.