A New Addition Law in Twisted Edwards Curves on Non Local Ring

Abstract

Let $\mathbb {F}_{q}$ be a finite field of q elements with $q=p^r$ for some odd prime integer p and a positive integer r. Let $R=\mathbb {F}_{q}[e],$ where $e^{2}=e.$ The purpose of this paper is to investigate $E_{E,a,d}(R)$ be the twisted Edwards curves over R, with $a,d \in R$. In the end of the paper, we study the complexity of this new addition law in $E_{E,a,d}(R)$ and highlight some links of our results with elliptic curves cryptosystem.

1 Introduction

The use of elliptic curves in cryptography is an important tool in several cryptography going back independently to Koblitz [10] and Miller [11]. Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. It allows smaller keys to provide equivalent security compared to other cryptosystem. It can also be used to encrypt images of different sizes in embedded systems such as in (cf. [12,13,14]). In particular, it is shown that Edwards curves and twisted Edwards curves can be very useful to improve the efficiency of protocols (cf. [1,2,3,4]). Let us quote here some interesting works that are related to the subject of our paper. In 2007, Edwards introduced a new normal form for elliptic curves on a field K with characteristic an odd prime p,  containing a unified addition formula for adding and doubling points (cf. [1]). Bernstein and Lange, presented fast explicit formulas for group operations on an Edwards curve and they compared it to the different shapes of elliptic curves and different coordinate systems for base group operations. The comparison indicated that the Edwards curve is a good choice in cryptography (cf. [2]).

Thereafter, in 2008, Bernstein and his co-authors introduced the twisted Edwards curves with equation:

$$\begin{aligned} (aX^{2}+Y^{2})Z^{2}=Z^4+dX^2Y^2. \end{aligned}$$

(1)

For $Z \ne 0$ the homogeneous point (X : Y : Z) represents the affine point (X/Z, Y/Z) of equation: $aX^{2}+Y^{2}=1+dX^2Y^2$, where $a, d \in K$ are non zero and distinct. In addition, they introduced explicit formulas for addition and doubling over a finite field K as follows:

$$(X_{1},Y_{1})+(X_{2},Y_{2})=(\frac{X_{1}Y_{2}+Y_{1}X_{2}}{1+dX_{1}X_{2}Y_{1}Y_{2}},\frac{Y_{1}Y_{2}-aX_{1}X_{2}}{1-dX_{1}X_{2}Y_{1}Y_{2}}),$$

the group operations on Edwards curves were faster than those of most other elliptic curve models known at the time. The mentioned authors gave quick explicit formulas for twisted Edwards curves in projective and inverted coordinates. Furthermore, they showed that twisted Edwards curves save more times than many other curves (cf. [3]). In the same year, Bernstein and his co-authors introduced the binary Edwards curves (cf. [5]). In 2019, Boudabra and Nitaj studied the twisted Edwards curves on the finite field $\mathbb {F}_p$ where $p \ge 5$ is a prime number, and they extend their study to the ring $\mathbb {Z}/p^r\mathbb {Z}$ and $\mathbb {Z}/p^rq^s\mathbb {Z}.$ They also proposed a new scheme and studied its efficiency and security (cf. [4]). In the current work, we study twisted Edwards curves over the ring $R=\mathbb {F}_{q}[e]$, with $e^{2}=e$ and $\mathbb {F}_{q}$ the finite field of order $q = p^{n}$, n a positive integer, and p an odd prime integer. Furthermore, we give the relation between twisted Edwards curves over a finite field $\mathbb {F}_{q}$ and twisted Edwards curves over the ring R. In 2022, Elhamam and his co-authors studied the binary Edwards curves on the ring $\mathbb {F}_{2^n}[e], e^{2}=e$ (cf. [8]). This paper is structured as follows: In Sect. 2, we collect some known arithmetic properties of the ring R which we need to use in the remainder. In Sect. 3, we define the twisted Edwards curves $E_{E,a,d}(R)$ over R and study the invertibility of $ab(a-b)$ in R, which allows us to define the two twisted Edwards curves $E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})$ and $E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})$, where $\pi _{0}$ and $\pi _{1}$ are two surjective morphisms of rings defined by:

$$\begin{aligned} \begin{array}{ccccc} \pi _{0} &{} : &{} \mathbb {F}_{q}[e] &{} \rightarrow &{} \mathbb {F}_{q} \\ &{} &{} x_{0}+x_{1}e &{} \mapsto &{} x_{0} \\ \end{array} ~~~~ \text {and} ~~~~ \begin{array}{ccccc} \pi _{1} &{} : &{} \mathbb {F}_{q}[e] &{} \rightarrow &{} \mathbb {F}_{q} \\ &{} &{} x_{0}+x_{1}e &{} \mapsto &{} x_{0}+x_{1} .\\ \end{array} \end{aligned}$$

Next, we present the elements of $E_{a,d}(R)$ and give a bijection between the two sets; $E_{E,a,d}(R)$ and $E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})\times E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})$. Section 4 is dedicated to the study of the addition in twisted Edwards curves over the ring R. We define the additive law $P \tilde{+} Q$ in $E_{E,a,d}(R)$ by $P \tilde{+} Q =\tilde{\pi }^{-1}(\tilde{\pi }(P)+\tilde{\pi }(Q))$, for all points P and Q of $E_{E,a,d}(R)$, and we conclude that the map $\tilde{\pi }$ is an isomorphism between the groups $E_{E,a,d}(R)$ and $E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})\times E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})$. Thereafter, we study the complexity of the sum law in the twisted Edwards curve $E_{E,a,d}(R)$. We conclude by highlighting some links of our results with cryptography. For more works in this direction we refer the reader to [7, 9].

2 The Ring $\mathbb {F}_{q}[e],e^{2}=e$

Let $\mathbb {F}_{q}$ be a finite field with $q=p^r$ for some odd prime integer p and a positive integer r. Consider the quotient ring $R=\frac{\mathbb {F}_{q}[X]}{X^2-X}$. Since $X^2-X$ is the minimal polynomial of e over $\mathbb {F}_{q}$, the ring R is identified to the ring $\mathbb {F}_{q}[e]$, where $e^2=e.$ Therefore,

$$R = \lbrace x_{0} + x_{1}e\vert (x_{0},x_{1})\in (\mathbb {F}_{q})^2\rbrace .$$

The arithmetic operations in R can be decomposed into operations in $\mathbb {F}_{q}$ and they are computed as follows:

$$\begin{aligned} \begin{array}{c} X + Y = (x_{0} + y_{0}) + (x_{1} + y_{1})e,\\ X\cdot Y = (x_{0}y_{0}) + (x_{0}y_{1} +x_{1}y_{0} + x_{1}y_{1})e. \end{array} \end{aligned}$$

