In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett. A naive way of computing

$ c = a \times b \pmod n. \, $

would be to use a fast division algorithm. Barrett reduction and Montgomery reduction are algorithms designed to optimize this operation.

Sources Edit

Community content is available under CC-BY-SA unless otherwise noted.