Content deleted Content added
Message for previous changes: add new insights of Barrett and Montgomery multiplications |
m task, replaced: Advances in Cryptology — → Advances in Cryptology – (2) |
||
Line 1:
In [[modular arithmetic]], '''Barrett reduction''' is a reduction [[algorithm]] introduced in 1986 by P.D. Barrett.<ref>{{Cite book | last1 = Barrett | first1 = P. | chapter = Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor | doi = 10.1007/3-540-47721-7_24 | title = Advances in Cryptology
▲In [[modular arithmetic]], '''Barrett reduction''' is a reduction [[algorithm]] introduced in 1986 by P.D. Barrett.<ref>{{Cite book | last1 = Barrett | first1 = P. | chapter = Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor | doi = 10.1007/3-540-47721-7_24 | title = Advances in Cryptology — CRYPTO' 86 | series = Lecture Notes in Computer Science | volume = 263 | pages = 311–323 | year = 1986 | isbn = 978-3-540-18047-0 }}</ref>
A naive way of computing
Line 20 ⟶ 19:
:<math> a \, \text{mod}^{\left[\,\right]} \, n = a - \left[a / n\right] n </math>.
Common choices of <math>\left[\,\right]</math> are [[floor function|floor]], [[ceiling function|ceiling]], and [[rounding]] functions.
Generally, Barrett multiplication starts by specifying two integer approximations <math>\left[\,\right]_0, \left[\,\right]_1</math> and computes a reasonably close approximation of <math>ab \, \bmod \, n</math> as
Line 117 ⟶ 115:
Generally, for integer approximations <math>\left[\,\right]_0, \left[\,\right]_1</math>,
we have
:<math>
Line 161 ⟶ 159:
It is also possible to use Barrett algorithm for polynomial division, by reversing polynomials and using X-adic arithmetic.<ref>{{Cite web |title=Barrett reduction for polynomials |url=https://www.corsix.org/content/barrett-reduction-polynomials |access-date=2022-09-07 |website=www.corsix.org}}</ref>
== See also ==
Line 171 ⟶ 170:
== Sources ==
{{refbegin}}
*{{cite book |last1=Bosselaers |first1=A. |first2=R. |last2=Govaerts |first3=J. |last3=Vandewalle |chapter=Comparison of Three Modular Reduction Functions |title=Advances in Cryptology
*{{cite book |first1=W. |last1=Hasenplaugh |first2=G. |last2=Gaubatz |first3=V. |last3=Gopal |chapter-url=http://www.acsel-lab.com/arithmetic/arith18/papers/ARITH18_Hasenplaugh.pdf |chapter=Fast Modular Reduction |title=18th IEEE Symposium on Computer Arithmetic(ARITH'07) |year=2007 |isbn=978-0-7695-2854-0 |pages=225–229 |doi=10.1109/ARITH.2007.18|s2cid=14801112 }}
{{refend}}
| |||