Then we have the following known proprieties [6] :

• 1. $(R,+, \cdot )$ is a finite unitary commutative ring.

• 2. R is an $\mathbb {F}_{q}$-vector space of dimension 2 with $\mathbb {F}_{q}$-basis ${\lbrace 1, e\rbrace }$.

• 3. $X\cdot Y = (x_{0}y_{0}) + ((x_{0} + x_{1})(y_{0} + y_{1})- x_{0}y_{0})e$.

• 4. $X^{2} = x_{0}^{2} + ((x_{0} + x_{1})^{2} - x_{0}^{2} )e.$

• 5. $X^{3} = x_{0}^{3} + ((x_{0} + x_{1})^{3}- x_{0}^{3})e.$

• 6. Put $X = x_{0} + x_{1}e \in R$. Then, X is invertible in R if and only if $x_{0}\ne 0$ and $x_{0} + x_{1}\ne 0$. In this case we have, $X^{-1}= x_{0}^{-1} +((x_{0} + x_{1})^{-1} - x_{0}^{-1})e$.

• 7. R is a non local ring.

• 8. $\pi _{0}$ and $\pi _{1}$ are two surjective morphisms of rings.

In the remainder of this paper we assume that $p\ne 2$.

3 Twisted Edwards Curves over the Ring R

Let X, Y, a and d be four elements of R such that $X = x_{0} + x_{1}e$, $Y = y_{0} + y_{1}e$, $a = a_{0} + a_{1}e$ and $d = d_{0} + d_{1}e$. We recall that a twisted Edwards curve is defined over finite fields. By analogous, we extend it as follows:

Definition 1

A twisted Edwards curve is defined over R is defined by the equation:

$$aX^{2}+Y^{2}=1+dX^2Y^2$$

such that $\varDelta =ad(a-d)$ is invertible in R. We denote it by $E_{E,a,d}(R)$;

$$E_{E,a,d}(R):=\lbrace (X,Y)\in R ~\vert ~ aX^{2}+Y^{2}=1+dX^2Y^2 \rbrace .$$

The following proposition allows to test the inversibility of $\varDelta$.

Proposition 1

Let $\varDelta _{0} = a_{0}d_{0}(a_{0}-d_{0})$ and $\varDelta _{1} = (a_{0}+a_{1})(d_{0}+d_{1})((a_{0}+a_{1})-(d_{0}+d_{1}))$. Then,

$$\varDelta =\varDelta _{0}+(\varDelta _{1}-\varDelta _{0}) \textit{and} \left\{ \begin{array}{ll} \varDelta _{0}=\pi _{0}(\varDelta ) \\ \varDelta _{1}=\pi _{1}(\varDelta ). \end{array} \right. $$

Proof

We have:

$$\begin{aligned} \varDelta&= ad(a-d) \\&= (a_{0}+a_{1}e)(d_{0}+d_{1}e)((a_{0}+a_{1}e)-(d_{0}+d_{1}e))\\&=[a_{0}d_{0}+(a_{0}d_{1}+a_{1}d_{0}+a_{1}d_{1})e][(a_{0}-d_{0})+(a_{1}-d_{1})e]\\&=a_{0}d_{0}(a_{0}-d_{0})+[a_{0}d_{0}(a_{1}-d_{1})+(a_{0}d_{1}+a_{1}d_{0}+a_{1}d_{1})(a_{0}-d_{0})+(a_{0}d_{1}+a_{1}d_{0}+a_{1}d_{1})(a_{1}-d_{1})]e\\&= a_{0}d_{0}(a_{0}-d_{0})+ [(a_{0}+a_{1})(d_{0}+d_{1})((a_{0}+a_{1})-(d_{0}+d_{1}))-a_{0}d_{0}(a_{0}-d_{0})]e\\&= \varDelta _{0}+(\varDelta _{1}-\varDelta _{0})e. \end{aligned}$$

Thus, $\varDelta _{0}=\pi _{0}(\varDelta )$ and $\varDelta _{1}=\pi _{1}(\varDelta ).$    $\square$

The following corollary is an immediate consequence of Proposition 1.

Corollary 1

$\varDelta$ is invertible in R if and only if $\varDelta _{0}\ne 0$ and $\varDelta _{1}\ne 0$.

By Corollary 1, if $\varDelta$ is invertible in R, then $E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})$ and $E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})$ are two twisted Edwards curves over the finite field $\mathbb {F}_{q}$. Note that

$$\begin{aligned} E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})&= \lbrace (x,y)\in (\mathbb {F}_{q})^2 \mid a_{0}x^{2}+y^{2}=1+d_{0}x^2y^2\rbrace , \\ E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})&= \lbrace (x,y)\in (\mathbb {F}_{q})^2\mid (a_{0}+a_{1})x^{2}+y^{2}=1+(d_{0}+d_{1})x^2y^2\rbrace . \end{aligned}$$

The following theorem characterizes the points of the twisted Edwards curves.

Theorem 1

Let X and Y be two elements of R. $(X , Y)\in E_{E,a,d}(R)$ if and only if $(\pi _{i}(X) , \pi _{i}(Y )) \in E_{E,\pi _{i}(a),\pi _{i}(d)}(\mathbb {F}_{q})$, for $i \in \lbrace 0, 1\rbrace .$

Proof

We have:

$$\begin{aligned} aX^{2}+Y^{2}&= (a_{0}+a_{1}e)(x_{0}+x_{1}e)^{2}+(y_{0}+y_{1}e)^{2} \\&= (a_{0}+a_{1}e)(x_{0}^{2}+((x_{0}+x_{1})^{2}-x_{0}^{2})e)+y_{0}^{2}+((y_{0}+y_{1})^{2}-y_{0}^{2})e\\&= a_{0}x_{0}^{2}+y_{0}^{2}+[(a_{0}+a_{1})(x_{0}+x_{1})^{2}+(y_{0}+y_{1})^{2}-a_{0}x_{0}^{2}-y_{0}^2]e, \text{ and } \end{aligned}$$

$$\begin{aligned} 1+dX^2Y^2&= 1+(d_{0}+d_{1}e)(x_{0}+x_{1}e)^2(y_{0}+y_{1}e)^2\\&= 1+(d_{0}+d_{1}e)(x_{0}^{2}+((x_{0}+x_{1})^{2}-x_{0}^{2})e)(y_{0}^{2}+((y_{0}+y_{1})^{2}-y_{0}^{2})e)\\&= 1+d_{0}x_{0}^{2}y_{0}^{2}+[(d_{0}+d_{1})(x_{0}+x_{1})^2(y_{0}+y_{1})^2-d_{0}x_{0}^{2}y_{0}^{2}]e, \end{aligned}$$

