46.115.90.113: MathWorld

2013-11-09T20:18:32Z

MathWorld

New page

In [[modular arithmetic]], '''Barrett reduction''' is a reduction [[algorithm]] introduced in 1986 by P.D. Barrett.<ref>{{cite doi|10.1007/3-540-47721-7_24}}</ref> A naive way of computing

:<math>c = a \,\bmod\, n. \, </math>

would be to use a fast [[division algorithm]]. Barrett reduction is an algorithm designed to optimize this operation assuming <math>n</math> is constant, and <math>a<n^2</math>, replacing divisions by multiplications.

== Naive idea ==

Let <math>m=1/n</math> be the inverse of <math>n</math> as a [[floating point]] number. Then

:<math>a \,\bmod\, n = a-\lfloor a m\rfloor n </math> where <math>\lfloor x \rfloor</math> denotes the [[floor function]],
assuming m was computed with sufficient accuracy.

== Barrett algorithm ==

Barrett algorithm is a [[fixed-point]] analog which expresses everything in terms of integers.
Let ''k'' be the smallest integer such that <math>2^k>n</math>. Think of ''n'' as representing the fixed-point number <math> n 2^{-k} </math>.
We precompute m such that <math> m = \lfloor 4^k/n \rfloor</math>. Then ''m'' represents the fixed-point number <math> m 2^{-k} \approx (n 2^{-k})^{-1} </math>.

Let <math>q = \left\lfloor \frac{m a}{4^k} \right\rfloor </math> and <math>r = a - q n</math>.

Clearly <math>a \equiv r \pmod{n}</math>, and if <math>a<n^2</math> then <math>r<2 n </math>.
So
:<math>a \,\bmod\, n = \begin{cases} r & \text{if } r<n \\ r-n & \text{otherwise} \end{cases}</math>

== Barrett algorithm for polynomials ==

It is also possible to use Barrett algorithm for polynomial division, by reversing polynomials
and using X-adic arithmetic.{{clarify|date=January 2014}}

== See also ==

[[Montgomery reduction]] is another similar algorithm.

==References==

{{Reflist}}

== Sources ==
*Chapter 14 of [[Alfred J. Menezes]], Paul C. van Oorschot, and [[Scott A. Vanstone]]. [http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf 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. [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.3779]
*W. Hasenplaugh, G. Gaubatz, V. Gopal, [http://www.acsel-lab.com/arithmetic/html/Hasenplaugh_W.html "Fast Modular Reduction"], ARITH 18

[[Category:Computer arithmetic]]
[[Category:Cryptographic algorithms]]
[[Category:Modular arithmetic]]

Airy zeta function - Revision history

46.115.90.113: MathWorld