Barrett Reduction
,The primary goal of Barrett reduction is to perform modular reduction efficiently. The standard calculation, , involves a division (), which can be slow. Barrett reduction aims to replace this division.
The Core Idea
Barrett reduction uses multiplications, subtractions, and bit shifts (fast division by powers of 2) instead of a general division. It achieves this using a precomputed value based on the modulus to approximate the quotient value .
How it works
Setup and Precomputation
Suppose we are working with integers base . (Typically in computers). Consider an integer such that . Often, is chosen such that is roughly (e.g., if fits in bits, is common). Now, we precompute the value :
which acts as a scaled approximation of division by .
Approximating the Quotient
The true remainder is , where the true quotient is . So in Barrett's method we would like to estimate without dividing by .
Consider the product . Substituting the definition of , we get:
Dividing both sides by (which is a right shift by if ):
This gives us the approximation to :
Let's denote this approximation as :
How Close is the Approximation?
Notice that we can write for some remainder . Solving for , we have. Replacing for the equation, we get:
Comparing to , the difference depends on the term , which is small if is large enough relative to .
For example, if , then which gives us a nice tight bound so we need only 1 subtraction at the worst case. If we choose a smaller such that , can get as low as , but typically we choose a large .
Final Reduction Algorithm
Precomputation (once for fixed ):
Choose (e.g., ). We assume .
Calculate .
Reduction (for each ):
Calculate (intermediate product might need bits; often only the higher bits are needed since we do a bit-shift afterwards).
Calculate .
Correction: while ,
Cost Analysis of Modular Multiplication
Single-Precision case
Suppose the modulus has bit width of . Then, the cost looks like:
Computing multiplication of bitwidth .
Computing multiplication of bitwidth .
Computing multiplication of bitwidth .
TODO(BATZORIG ZORIGOO): add multi-precision case
Written by BATZORIG ZORIGOO from A41
Last updated