As $\lbrace 1, e\rbrace$ is an $\mathbb {F}_{q}$-basis of the $\mathbb {F}_{q}$-vector space R, then $aX^2+Y^2=1+dX^2Y^2$ if and only if

$$\left\{ \begin{array}{ll} a_{0}x^{2}_{0}+y_{0}^2=1+d_{0}x_{0}^2y_{0}^2 \\ \text { and } \\ (a_{0}+a_{1})(x_{0}+x_{1})^{2}+(y_{0}+y_{1})^{2}=1+(d_{0}+d_{1})(x_{0}+x_{1})^2(y_{0}+y_{1})^2 \end{array}. \right. $$

Which gives the result.    $\square$

Corollary 2

The mapping:

$$\begin{aligned} \begin{array}{ccccc} \tilde{\pi }_{i} &{} : &{} E_{E,a,d}(R) &{} \rightarrow &{} E_{E,\pi _{i}(a),\pi _{i}(d)}(\mathbb {F}_{q}) \\ &{} &{} (X , Y) &{} \mapsto &{} (\pi _{i}(X) , \pi _{i}(Y )) \end{array} \end{aligned}$$

is well defined, $i\in \lbrace 0,1\rbrace$.

Proof

By Theorem 1, we have $(\pi _{i}(X) , \pi _{i}(Y ) )\in E_{E,\pi _{i}(a),\pi _{i}(d)}(\mathbb {F}_{q})$. If $(X_{1}, Y_{1}) = (X_{2} , Y_{2})$, then $X_{2}=X_{1}$ and $Y_{2}=Y_{1}.$ Therefore,

$$\begin{aligned} \tilde{\pi }_{i}(X_{2} , Y_{2})&= (\pi _{i}(X_{2}) , \pi _{i}(Y_{2}) ) \\&=(\pi _{i}(X_{1}) , \pi _{i}(Y_{1}))\\&= \tilde{\pi }_{i}(X_{1}, Y_{1}). \end{aligned}$$

   $\square$

Now we classify the elements of $E_{E,a,d}(R)$. In fact we have:

Proposition 2

The elements of $E_{E,a,d}(R)$ are of the form:

• (X, Y) such that X is invertible,

• $(xe,\alpha +ye)$ such that $\alpha \in \lbrace -1,1\rbrace$ and $(x,\alpha +y)\in E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q}),$

• $(x-xe,y+(\alpha -y)e)$ such that $\alpha \in \lbrace -1,1\rbrace$ and $(x,y)\in E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q}).$

Proof

Let $P = (X , Y) \in E_{E,a,d}(R)$, where $X = x_{0} + x_{1}e$ and $Y = y_{0} + y_{1}e$. We distinguish two cases of X:

The First case: X is invertible.

The second case: X is not invertible. In this case we distinguish the next two sub-cases:

i):

If $X=xe$, where $x\in \mathbb {F}_{q}$, we have: $\pi _{0}(xe , y_{0} + y_{1}e)= (0 , y_{0})\in E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})$ then, $(0 , y_{0} )= (0 , 1 )$ or $(0 , y_{0} )= (0 , -1 ),$ so $(xe,Y)=(xe,\alpha +ye)$ such that $(x,\alpha +y)\in E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q});$ $\alpha \in \lbrace -1,1\rbrace$.

ii):

If $X=x-xe$, where $x\in \mathbb {F}_{q}$, then we have: $\pi _{1}(x-xe , y_{0} + y_{1}e)= (0 , y_{0}+y_{1})\in E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})$ then, $(0 , y_{0} + y_{1} )= (0 , 1 )$ or $(0 , y_{0} + y_{1} )= (0 , -1 ),$ so $(x-xe ,Y)=(x-xe,y+(\alpha -y)e)$ such that $(x,y)\in E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q});$ $\alpha \in \lbrace -1,1\rbrace$.

   $\square$

Corollary 3

The maps $\tilde{\pi }_{0}$ and $\tilde{\pi }_{1}$ are surjective.

Proof

Let $(x , y)\in E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})$ (resp. $(x' , y')\in E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})$), then $(x-xe,y+(1-y)e)$ (resp. $(x'e,1+(y'-1)e)$) is an antecedent of (x, y) (resp. $(x' , y')$).    $\square$

The following theorem establishes a $1-1$ correspondence between $E_{E,a,d}(R)$ and $E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})\times E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})$, and so it will be used to calculate the cardinal of $E_{E,a,d}(R)$ in Corollary 4.

Theorem 2

The map $\tilde{\pi }$ defined by:

$$\begin{array}{ccccc} \tilde{\pi } &{} : &{} E_{E,a,d}(R) &{} \rightarrow &{} E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})\times E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q}) \\ &{} &{} (X ,Y ) &{} \mapsto &{} ((\pi _{0}(X) , \pi _{0}(Y ) ) , (\pi _{1}(X) , \pi _{1}(Y ))) \\ \end{array}$$

is a bijection.

Proof

• As $\tilde{\pi }_{0}$ and $\tilde{\pi }_{1}$ are well defined, then $\tilde{\pi }$ is well defined.

• Let $((x_{0} , y_{0} ), (x_{1} , y_{1} )) \in E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})\times E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})$, then

  $$a_{0}x_{0}^{2}+y_{0}^{2}=1+d_{0}x_{0}^{2}y_{0}^{2},$$
  $$(a_{0}+a_{1})x_{1}^{2}+y_{1}^{2}=1+(d_{0}+d_{1})x_{1}^{2}y_{1}^{2},$$

  Put $X=x_{0}+(x_{1} - x_{0})e$ and $Y=y_{0}+(y_{1} - y_{0})e$. We have:

  $$\begin{aligned} aX^{2}+Y^{2}&= a_{0}x_{0}^{2}+y_{0}^{2}+[(a_{0}+a_{1})x_{1}^{2}+y_{1}^{2}-a_{0}x_{0}^{2}-y_{0}^2]e,\\ 1+dX^2Y^2&= 1+d_{0}x_{0}^{2}y_{0}^{2}+[(d_{0}+d_{1})x_{1}^2y_{1}^2-d_{0}x_{0}^{2}y_{0}^{2}]e, \end{aligned}$$

  So $(X,Y)\in E_{E,a,d}(R).$ Note that $\tilde{\pi }((x_{0}+(x_{1} - x_{0}) e , y_{0} + (y_{1} - y_{0}) e)) = ((x_{0} , y_{0} ), (x_{1}, y_{1} ))$. Hence $\tilde{\pi }$ is a surjective map.

