# Barrett reduction

## From Wikipedia, the free encyclopedia

In modular arithmetic, **Barrett reduction** is a reduction algorithm introduced in 1986 by P.D. Barrett.[1]

A naive way of computing

- $c=a\,{\bmod {\,}}n\,$

would be to use a fast division algorithm. Barrett reduction is an algorithm designed to optimize this operation assuming $n$ is constant, and $a<n^{2}$, replacing divisions by multiplications.

Historically, for values $a,b<n$, one computed $ab\,{\bmod {\,}}n\,$ by applying Barrett reduction to the full product $ab$. Recently, it was shown that the full product is unnecessary if we can perform precomputation on one of the operands.[2][3]

Oops something went wrong: