## 5 Implementation Details of Curve Arithmetic
### Scalar Decomposition  
In this subsection, we describe the scalar decomposition method for a random integer \(k\in[1,r]\) and corresponding multi-scalars \((k_{0},k_{1},k_{2},k_{3})\in\mathbb{Z}^{4}\) such that \(k\equiv k_{0}+k_{1}\phi+k_{2}\psi+k_{3}\psi\phi\) as \(\max(k_{i})<Cr^{1/4}\) for \(0\leq i\leq 3\) and some explicit constant \(C>0\). We assume that \(\phi\equiv\lambda\pmod{r}\) and \(\psi\equiv\mu\pmod{r}\). Let \(F\) be a four-dimensional GLV-GLS reduction map defined by  
\[F:\mathbb{Z}^{4} \to\mathbb{Z}/n,\] \[(k_{0},k_{1},k_{2},k_{3}) \mapsto k_{0}+k_{1}\lambda+k_{2}\mu+k_{3}\lambda\mu\pmod{r}.\]  
Let \(B=(b_{0},b_{1},b_{2},b_{3})\) be a \(4\times 4\) matrix consisting of four linearly independent vectors with \(\max_{i}|b_{i}|\leq Cr^{1/4}\). Then, for any \(k\in[1,r-1]\), the decomposition method computes \((\alpha_{0},\alpha_{1},\alpha_{2},\alpha_{3})\in\mathbb{Q}^{4}\) and computes the multi-scalars  
\[(k_{0},k_{1},k_{2},k_{3})=(k,0,0,0)-\sum_{i=0}^{3}\lceil\alpha_{i}\rfloor \cdot b_{i},\]  
where \(\lceil\ \rfloor\) represents a rounding operation. There are two typical methods for decomposing a scalar: the Babai rounding method [39] and division in a ring \(\mathbb{Z}[\phi]\) method, where \(\phi\) is an efficiently computable endomorphism [40]. In [14], lattice reduction algorithms based on [PERSON]'s algorithms were proposed for finding a uniform basis. The first step is finding [PERSON]'s GCD in \(\mathbb{Z}\) and the second step is using the [PERSON]'s algorithm in \(\mathbb{Z}[i]\). We utilize these two algorithms to find four linearly independent vectors \(b_{0},b_{1},b_{2},b_{3}\in\ker F\), where the rectangle norms \(<51.5\sqrt{2}r^{1/4}\). The coordinates of these vectors utilize the scalar decomposition. Additionally, the relationships of four vectors can reduce the number of fixed constants. Two vectors \(b_{0}=(b_{0}[0],b_{0}[1],b_{0}[2],b_{0}[3])\) and \(b_{1}=(b_{1}[0],b_{1}[1],b_{1}[2],b_{1}[3])\) can represent the remaining vectors \(b_{2}=(-b_{0}[2],-b_{0}[3],b_{0}[0],b_{0}[1])\) and \(b_{3}=(-b_{1}[2],-b_{1}[3],b_{1}[0],b_{1}[1])\). Let \(B_{i}\) be the \(4\times 4\) matrix formed by replacing \(b_{i}\) in \(B\) with the vector \((1,0,0,0)\). We then define four precomputed constants \(h_{i}=\det(B_{i})\), where \(0\leq i\leq 3\). The four-dimensional decomposition computes \(\alpha_{i}=\lceil\frac{k_{i}! }{r}\rfloor\) using four integer multiplication, four integer divisions, and four rounding operations. [PERSON] et al. [17] introduced an efficient rounding method for eliminating integer divisions. This method chooses an integer \(m\) such that \(r<2^{m}\), and precomputes the fixed constants \(l_{i}=\lceil\frac{h_{i}}{r}\rceil\cdot 2^{m}\rfloor\). Then, \(\alpha_{i}\) can be computed by \(\lceil\frac{k_{i}! }{2^{m}}\rfloor\), where the division by \(2^{m}\) can be computed by a shift operation. The four-dimensional decomposition of a random scalar \(k\) using curve Ted127-glv4 can be computed as follows:  
\[k_{0} =k-\alpha_{0}\cdot b_{0}[0]-\alpha_{1}\cdot b_{1}[0]+\alpha_{2} \cdot b_{0}[2]+\alpha_{3}\cdot b_{1}[2],\] \[k_{1} =-\alpha_{0}\cdot b_{0}[1]-\alpha_{1}\cdot b_{1}[1]+\alpha_{2} \cdot b_{0}[3]+\alpha_{3}\cdot b_{1}[3],\] \[k_{2} =-\alpha_{0}\cdot b_{0}[2]-\alpha_{1}\cdot b_{1}[2]-\alpha_{2} \cdot b_{0}[0]-\alpha_{3}\cdot b_{1}[0],\] \[k_{3} =-\alpha_{0}\cdot b_{0}[3]-\alpha_{1}\cdot b_{1}[3]-\alpha_{2} \cdot b_{0}[1]-\alpha_{3}\cdot b_{1}[1].\]  
However, Ref. [21] reported that this method yields the correct answer and \(\lceil\frac{k_{i}!}{r}\rfloor-1\). They also reported that a large size of \(m\) decreases the probability of a round-off error. Because the multi-scalars \((k_{0},k_{1},k_{2},k_{3})\) lie between \(-2^{63}\) and \(2^{63}\), all coordinates are both positive and negative. Signed multi-scalars require additional cost to compute scalar multiplication. [PERSON] and [PERSON] [21] demonstrated the offset vectors such that all coordinates of the multi-scalars were always positive to simplify scalar recoding.