• Let (X, Y) and $(X' , Y')$ are elements of $E_{E,a,d}(R)$, where $X = x_{0} + x_{1}e$, $Y = y_{0} + y_{1}e$, $X' =x'_{0} + x'_{1}e$, $Y' = y'_{0} + y'_{1}e$. If $(x_{0} , y_{0}) = (x'_{0} , y'_{0})$ and $(x_{0} + x_{1} , y_{0} + y_{1} ) = (x'_{0} + x'_{1} , y'_{0} + y'_{1} )$, then

  $$\left\{ \begin{array}{ll} x'_{0}=x_{0} \\ y'_{0}= y_{0}\\ \end{array} \right. \text { and }\left\{ \begin{array}{ll} x'_{1}=x_{1} \\ y'_{1}=y_{1}.\\ \end{array} \right. $$

  Therefore, $\tilde{\pi }$ is an injective application.

  We can easily show that the mapping $\tilde{\pi }^{-1}$ defined by:

  $$\tilde{\pi }^{-1}((x_{0} , y_{0} ), (x_{1} , y_{1} )) = (x_{0} +(x_{1}-x_{0})e , y_{0} +(y_{1}-y_{0})e)$$

  is the converse of $\tilde{\pi }.$

   $\square$

Corollary 4

The cardinal of $E_{E,a,d}(R)$ equals to the cardinal of $E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})\times E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})$.

Example 1

In $R=\mathbb {F}_{5}[e],$ let $a = 1 + 3e$ and $d = 2 + 3e.$ We have:

$$\begin{aligned} E_{E,a,d}(R)&= \lbrace (0, 1), (0, 4), (0, 1+3e), (0, 4+2e), (2, 2+3e), (2, 3+2e), (3, 2+3e), (3, 3+2e),\\&\qquad (2e, 1+4e), (2e, 4+e), (3e, 1+4e), (3e, 4+e), (1+4e, e), (1+4e, 4e),\\&\qquad (2+e, 2+3e), (2+e, 3+2e), (2+3e, 2+2e), (2+3e, 2+4e), (2+3e, 3+3e),\\&\qquad (2+3e, 3+e), (3+4e, 2+3e), (3+4e, 3+2e), (1+e, 0), (4+e, e),\\&\qquad (4+e, 4e), (1+2e, 0), (3+2e, 2+2e), (3+2e, 2+4e), (3+2e, 3+3e),\\ {}&\qquad (3+2e,3+e), (4+3e, 0), (4+4e, 0)\rbrace ,\\ E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{5})&= \lbrace (0, 1), (0, 4), (1, 0), (2, 2), (2, 3), (3, 2), (3, 3), (4, 0)\rbrace ,\\ E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{5})&= \lbrace (0, 1), (0, 4), (2, 0), (3, 0) \rbrace . \end{aligned}$$

4 Addition in Twisted Edwards Curve $E_{E,a,d}(R)$

Let $(x_{1},y_{1})$, $(x_{2},y_{2})$ two points on the twisted Edwards curve $E_{E,\pi _{i}(a),\pi _{i}(d)}(\mathbb {F}_{q}),$ for $i \in \lbrace 0,1\rbrace .$

The sum of these points on $E_{E,\pi _{i}(a),\pi _{i}(d)}(\mathbb {F}_{q}),$ for $i \in \lbrace 0,1\rbrace$ is given by:

$$\begin{aligned} (x_{1},y_{1})+(x_{2},y_{2})=(\dfrac{x_{1}y_{2}+y_{1}x_{2}}{1+\pi _{i}(d)x_{1}x_{2}y_{1}y_{2}},\dfrac{y_{1}y_{2}-\pi _{i}(a)x_{1}x_{2}}{1-\pi _{i}(d)x_{1}x_{2}y_{1}y_{2}}). \end{aligned}$$

(2)

The neutral element of this law is (0, 1) and the inverse of an element $(x_{1},y_{1})$ is $(-x_{1},y_{1}).$ These formulas are complete if $\pi _{i}(a)$ is a square and $\pi _{i}(d)$ is a non-square in the field $\mathbb {F}_{q},$ for $i \in \lbrace 0,1\rbrace$ (cf. [3]).

Lemma 1

Let $a=a_{0}+a_{1}e$ be an element the R. Then, a is a square in R if and only if $a_{0}$ and $a_{0}+a_{1}$ are squares in $\mathbb {F}_{q}.$

Proof

Let us start by proving the direct implication. If a is a square in R, then there exists $b=b_{0}+b_{1}e\in R$, with $a=b^2$. Thus, $a_{0}+a_{1}e=b_{0}^2+((b_{0}+b_{1})^2-b_{0}^2)e.$ So $a_{0}=b_{0}^2$ and $a_{1}=(b_{0}+b_{1})^2-b_{0}^2$. Therefore, $a_{0}=b_{0}^2$ and $a_{0}+a_{1}=(b_{0}+b_{1})^2$, i.e. $a_{0}$ and $a_{0}+a_{1}$ are squares in $\mathbb {F}_{q}.$

For the converse let $a=a_{0}+a_{1}e$ be an element of R, with $a_{0}$ and $a_{0}+a_{1}$ are squares in $\mathbb {F}_{q}.$ Then, there exists $(b_{0},b_{1})\in (\mathbb {F}_{q})^2$, where $a_{0}=b_{0}^2$ and $a_{0}+a_{1}=b_{1}^2.$ Therefore, $a_{0}+a_{1}e=b_{0}^2+(b_{1}^2-b_{0}^2)e=(b_{0}+(b_{1}-b_{0})e)^2,$ i.e. $a_{0}+a_{1}e$ is a square in R.    $\square$

The following example shows that if a is not a square in R, then the addition on $E_{E,a,d}(R)$ is not always defined as in the following example. Consider $p=5$, $a=2+3e,$ $d =2+3e$, then a and d are not squares and $P=(2+4e, 1)$ and $Q=(4, 4+2e)$ are a point on $E_{E,a,d}(R)$. Nevertheless, $P+Q$ not possible since the inverse of $1+dX_{1}X_{2}Y_{1}Y_{2}=e$ does not exist.

Lemma 2

