# Barrett Reduction
Barrett reduction allows us to quickly calculate the quotient $q$ and reminder $r$ of $a \pmod n$, i.e. $a = q\cdot n + r, 0\leq r<n$.

## GLV
One of the use case is in GLV decomposition. For simplicity, we consider all the integers below are less than $2^{256}$. We want to decompose $k=k_1+k_2\cdot\lambda$ with both $k_1, k_2$ are small. Here is the correspondence
$$k\rightarrow a,k_1\rightarrow r, k_2\rightarrow q, \lambda\rightarrow n$$

When $\lambda$ is $128$ bit, we can use Barrett reduction to derive $k_1, k_2$ with $k_1<2^{128}, k_2<2^{128}$.

In the glv paper, it considers more general case where $\lambda$ might not be $128$ bit and hence use lattice based algorithm to derive small $k_1, k_2$ (which might not less than $2^{128}$)

## Barrett Reduction Algorithm
In practice, We use $\beta=2^{128}$ (or $2^c$ in general) for efficient calculation. For BLS12-381 curve, `n=lambda=0xAC45A4010001A40200000000FFFFFFFF` is exaclty $128$ bit, hence satisfy algorithm's assumption.

**Algorithm 1**
Assume $0\leq a<\beta^2$, $\beta/2<n<\beta$.
$$I=\lfloor\beta^2/n\rfloor\\
q=\lfloor \frac{a\cdot I}{\beta^2}\rfloor\\
r=a-q\cdot n\\
\text{while r>=n}: r=r-n; q=q+1 (\text{at most 1 times})$$
**Proof**
It's easy to see $r\pmod n = a\pmod n$. We just need to prove $0\leq r < 2\cdot n$ (value of $r$ before while loop).
$$q\leq \frac{a\cdot I}{\beta^2}\leq \frac{a\cdot \beta^2}{n\cdot \beta^2}\implies r\geq 0\\
I>\beta^2/n-1\implies I\cdot n>\beta^2 -n\\
q>\frac{a\cdot I}{\beta^2}-1\implies \beta^2 q>a\cdot I-\beta^2\\
\beta^2\cdot q\cdot n>a\cdot I\cdot n-\beta^2\cdot n>a\cdot\beta^2-a\cdot n-\beta^2\cdot n>\beta^2(a-2\cdot n)\\
a-q\cdot n < 2\cdot n$$

We prove a general algorithm.
**Algorithm 2**
Assume $0\leq a<\beta^2$, $\beta/2<n<\beta$.
$$I=\lfloor\beta^2/n\rfloor\\
a=a_1\cdot \gamma + a_2, a_1=\lfloor a/\gamma\rfloor,a_2=a \pmod \gamma\\
q=\lfloor\frac{a_1\cdot\gamma\cdot I}{\beta^2}\rfloor,k=\lceil\frac{a_0\cdot I}{\beta^2}\rceil\\
r=a-q\cdot n\\
\text{while r>=n}: r=r-n; q=q+1 (\text{at most } 2+k \text{ times})$$
**Proof**
(In general, algorithm holds as long as $\frac{a_0\cdot I}{\beta^2}\leq k$ for some integer $k$).
Define $q_0=\lfloor \frac{a\cdot I}{\beta^2}\rfloor=\lfloor\frac{a_1\cdot\gamma\cdot I}{\beta^2}+\frac{a_0\cdot I}{\beta^2}\rfloor$, we have
$$q\leq q_0\leq \lfloor\frac{a_1\cdot\gamma\cdot I}{\beta^2}+k\rfloor=q+k$$
By Algorithm 1, we have $a-q\cdot n\leq a-(q_0-k)\cdot n=a-q_0\cdot n+k\cdot n<(2+k)\cdot n$

**Example 1** If we choose $\gamma=\beta$, we have $a_0\cdot I/\beta^2<\beta\cdot 2\beta/\beta^2=2$, we derive the algorithm in section 2.4.1 in Modern Computer Arithmetic (reference), where $r<4\cdot n$.

**Example 2** If we choose $\gamma=\beta/2$, we have $a_0\cdot I/\beta^2<\gamma\cdot 2\beta/\beta^2\leq 1$. Thus $r<(2+k)\cdot n=3\cdot n$.

## Reference
[Faster Point Multiplication on Elliptic Curves
with Efficient Endomorphisms](https://www.iacr.org/archive/crypto2001/21390189.pdf)
[Modern Computer Arithmetic](http://www.loria.fr/~zimmerma/mca/mca-cup-0.5.7.pdf)

###### tags: `public`