## 5 Implementation Details of Curve Arithmetic
### Point Arithmetic  
To enhance the performance of scalar multiplication, the selections of efficient point arithmetic and coordinate system are one of the most crucial subjects. The extended Edwards coordinates of the form \((X:Y:Z:T)\) were proposed by [PERSON] et al., where \(T=XY/Z\)[30]. The extended Edwards coordinates are an extended version of the homogeneous coordinates of the form \((X:Y:Z)\). The identity element is represented by \((0:1:1:0)\) and the negative element of \((X:Y:Z:T)\) is represented by \((-X:Y:Z:-T)\). [PERSON] et al. [30] proposed dedicated addition and doubling formulas that are independent of the curve parameter \(d\). Given \((X_{1}:Y_{1}:Z_{1}:T_{1})\) and \((X_{2}:Y_{2}:Z_{2}:T_{2})\) of distinct points with \(Z_{1}\
eq 0\) and \(Z_{2}\
eq 0\), the ECADD operation \((X_{3}:Y_{3}:Z_{3}:T_{3})=(X_{1}:Y_{1}:Z_{1}:T_{1})+(X_{2}:Y_{2}:Z_{2}:T_{2})\) can be computed as follows:  
\[X_{3} =(X_{1}Y_{2}-Y_{1}X_{2})(T_{1}Z_{2}+Z_{1}T_{2}),\] \[Y_{3} =(Y_{1}Y_{2}+aX_{1}X_{2})(T_{1}Z_{2}-Z_{1}T_{2}),\] \[Z_{3} =(T_{1}Z_{2}-Z_{1}T_{2})(T_{1}Z_{2}-Z_{1}T_{2}),\] \[T_{3} =(Y_{1}Y_{2}+aX_{1}X_{2})(X_{1}Y_{2}-Y_{1}X_{2}).\]Similarly, given \((X_{1}:Y_{1}:Z_{1}:T_{1})\) with \(Z_{1}\
eq 0\), the ECDBL operation \((X_{3}:Y_{3}:Z_{3}:T_{3})=2(X_{1}:Y_{1}:Z_{1}:T_{1})\) can be computed as follows:  
\[X_{3} =2X_{1}Y_{1}(2Z_{1}^{2}-Y_{1}^{2}-aX_{1}^{2}),\] \[Y_{3} =(Y_{1}^{2}+aX_{1}^{2})(Y_{1}^{2}-aX_{1}^{2}),\] \[Z_{3} =2X_{1}Y_{1}(Y_{1}^{2}-aX_{1}^{2}),\] \[T_{3} =(Y_{1}^{2}+aX_{1}^{2})(2Z_{1}^{2}-Y_{1}^{2}-aX_{1}^{2}).\]  
Hamburg [41] proposed extensible coordinates of the form \((X:Y:Z:T_{a}:T_{b})\), where \(T=T_{a}\cdot T_{b}\). The final step of the ECADD and ECDBL operations using extended Edwards coordinates computes \(T=T_{a}\cdot T_{b}\). However, the extensible coordinates store the coordinates \(T\) as \(T_{a}\) and \(T_{b}\), and compute \(T\) when required for point arithmetic. For the further improvement of the ECADD operation, the precomputed point \(Q\) is represented in the form \((X+Y,Y-X,2Z,2T)\)[25]. This method eliminates two multiplication by 2 operations and two field additions over \(\mathbb{F}_{p}\) compared to the extended Edwards coordinates. In the case of the ECDBL operation, we utilize the transformation \(2 XY=(X+Y)^{2}-X^{2}-Y^{2}\) to reduce the number of multiplications. It can be computed by converting one field multiplication and one field addition over \(\mathbb{F}_{p^{2}}\) to one field squaring, two field subtractions over \(\mathbb{F}_{p^{2}}\). Algorithms 6 and 7 describe the extensible coordinates of the ECADD and ECDBL operations over \(\mathbb{F}_{p^{2}}\) with a curve parameter \(a=-1\), which require \(8M_{2}+6A_{2}\) and \(3M_{2}+4S_{2}+6A_{2}\) operations, respectively. ```
1:\(P=(X_{1},Y_{1},Z_{1},T_{a},T_{b})\) where \(T_{1}=T_{a}\cdot T_{b}\) and \(Q=(X_{2}+Y_{2},Y_{2}-X_{2},2Z_{2},2T_{2})\). 2:\(P+Q=(X_{3},Y_{3},Z_{3},T_{a},T_{b})\) where \(T_{3}=T_{a}\cdot T_{b}\). 3:\(t_{2}\gets T_{a}\times T_{b}\) {\(M_{2}\)}
4:\(t_{2}\gets t_{2}\times 2Z_{2}\) {\(M_{2}\)}
5:\(t_{1}\gets 2T_{2}\times Z_{1}\) {\(M_{2}\)}
6:\(T_{a}\gets t_{2}-t_{1}\) {\(A_{2}\)}
7:\(T_{b}\gets t_{2}+t_{1}\) {\(A_{2}\)}
8:\(t_{2}\gets X_{1}+Y_{1}\) {\(A_{2}\)}
9:\(t_{2}\leftarrow(Y_{2}-X_{2})\times t_{2}\) {\(M_{2}\)}
10:\(t_{1}\gets Y_{1}-X_{1}\) {\(A_{2}\)}
11:\(t_{2}\leftarrow(X_{2}+Y_{2})\times t_{1}\) {\(M_{2}\)}
12:\(Z_{3}\gets t_{1}-t_{2}\) {\(A_{2}\)}
13:\(t_{1}\gets t_{1}+t_{2}\) {\(A_{2}\)}
14:\(X_{3}\gets T_{b}\times Z_{3}\) {\(M_{2}\)}
15:\(Z_{3}\gets t_{1}\times Z_{3}\) {\(M_{2}\)}
16:\(Y_{3}\gets t_{a}\times t_{1}\) {\(M_{2}\)}
17:return\(P+Q=(X_{3},Y_{3},Z_{3},T_{a},T_{b})\) where \(T=T_{a}\cdot T_{b}\). ```  
**Algorithm 6**Twisted Edwards point addition over \(\mathbb{F}_{p^{2}}\). To demonstrate the efficiency of the twisted Edwards curves, we compare it to the cost of a short Weierstrass elliptic curve.