Let $d_{0}+d_{1}e$, $\alpha \in \lbrace -1,1\rbrace$, and $(X_{1}, Y_{1}),$ $(X_{2}, Y_{2})$ be two points of the twisted Edwards curve $E_{E,a,d}(R)$, where $X_{1}=x_{0}+x_{1}e,$ $Y_{1}=y_{0}+y_{1}e,$ $X_{2}=x_{0}'+x_{1}'e$ and $Y_{1}=y_{0}'+y_{1}'e$, then $\alpha +dX_{1}X_{2}Y_{1}Y_{2}$ is invertible in R if and only if $\alpha +d_{0}x_{0}x_{0}'y_{0}y_{0}'\ne 0$ and $\alpha +(d_{0}+d_{1})(x_{0}+x_{1})(x_{0}'+x_{1}')(y_{0}+y_{1})(y_{0}'+y_{1}')\ne 0$ in $\mathbb {F}_{q}.$

Proof

We have:

$$\begin{aligned} \alpha +dX_{1}X_{2}Y_{1}Y_{2}&=\alpha +(d_{0}+d_{1}e)(x_{0}+x_{1}e)(x_{0}'+x_{1}'e)(y_{0}+y_{1}e)(y_{0}'+y_{1}'e)\\&=\alpha +d_{0}x_{0}x_{0}'y_{0}y_{0}'+[\alpha +(d_{0}+d_{1})(x_{0}+x_{1})(x_{0}'+x_{1}')(y_{0}+y_{1})(y_{0}'+y_{1}')-\\ {}&\qquad (\alpha +d_{0}x_{0}x_{0}'y_{0}y_{0}')]e, \end{aligned}$$

$\alpha +dX_{1}X_{2}Y_{1}Y_{2}$ is invertible in R if and only if $\pi _{0}(\alpha +dX_{1}X_{2}Y_{1}Y_{2})\ne 0$ and $\pi _{1}(\alpha +dX_{1}X_{2}Y_{1}Y_{2})\ne 0$ in $\mathbb {F}_{q},$ i.e.: $\alpha +d_{0}x_{0}x_{0}'y_{0}y_{0}'\ne 0$ and $\alpha +(d_{0}+d_{1})(x_{0}+x_{1})(x_{0}'+x_{1}')(y_{0}+y_{1})(y_{0}'+y_{1}')\ne 0$ in $\mathbb {F}_{q}.$    $\square$

Corollary 5

Let $d_{0}+d_{1}e$ be an element in R and $(X_{1}, Y_{1}),$ $(X_{2}, Y_{2})$ two points of the twisted Edwards curve $E_{E,a,d}(R)$. If $\pi _{0}(d)$ and $\pi _{1}(d)$ are not a square in $\mathbb {F}_{q}$, then $\alpha +dX_{1}X_{2}Y_{1}Y_{2}$ is invertible in R, $\alpha \in \lbrace -1,1\rbrace$.

Corollary 6

Let a, d be two elements of R and $(X_{1}, Y_{1}),$ $(X_{2}, Y_{2})$ two points of the twisted Edwards curve $E_{E,a,d}(R)$. Assume that a is a squre and d is not a square in R, then

$$\begin{aligned} (X_{1},Y_{1})+(X_{2},Y_{2})=(\dfrac{X_{1}Y_{2}+Y_{1}X_{2}}{1+dX_{1}X_{2}Y_{1}Y_{2}},\dfrac{Y_{1}Y_{2}-aX_{1}X_{2}}{1-dX_{1}X_{2}Y_{1}Y_{2}}) \end{aligned}$$

is well defined in $E_{E,a,d}(R).$

In order to reduce the computation cost in $E_{E,a,d}(R)$, we introduce a new addition in $E_{E,a,d}(R)$ in Sect. 4, and we compare the computation cost of the new law with the that law given in Corollary 6.

As $\tilde{\pi }$ is a bijection mapping between the two sets $E_{E,a,d}(R)$ and $E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})\times E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q}),$ we can define the sum on $E_{E,a,d}(R).$

Definition 2

Let $P=(X_{1},Y_{1})$ and $Q=(X_{2},Y_{2})$ be two points of the twisted Edwards curve $E_{E,a,d}(R)$, assume that a is a square and d is not a square in R, we define the additive law $P \tilde{+} Q$ in $E_{E,a,d}(R)$ by: $P \tilde{+} Q =\tilde{\pi }^{-1}(\tilde{\pi }(P)+\tilde{\pi }(Q)).$

Keep the assumptions of the above definition during this section. The following corollaries can be easily proved:

Corollary 7

The set $(E_{E,a,d}(R),\tilde{+})$ is a commutative group, which has (0, 1) as its zero element and the inverse of $(X_{1},Y_{1})$ is $(-X_{1},Y_{1}).$

Corollary 8

The $\tilde{\pi }$ mapping is an isomorphism of groups.

By using formula (2), Theorem 2 and Proposition 2, we shall give the explicit formula of sum of two points in the twisted Edwards curve $E_{E,a,d}(R)$ in the next lemmas.

Lemma 3

Let $P=(xe,\alpha +ye)$ and $Q=(x'e,\beta +y'e)$ be two elements of $E_{E,a,d}(R)$ such that $\alpha \in \lbrace -1,1\rbrace$ and $\beta \in \lbrace -1,1\rbrace$. Then $P\tilde{+}Q=(x_{3}e,\alpha \beta +(y_{3}-\alpha \beta )e),$ where

$$\begin{aligned} x_{3}=\dfrac{x(\beta +y')+(\alpha +y)x'}{1+\pi _{1}(d)xx'(\alpha +y)(\beta +y')} \text { and } y_{3}=\dfrac{(\alpha +y)(\beta +y')-\pi _{1}(a)xx'}{1-\pi _{1}(d)xx'(\alpha +y)(\beta +y')}. \end{aligned}$$

Proof

As $\left\{ \begin{array}{ll} \tilde{\pi }_{0}(xe,\alpha +ye)=(0,\alpha ) \\ \tilde{\pi }_{0}(x'e,\beta +y'e)=(0,\beta )\\ \end{array} \right. \text { and }$ $\left\{ \begin{array}{ll} \tilde{\pi }_{1}(xe,\alpha +ye)=(x,\alpha +y) \\ \tilde{\pi }_{1}(x'e,\beta +y'e)=(x',\alpha +y')\\ \end{array}, \right.$ according to the formula (2), we have:

$$\begin{aligned} \tilde{\pi }_{0}(xe,\alpha +ye)+ \tilde{\pi }_{0}(x'e,\beta +y'e) =(0,\alpha \beta ) \text { and } \tilde{\pi }_{1}(xe,\alpha +ye)+\tilde{\pi }_{1}(x'e,\beta +y'e) =(x_{3},y_{3}), \text{ where } \end{aligned}$$

$$\begin{aligned} x_{3} =\dfrac{x(\beta +y')+(\alpha +y)x'}{1+\pi _{1}(d)xx'(\alpha +y)(\beta +y')} \text { and } y_{3} =\dfrac{(\alpha +y)(\beta +y')-\pi _{1}(a)x'}{1-\pi _{1}(d)xx'(\alpha +y)(\beta +y')}. \end{aligned}$$

Therefore,

$$P\tilde{+}Q=\tilde{\pi }^{-1}((0,\alpha \beta ),(x_{3},y_{3}))=(x_{3}e,\alpha \beta +(y_{3}-\alpha \beta )e).$$

   $\square$

Lemma 4

Let $P=(xe,\alpha +ye)$ and $Q=(x'-x'e,y'+(\beta -y')e)$ be two points of the twisted Edwards curve $E_{E,a,d}(R)$ such that $\alpha \in \lbrace -1,1\rbrace$ and $\beta \in \lbrace -1,1\rbrace$. Then $P\tilde{+}Q=(\alpha x'+(\beta x-\alpha x')e,\alpha y'+(\beta (\alpha +y)-\alpha y')e).$

