# GLV Multiplication

This note explains the scalar decomposition step on the efficient EC multiplication algorithm proposed in this [article](https://www.iacr.org/archive/crypto2001/21390189.pdf).

Some implementations of the algorithm:

- [Python implementation](https://github.com/demining/CryptoDeepTools/blob/9dfd594126117e07fc51a77a7c613180eb662f18/07EndomorphismSecp256k1/endomorphism.py#L145)
- [Go implementation](https://github.com/ConsenSys/gnark-crypto/blob/8f7ca09273c24ed9465043566906cbecf5dcee91/ecc/utils.go#L141)
- [Rust implementation](https://github.com/privacy-scaling-explorations/halo2curves/pull/24)
- In-circuit implementation in halo2wrong [PR](https://github.com/davidnevadoc/halo2wrong/tree/test/endo-scalar-mul)

Here is a good explanation of the whole algorithm along with an implementation:
[bitcoin secp impl](https://github.com/bitcoin-core/secp256k1/blob/1b21aa51752958138aab3f750afdb7549f82ca89/src/scalar_impl.h#L75).

$\newcommand{sF}{\mathbb{F}_n}$
$\newcommand{zz}{\mathbb{Z}\times\mathbb{Z}}$
$\newcommand{g}{\gamma}$
$\newcommand{b}{\beta}$
## Scalar decomposition

The following homomorphism is defined:
$$
\begin{aligned}
f: \zz & \to \sF \\
(i,j) & \mapsto i + \lambda j
\end{aligned}
$$
where $\lambda$ is the endoscalar of the curve.

The problem of decomposing a given scalar $k \in \sF$ consists of finding a pair $(k_1, k_2) \in \zz$ s.t. $f(k_1, k_2) = k$.
The key of the problem is to find the shortest vector possible that satisfies this relation.

First we precompute 2 vectors $\g, \b$ such that $f(\g) = f(\b) = 0$.
The problem now turns into finding a vector $v$ in the lattice generated by $[\b, \g]$ that is close to $(k, 0)$.
With such vector $v$ we easily compute
$$
(k_1, k_2) := (k, 0) - v
$$
which is short, ($\leq \max{(\lVert\b\rVert, \lVert\g\rVert)}$)
and satisfies our fist condition, since
$$
f((k_1, k_2)) = f((k, 0)) - f(v) = k
$$

Let $v := t_1 \cdot \b + t_2 \cdot \g$.
We solve the system
$$
\begin{pmatrix}
\b_1 & \g_1 \\
\b_2 & \g_2
\end{pmatrix}
\begin{pmatrix}
t_1 \\
t_2
\end{pmatrix} =
\begin{pmatrix}
k \\
0
\end{pmatrix}
$$

$$
\begin{pmatrix}
t_1 \\
t_2
\end{pmatrix} =
\frac{1}{d}
\begin{pmatrix}
\g_2 & - \g_1 \\
-\b_2 & \b_1
\end{pmatrix}
\begin{pmatrix}
k \\
0
\end{pmatrix}
$$
where $d$ is the determinant of the $[\g, \b]$ matrix.

We get
$$
\begin{align}
t_1 =& \frac{1}{d} \cdot k \cdot \g_2 \\
t_2 =& -\frac{1}{d} \cdot k \cdot \b_2
\end{align}
$$

Due to the determinant division, these values lie on $\mathbb{Q}$. We round them to their closest integer value to obtain a point in the $[\b, \g]$-generated lattice. Now we have:

$$
\begin{pmatrix}
k_1 \\
k_2
\end{pmatrix} =
\begin{pmatrix}
k \\
0
\end{pmatrix} -
\begin{pmatrix}
\b_1 & \g_1 \\
\b_2 & \g_2
\end{pmatrix}
\begin{pmatrix}
\lfloor t_1 \rceil \\
\lfloor t_2 \rceil
\end{pmatrix}
$$

We will only compute $-k_2$:
$$
-k_2 = \b_2 \cdot \lfloor t_1 \rceil + \g_2 \cdot \lfloor t_2 \rceil
$$
Then we use the original definition $k = k_1 + \lambda k_2$ to compute $k_1$:
$$
k_1 = k + \lambda (-k_2)
$$

Finally, instead of returning $k_1, k_2$, this algorithm will return $-k_i$ or $k_i$ choosing the one with a lower absolute value. The choice is indicated with some flags. The output then is `(k_1, k_1_neg, k_2, k_2_neg)`.