Crypto Wiki

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

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


  • 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]