Proof

As $\left\{ \begin{array}{ll} \tilde{\pi }_{0}(xe,\alpha +ye)=(0,\alpha ) \\ \tilde{\pi }_{0}(x'-x'e,y'+(\beta -y')e)=(x',y')\\ \end{array} \right.$ and $\left\{ \begin{array}{ll} \tilde{\pi }_{1}(xe,\alpha +ye)=(x,\alpha +y) \\ \tilde{\pi }_{1}(x'-x'e,y'+(\beta -y')e)=(0,\beta )\\ \end{array}, \right.$ According to the formula (2), we have:

$$\begin{aligned} \tilde{\pi }_{0}(xe,\alpha +ye)+ \tilde{\pi }_{0}(x'e,\beta +y'e)=(\alpha x',\alpha y') \text { and } \tilde{\pi }_{1}(xe,\alpha +ye)+\tilde{\pi }_{1}(x'e,\beta +y'e)=(\beta x,\beta (\alpha +y)). \end{aligned}$$

Then

$$P\tilde{+}Q=\tilde{\pi }^{-1}((\alpha x',\alpha y'),(\beta x,\beta (\alpha +y)))=(\alpha x'+(\beta x-\alpha x')e,\alpha y'+(\beta (\alpha +y)-\alpha y')e).$$

   $\square$

Lemma 5

Let $P=(x-xe,y+(\alpha -y)e)$ and $Q=(x'-x'e,y'+(\beta -y')e)$ be two points of the twisted Edwards curve $E_{E,a,d}(R)$ such that $\alpha \in \lbrace -1,1\rbrace$ and $\beta \in \lbrace -1,1\rbrace$. Then $P\tilde{+}Q=(x_{3}-x_{3}e,y_{3}+(\alpha \beta -y_{3})e),$ where

$$\begin{aligned} x_{3}=\dfrac{xy'+yx'}{1+\pi _{0}(d)xx'yy'} \text { and } y_{3}=\dfrac{yy'-\pi _{0}(a)xx'}{1-\pi _{0}(d)xx'yy'}. \end{aligned}$$

Proof

As $\left\{ \begin{array}{ll} \tilde{\pi }_{0}(x-xe,y+(\alpha -y)e)=(x,y) \\ \tilde{\pi }_{0}(x'-x'e,y'+(\beta -y')e)=(x',y')\\ \end{array} \right.$ and $\left\{ \begin{array}{ll} \tilde{\pi }_{1}(x-xe,y+(\alpha -y)e)=(0,\alpha ) \\ \tilde{\pi }_{1}(x'-x'e,y'+(\beta -y')e)=(0,\beta )\\ \end{array}, \right.$ According to formula (2), we have:

$$\begin{aligned} \begin{array}{c} \tilde{\pi }_{0}(x-xe,y+(\alpha -y)e)+ \tilde{\pi }_{0}(x'-x'e,y'+(\beta -y')e)=(x_{3},y_{3}) \text { and }\\ \tilde{\pi }_{1}(x-xe,y+(\alpha -y)e)+\tilde{\pi }_{1}(x'-x'e,y'+(\beta -y')e)=(0,\alpha \beta ), \text{ where } \end{array} \end{aligned}$$

$$\begin{aligned} x_{3}=\dfrac{xy'+yx'}{1+\pi _{0}(d)xx'yy'}\text { and } y_{3}=\dfrac{yy'-\pi _{0}(a)xx'}{1-\pi _{0}(d)xx'yy'}. \end{aligned}$$

Therefore,

$$P\tilde{+}Q=\tilde{\pi }^{-1}((x_{3},y_{3}),(0,\alpha \beta ))=(x_{3}-x_{3}e,y_{3}+(\alpha \beta -y_{3})e).$$

   $\square$

Lemma 6

Let $P=(xe,\alpha +ye)$ and $Q=(x_{0}+x_{1}e,y_{0}+y_{1}e)$ be two points of the twisted Edwards curve $E_{E,a,d}(R)$ such that $\alpha \in \lbrace -1,1\rbrace .$ Then $P\tilde{+}Q=(\alpha x_{0}+(x_{3}-\alpha x_{0})e,\alpha y_{0}+(y_{3}-\alpha y_{0})e),$ where

$$\begin{aligned} x_{3}=\dfrac{x(y_{0}+y_{1})+(\alpha +y)(x_{0}+x_{1})}{1+\pi _{1}(d)x(x_{0}+x_{1})(\alpha +y)(y_{0}+y_{1})} \text { and } y_{3}=\dfrac{(\alpha +y)(y_{0}+y_{1})-\pi _{1}(a)x(x_{0}+x_{1})}{1-\pi _{1}(d)x(x_{0}+x_{1})(\alpha +y)(y_{0}+y_{1})}. \end{aligned}$$

Proof

