Barrett reduction

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

• P.D. Barrett, "Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor," Advances in Cryptology — CRYPTO'86, Springer, 1986. [1]
• Chapter 14 of Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7.
• Bosselaers, et. al., "Comparison of Three Modular Reduction Functions," Advances in Cryptology-Crypto'93, 1993. [2]