Barrett Reduction

Barrett reduction allows us to quickly calculate the quotient

$q$ and reminder

$r$ of

$a(\mathrm{mod}n)$, i.e.

$a=q\cdot n+r,0\le 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\to a,k_1\to r,k_2\to q,\lambda \to 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\le a<{\beta }^2$,

$\beta /2<n<\beta$.

$$\begin{gathered} 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}) \end{gathered}$$
Proof
It's easy to see

$r(\mathrm{mod}n)=a(\mathrm{mod}n)$. We just need to prove

$0\le r<2\cdot n$ (value of

$r$ before while loop).

$$\begin{gathered} q\le \frac{a\cdot I}{{\beta }^2}\le \frac{a\cdot {\beta }^2}{n\cdot {\beta }^2}⟹r\ge 0 \\ I>{\beta }^2/n-1⟹I\cdot n>{\beta }^2-n \\ q>\frac{a\cdot I}{{\beta }^2}-1⟹{\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 \end{gathered}$$

We prove a general algorithm.
Algorithm 2
Assume

$0\le a<{\beta }^2$,

$\beta /2<n<\beta$.

$$\begin{gathered} I=\lfloor {\beta }^2/n\rfloor \\ a=a_1\cdot \gamma +a_2,a_1=\lfloor a/\gamma \rfloor ,a_2=a(\mathrm{mod}\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}) \end{gathered}$$
Proof
(In general, algorithm holds as long as

$\frac{a_0\cdot I}{{\beta }^2}\le 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\le q_0\le \lfloor \frac{a_1\cdot \gamma \cdot I}{{\beta }^2}+k\rfloor =q+k$$
By Algorithm 1, we have

$a-q\cdot n\le 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\le 1$. Thus

$r<(2+k)\cdot n=3\cdot n$.

Reference

Faster Point Multiplication on Elliptic Curves
with Efficient Endomorphisms
Modern Computer Arithmetic

tags: public