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
would be to use a fast division algorithm. Barrett reduction is an algorithm designed to optimize this operation assuming is constant, and , replacing divisions by multiplications.
Historically, for values , one computed by applying Barrett reduction to the full product . Recently, it was shown that the full product is unnecessary if we can perform precomputation on one of the operands.[2][3]