As $\left\{ \begin{array}{ll} \tilde{\pi }_{0}(xe,\alpha +ye)=(0,\alpha ) \\ \tilde{\pi }_{0}(x_{0}+x_{1}e,y_{0}+y_{1}e)=(x_{0},y_{0}) \end{array} \right.$ and $\left\{ \begin{array}{ll} \tilde{\pi }_{1}(xe,\alpha +ye)=(x,\alpha +y) \\ \tilde{\pi }_{1}(x_{0}+x_{1}e,y_{0}+y_{1}e)=(x_{0}+x_{1},y_{0}+y_{1}) \end{array}, \right.$ According to the formula (2), we have:

$$\begin{aligned}&\tilde{\pi }_{0}(xe,\alpha +ye)+ \tilde{\pi }_{0}(x_{0}+x_{1}e,y_{0}+y_{1}e)=(\alpha x_{0},\alpha y_{0}) \text { and }\\&\tilde{\pi }_{1}(xe,\alpha +ye)+\tilde{\pi }_{1}(x_{0}+x_{1}e,y_{0}+y_{1}e)=(x_{3},y_{3}), \text { where } \end{aligned}$$

$$\begin{aligned} x_{3}=\dfrac{x(y_{0}+y_{1})+(\alpha +y)(x_{0}+x_{1})}{1+\pi _{1}(d)x(x_{0}+x_{1})(\alpha +y)(y_{0}+y_{1})} \text { and } y_{3}=\dfrac{(\alpha +y)(y_{0}+y_{1})-\pi _{1}(a)x(x_{0}+x_{1})}{1-\pi _{1}(d)x(x_{0}+x_{1})(\alpha +y)(y_{0}+y_{1})}. \end{aligned}$$

Therefore,

$$P\tilde{+}Q=\tilde{\pi }^{-1}((\alpha x_{0},\alpha y_{0}),(x_{3},y_{3}))=(\alpha x_{0}+(x_{3}-\alpha x_{0})e,\alpha y_{0}+(y_{3}-\alpha y_{0})e).$$

   $\square$

Lemma 7

Let $P=(x-xe,y+(\alpha -y)e)$ and $Q=(x_{0}+x_{1}e,y_{0}+y_{1}e)$ be two points of the twisted Edwards curve $E_{E,a,d}(R)$ such that $\alpha \in \lbrace -1,1\rbrace$. Then $P\tilde{+}Q=(x_{3}+(\alpha (x_{0}+x_{1})-x_{3})e,y_{3}+(\alpha (y_{0}+y_{1})-y_{3})e)$, where

$$\begin{aligned} x_{3}=\dfrac{xy_{0}+x_{0}y}{1+\pi _{0}(d)xx_{0}yy_{0}} \text { and } y_{3}=\dfrac{yy_{0}-\pi _{1}(a)xx_{0}}{1-\pi _{1}(d)xx_{0}yy_{0}}. \end{aligned}$$

Proof

As $\left\{ \begin{array}{ll} \tilde{\pi }_{0}(x-xe,y+(\alpha -y)e)=(x,y) \\ \tilde{\pi }_{0}(x_{0}+x_{1}e,y_{0}+y_{1}e)=(x_{0},y_{0})\\ \end{array} \right.$ and $\left\{ \begin{array}{ll} \tilde{\pi }_{1}(x-xe,y+(\alpha -y)e)=(0,\alpha ) \\ \tilde{\pi }_{1}(x_{0}+x_{1}e,y_{0}+y_{1}e)=(x_{0}+x_{1},y_{0}+y_{1}) \end{array}, \right.$ According to the formula (2), we have:

$$\begin{aligned} \begin{array}{c} \tilde{\pi }_{0}(x-xe,y+(\alpha -y)e)+ \tilde{\pi }_{0}(x_{0}+x_{1}e,y_{0}+y_{1}e)=(x_{3},y_{3})\text { and }\\ \tilde{\pi }_{1}(xe,\alpha +ye)+\tilde{\pi }_{1}(x_{0}+x_{1}e,y_{0}+y_{1}e) =(\alpha (x_{0}+x_{1}),\alpha (y_{0}+y_{1})), \text { where } \end{array} \end{aligned}$$

$$\begin{aligned} x_{3}=\dfrac{xy_{0}+x_{0}y}{1+\pi _{0}(d)xx_{0}yy_{0}} \text { and } y_{3}=\dfrac{yy_{0}-\pi _{1}(a)xx_{0}}{1-\pi _{1}(d)xx_{0}yy_{0}}. \end{aligned}$$

Therefore,

$$P\tilde{+}Q =\tilde{\pi }^{-1}((x_{3},y_{3}),(\alpha (x_{0}+x_{1}),\alpha (y_{0}+y_{1})))=(x_{3}+(\alpha (x_{0}+x_{1})-x_{3})e,\alpha y_{0}+(\alpha (y_{0}+y_{1})-y_{3})e).$$

   $\square$

Lemma 8

Let $P=(x_{0}+x_{1}e,y_{0}+y_{1}e)$ and $Q=(x'_{0}+x'_{1}e,y'_{0}+y'_{1}e)$ be two points of the twisted Edwards curve $E_{E,a,d}(R)$. Then $P\tilde{+}Q=(x_{3}+(x'_{3}-x_{3})e,y_{3}+(y'_{3}-y_{3})e),$ where

$$\begin{aligned}&x_{3}=\dfrac{x_{0}y'_{0}+x'_{0}y_{0}}{1+\pi _{0}(d)x_{0}y'_{0}x'_{0}y_{0}}, y_{3}=\dfrac{y_{0}y'_{0}-\pi _{0}(a)x_{0}x'_{0}}{1-\pi _{0}(d)x_{0}y'_{0}x'_{0}y_{0}},\\&x'_{3}=\dfrac{(x_{0}+x_{1})(y'_{0}+y'_{1})+(y_{0}+y_{1})(x'_{0}+x'_{1})}{1+\pi _{1}(d)(x_{0}+x_{1})(y'_{0}+y'_{1})(y_{0}+y_{1})(x'_{0}+x'_{1})} \\&\text { and }\\&y'_{3}=\dfrac{(y_{0}+y_{1})(y'_{0}+y'_{1})-\pi _{1}(a)(x_{0}+x_{1})(x'_{0}+x'_{1})}{1-\pi _{1}(d)(x_{0}+x_{1})(y'_{0}+y'_{1})(y_{0}+y_{1})(x'_{0}+x'_{1})}. \end{aligned}$$

Proof

As $\left\{ \begin{array}{ll} \tilde{\pi }_{0}(x_{0}+x_{1}e,y_{0}+y_{1}e)=(x_{0},y_{0}) \\ \tilde{\pi }_{0}(x'_{0}+x'_{1}e,y'_{0}+y'_{1}e)=(x'_{0},y'_{0})\\ \end{array} \right.$ and $\left\{ \begin{array}{ll} \tilde{\pi }_{1}(x_{0}+x_{1}e,y_{0}+y_{1}e)=(x_{0}+x_{1},y_{0}+y_{1}) \\ \tilde{\pi }_{1}(x'_{0}+x'_{1}e,y'_{0}+y'_{1}e)=(x'_{0}+x'_{1},y'_{0}+y'_{1})\\ \end{array}, \right.$ According to the formula (2), we have:

$$\begin{aligned} \tilde{\pi }_{0}(x_{0}+x_{1}e,y_{0}+y_{1}e)+ \tilde{\pi }_{0}(x'_{0}+x'_{1}e,y'_{0}+y'_{1}e)=(x_{3},y_{3}) \text { and } \end{aligned}$$

$$\begin{aligned} \tilde{\pi }_{1}(x_{0}+x_{1}e,y_{0}+y_{1}e)+\tilde{\pi }_{1}(x'_{0}+x'_{1}e,y'_{0}+y'_{1}e)=(x'_{3},y'_{3}), \text { where } \end{aligned}$$

$$\begin{aligned} x_{3}=\dfrac{x_{0}y'_{0}+x'_{0}y_{0}}{1+\pi _{0}(d)x_{0}y'_{0}x'_{0}y_{0}}, y_{3}=\dfrac{y_{0}y'_{0}-\pi _{0}(a)x_{0}x'_{0}}{1-\pi _{0}(d)x_{0}y'_{0}x'_{0}y_{0}}, \end{aligned}$$

$$\begin{aligned} x'_{3}=\dfrac{(x_{0}+x_{1})(y'_{0}+y'_{1})+(y_{0}+y_{1})(x'_{0}+x'_{1})}{1+\pi _{1}(d)(x_{0}+x_{1})(y'_{0}+y'_{1})(y_{0}+y_{1})(x'_{0}+x'_{1})} \text { and } \\ y'_{3}=\dfrac{(y_{0}+y_{1})(y'_{0}+y'_{1})-\pi _{1}(a)(x_{0}+x_{1})(x'_{0}+x'_{1})}{1-\pi _{1}(d)(x_{0}+x_{1})(y'_{0}+y'_{1})(y_{0}+y_{1})(x'_{0}+x'_{1})}. \end{aligned}$$

Therefore,

$$P\tilde{+}Q=\tilde{\pi }^{-1}((x_{3},y_{3}),(x'_{3},y'_{3}))=(x_{3}+(x'_{3}-x_{3})e,y_{3}+(y'_{3}-y_{3})e),$$

which completes the proof.    $\square$

Lemmas 3, 4, 5, 6, 7 and 8 can be regrouped in the next theorem which given the additive law of the twisted Edwards curve $E_{E,a,d}(R).$

Theorem 3

Let $P=(X_{1},Y_{1})$ and $Q=(X_{2},Y_{2})$ be in $E_{E,a,d}(R)$. Assume that $\pi _{i}(a)$ is a square and $\pi _{i}(d)$ is not a square in $\mathbb {F}_{q}$, where $i\in \lbrace 0,1\rbrace$. Under the law $\tilde{+}$, $(E_{E,a,d}(R),\tilde{+})$ is an Abelian group with zero element (0, 1). More precisely for every $\alpha , \beta \in \lbrace -1,1\rbrace$, we have $P\tilde{+}Q=(X_{3},Y_{3})$ is given by:

• 1) If $\tilde{\pi }_{0}(P)=(0,\alpha )$, then

  $$\begin{aligned} X_{3}&= \alpha \pi _{0}(X_{2})+(x_{3}-\alpha \pi _{0}(X_{2}))e,\\ Y_{3}&= \alpha \pi _{0}(Y_{2})+(y_{3}-\alpha \pi _{0}(Y_{2}))e, \end{aligned}$$

  where

  $$\tilde{\pi }_{1}(P)+\tilde{\pi }_{1}(Q)=(x_{3},y_{3}).$$

• 2) If $\tilde{\pi }_{1}(P)=(0,\alpha ),$ then

  $$\begin{aligned} X_{3}&= x_{3}+(\alpha \pi _{1}(X_{2})-x_{3})e,\\ Y_{3}&= y_{3}+(\alpha \pi _{1}(Y_{2})-y_{3})e, \end{aligned}$$

  where

  $$\tilde{\pi }_{0}(P)+\tilde{\pi }_{0}(Q)=(x_{3},y_{3}).$$

• 3) If $\tilde{\pi }_{0}(P)=(0,\alpha )$ and $\tilde{\pi }_{1}(Q)=(0,\beta ),$ then

  $$\begin{aligned} X_{3}&= \alpha \pi _{0}(X_{2})+(\beta \pi _{1}(X_{1})-\alpha \pi _{0}(X_{2}))e,\\ Y_{3}&= \alpha \pi _{0}(Y_{2})+(\beta \pi _{1}(Y_{1})-\alpha \pi _{0}(Y_{2}))e. \end{aligned}$$

• 4) If $\tilde{\pi }_{0}(P)\ne (0,\alpha )$ and $\tilde{\pi }_{1}(P)\ne (0,\alpha ),$ then

  $$\begin{aligned} X_{3}&= x_{3}+(x_{3}'-x_{3})e,\\ Y_{3}&= y_{3}+(y_{3}'-y_{3})e, \end{aligned}$$

  where

  $$\tilde{\pi }_{0}(P)+\tilde{\pi }_{0}(Q)=(x_{3},y_{3}),$$
  $$\tilde{\pi }_{1}(P)+\tilde{\pi }_{1}(Q)=(x_{3}',y_{3}').$$

Proof. For the proof, we can easily show that the lemmas from 3 to 8 verify the cases of the theorem.

$\square$

Now we shall focus on the complexity of the sum law in the twisted Edwards curve $E_{E,a,d}(R).$

Let S be the cost of the sum and M the cost of the multiplication in the field $\mathbb {F}_{q}$. The computation cost of calculating $P+Q$ the sum that is defined in Corollary 6 and $P\tilde{+}Q$ the sum that is defined in Definition 2 are given in the following table (Table 1):

Table 1. The complexity of the additions in the twisted Edwards curve $E_{E,a,d}(R)$.

The following graphics illustrate the above results (Fig. 1).

Fig. 1.

The complexity of the additions in the twisted Edwards curve $E_{E,a,d}(R).$

Concerning the complexity reduction of the sum law in the twisted Edwards curve $E_{E,a,d}(R)$, one can remark that the direct calculation of the sum $P + Q$ is more expensive compared to the calculation of this sum $P \tilde{+} Q$ using the isomorphism $\tilde{\pi }$. Which explain the need of this study.

Links with Cryptography

Let us close this section with few applications in cryptography. We have:

• $card (E_{E,a,d}(R))=card(E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})) \times card(E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})).$

• $E_{E,a,d}(R)$ and $E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})\times E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q})$ have the same security discrete logarithm problem.

• In cryptanalysis, break the discrete logarithm problem on $E_{E,a,d}(R)$ is equivalent to break the discrete logarithm problem on $E_{E,\pi _{0}(a),\pi _{0}(d)}(\mathbb {F}_{q})$ and $E_{E,\pi _{1}(a),\pi _{1}(d)}(\mathbb {F}_{q}).$