Ready-made short basis for GLV+GLS on high degree twisted curves

1.   Introduction

Scalar multiplication on elliptic curves is the key operation in elliptic curve cryptography. It is thus extremely important to speed-up the scalar multiplication. The Gallant-Lambert-Vanstone (GLV) method ^[1], its generalizations including Galbraith-Lin-Scott (GLS) method ^[2] and the GLV+GLS method by Longa-Sica ^[3], use fast endomorphisms to decompose the scalar multiplication into shorter ones. The basic idea of GLV can be explained as follows.

Let $(E, \mathcal{O}_{E})$ be an elliptic curve defined over a finite field $\mathbb{F}_{q}$. Suppose $\phi_{1} = 1, \ldots, \phi_{m}$ are efficiently computable $\mathbb{F}_{q}$-endomorphisms of $E$ (in practice $m = 2$ or $4$). For an integer $k\in [1, n-1]$ and a point $P\in G$, if there exists an $m$-dimensional decomposition

for some constant $C$, then one can speed up the scalar multiplication $[k]P$ by computing the right hand side of (1.1). This approach is called the $m$-GLV method.

The crucial step in the GLV method is to solve the shortest vector problem of a lattice. To obtain a shorter basis, lattice basis reduction algorithms, such as the Euclidean algorithm ($m = 2$) ^[1], LLL ^[11], or even a more specialized algorithm ($m = 4$) ^[3], are then used. However, in recent development, lattice basis reduction was found to be unnecessary. One can simply write down short vectors of length at most $O\left(n^{1/m}\right)$ directly from the elliptic curve. Galbraith et al. ^[2] constructed an endomorphism equipped with a convenient ready-made basis for $2$-dimensional decompositions and Benjamin Smith ^[6] constructed more families of endomorphisms from $\mathbb{Q}$-curves equipped with ready-made bases. Then, Smith ^[5] generalized these ready-made bases to all other known efficient endomorphism constructions for curves. He used elementary facts about quadratic rings to immediately write down ready-made short bases of the lattices for the GLV, GLS, GLV+GLS of quadratic twists, for $\mathbb{Q}$-curve construction on elliptic curves ^[4,6], and for Jacobians with real multiplication construction ^[7,8].

In this paper, we extend Smith's method to give a ready-made short basis for GLV+GLS with degree of twist $4$ or $6$. We note that Longa-Sica's algorithm ^[3] can be used to calculate a short basis of the lattice for this class of quartic twisted elliptic curves. What's more, for the class of sextic twisted curves $E'/\mathbb{F}_{p^{2}}$, Hu et al. ^[10] described a method to compute different short bases for the lattice according to the order $\#E'(\mathbb{F}_{p^{2}})$. However, we give a unified short basis of the lattice for the two classes of curves without discussions about their orders. Moreover, these short bases of lattices constructed by us from the scalar decompositions can be read off from simple endomorphism ring relations which in practice are known in advance.

This paper is organized as follows. In §2, we give an overview of Smith's method on GLV+GLS with quadratic twists. In §3, we give supplements to Smith's method on high degree twisted elliptic curves. In §4, we give examples to verify our supplements.

2.   Preliminary

2.1.   GLV+GLS

The original GLV method by Gallant-Lambert-Vanstone ^[1] was about the $2$-dimensional decomposition on special elliptic curves with an efficient endomorphism $\phi_2 = \rho$. The characteristic polynomial of $\rho$ is $X^2+rX+s$ with $r, s\in \mathbb{Z}$. Six examples of ordinary elliptic curves (identified with their $j$-invariants) defined over $\mathbb{F}_p$ with the endomorphism $\rho$ be the complex multiplication map $P\mapsto [a]P$ were found to be applicable of their method:

These curves are called the GLV curves. Note that $\mathbb{Z}[\rho] = \mathbb{Z}[\frac{-r+\sqrt{r^2-4s}}{2}]$ is either the maximal order or of an order of index $2$ to the maximal order of the quadratic field $\mathbb{Q}(\rho) = \operatorname{End}(E)\otimes\mathbb{Q}$.

Galbraith-Lin-Scott ^[2] proved the following theorem:

Theorem 1 (^[2]). Let $p > 3$ be a prime and $E$ an ordinary elliptic curve defined over $\mathbb{F}_{p}$. Let $\pi_{0}$ be the $p$-power Frobenius map on $E$ and $t_{\pi_{0}}$ the trace of $\pi_{0}$. Let $E'/\mathbb{F}_{p^{2}}$ be the quadratic twist of $E(\mathbb{F}_{p^{2}})$ and $\tau: E\rightarrow E'$ be the twist isomorphism defined over $\mathbb{F}_{p^{4}}$. Let $\psi = \tau\pi_{0}\tau^{-1}$.

$(1)$ The characteristic polynomial of $\psi$ is $X^2-t_{\pi_0}X+p$, i.e. $\psi^2(P)-[t_{\pi_0}]\psi(P)+[p]P = \mathcal{O}_{E'}$ for $P\in E'(\overline{\mathbb{F}}_{p})$.

$(2)$ If $n > 2p$ is a prime factor of $\#E'(\mathbb{F}_{p^{2}}) = (p-1)^2+t_{\pi_0}^2$, then for $P\in E'(\mathbb{F}_{p^{2}})[n]$, $\psi^{2}(P)+P = \mathcal{O}_{E'}$.

Based on Theorem 1, Galbraith-Lin-Scott constructed the $2$-dimensional GLV decomposition on the quadratic twist $E'(\mathbb{F}_{p^2})$. The curve $E'/\mathbb{F}_{p^{2}}$ which is a twist of $E(\mathbb{F}_{p^{2}})$ is called the GLS curve and the $2$-dimensional decomposing method using the restricted endomorphism $\psi$ on $E'(\mathbb{F}_{p^2})$ satisfying $\psi^{2}+1 = 0$ is called the GLS method. Moreover, for quartic and sextic twists, Galbraith et al. also described how to obtain the $4$-dimensional decompositions on $E'(\mathbb{F}_{p^2})$ by $\psi = \tau\pi_{0}\tau^{-1}$ satisfying certain quartic equations, which we will give in §3. In particular, Hu et al. ^[10] described the complete implementation of 4-dimensional decompositions on sextic twisted GLS elliptic curves.

Longa-Sica ^[3] combined GLV and GLS method (GLV+GLS) to get a $4$-dimensional decomposition for twists of any GLV curve over $\mathbb{F}_{p^{2}}$. Let $E/\mathbb{F}_{p}$ be a GLV curve with $\rho$ being the GLV endomorphism, let $E'/\mathbb{F}_{p^{2}}$ be a quadratic twist of $E$ via the twist map $\tau:E\rightarrow E'$. We thus get two endomorphisms $\phi = \tau\rho\tau^{-1}$ and $\psi = \tau\pi_{0}\tau^{-1}$ of $E'$ defined over $\mathbb{F}_{p^{2}}$, with characteristic polynomials $X^2+rX+s$ and $X^2-t_{\pi_0}X+p$ respectively. Let $\mathbb{Z}[\phi]$ and $\mathbb{Z}[\psi]$ be the $\mathbb{Z}$-modules over $\mathbb{Z}$ generated by the roots of the respective characteristic polynomials. If $E'$ is ordinary, we know $\mathbb{Q}(\phi) = \mathbb{Q}(\psi)$.

Now if $n$ satisfies the condition in Theorem 1 and $G\subset E'(\mathbb{F}_{p^2})$ is only the cyclic subgroup of order $n$, then for $P\in G$, $\psi^{2}(P)+P = \mathcal{O}_{E'}$. The root of $\psi^2+1 = 0$ generates the quadratic ring $\mathbb{Z}[\sqrt{-1}]$ over $\mathbb{Z}$. Let $\left.\phi\right|_{G} = \left[\lambda_{\phi}\right]_{G}$ and $\left.\psi\right|_{G} = \left[\lambda_{\psi}\right]_{G}$, which we call the eigenvalues respect to $\phi$ and $\psi$.

For any scalar $k\in[1, n-1]$, Longa-Sica obtained a $4$-dimensional GLV decompositions

Consider the $4$-dimensional GLV reduction map

Clearly $F$ is a surjective homomorphism, its kernel

is a full sublattice of $\mathbb{Z}^{4}$.

Note that for any $k\in \mathbb{Z} / n \mathbb{Z}$, $[k]P = [x_{1}]P+[x_{2}]\phi(P)+[x_{3}]\psi(P)+[x_{4}]\phi\psi(P)$ for all $P\in G$ if and only if $(x_1, x_{2}, x_{3}, x_4)\in F^{-1}(k) = (k, 0, 0, 0)+\mathcal{L}$. If a basis $\{{\bf{b}}_{1}, {\bf{b}}_{2}, {\bf{b}}_{3}, {\bf{b}}_{4}\}$ for $\mathcal{L}$ is known, let $\left(\alpha_{1}, \alpha_{2}, \alpha_{3}, \alpha_{4}\right)$ be the (unique) solution in $\mathbb{Q}^{4}$ to the linear system $(k, 0, 0, 0) = \sum_{i = 1}^{4} \alpha_{i} {\bf{b}}_{i}$. Then

satisfies $\left\|\left(k_{1}, k_{2}, k_{3}, k_{4}\right)\right\|_{\infty} \leq 2\max _{i} \operatorname{norm}{{\bf{b}}_i}_\infty$ as $|x-\lfloor x\rceil| \leq 1 / 2$ for any $x\in \mathbb{Q}$. If the basis vectors are bounded by $O\left(n^{1/4}\right)$, then the decomposition in (2.1) and as a result faster computation for $[k]P$ are achieved.

Moreover, Longa-Sica ^[3] proposed a specialized algorithm (the twofold Cornacchia-type algorithm) to find a short basis for $\mathcal{L}$ under the assumption that $\mathbb{Z}[\phi]$ and $\mathbb{Z}[\sqrt{-1}]$ are $\mathbb{Z}$-linearly independent. They also treated the case $E/\mathbb{F}_{p}$ with $j$-invariant $1728$ and $E'$ a quartic twist of $E$ in [3,Appendix B].

2.2.   Ready-made short bases on GLV+GLS of quadratic twists

Now, we give some notations for the following content. Let $E/\mathbb{F}_{p}$ be a GLV curve with a GLV endomorphism $\rho$. Let $\pi_{0}$ be the $p$-power Frobenius on $E$ and $t_{\pi_{0}}$ be the trace of $\pi_{0}$. Let $E'/\mathbb{F}_{p^{2}}$ be a twist of $E(\mathbb{F}_{p^{2}})$ and $\tau: E\rightarrow E'$ be the twist isomorphism. $G\subset E'(\mathbb{F}_{p^2})$ is the only cyclic subgroup of large prime order $n$. Let $\phi = \tau\rho\tau^{-1}$ and $\psi = \tau\pi_{0}\tau^{-1}$, which are defined over $\mathbb{F}_{p^{2}}$ on $E'$. $\lambda_{\phi}$ and $\lambda_{\psi}$ are the eigenvalues of $\phi$ and $\psi$ on $G$, respectively.

First, we review the following result in ^[5], from which we can see that to produce the ready-made basis is mostly based on the simple order relations.

Lemma 1 (^[5]). Let $\zeta$ and $\zeta'$ be endomorphisms of an abelian variety $\mathcal{A}/\mathbb{F}_{q}$ such that $\mathbb{Z}[\zeta]$ and $\mathbb{Z}[\zeta']$ are quadratic rings and $\mathbb{Z}[\zeta]\subseteq \mathbb{Z}[\zeta']$, so $\zeta = c\zeta'+b$ for some integers $b$ and $c$. Let $G\subset \mathcal{A}$ be a cyclic subgroup of order $n$ such that $\zeta(G)\subseteq G$ and $\zeta'(G)\subseteq G$, and let $\lambda$ and $\lambda'$ be the eigenvalues in $\mathbb{Z}/n\mathbb{Z}$ of $\zeta$ and $\zeta'$ on $G$, respectively. Then

and

where $t_{\zeta'}$ is the trace of $\zeta'$ and $n_{\zeta'}$ is the norm of $\zeta'$.

From Lemma 1, Smith constructed explicit short bases for the GLV ^[1], GLS ^[2], GLV+GLS ^[3], and other constructions on $\mathbb{Q}$-curve ^[4,6] and genus 2 Jacobians ^[7,8].

In this paper, we only recall Smith's method on GLV+GLS of quadratic twists. $\lambda_{\phi}$ satisfies $\lambda_{\phi}^{2}+r\lambda_{\phi}+s = 0 \bmod n$, $\lambda_{\psi}$ satisfies $\lambda_{\psi}^{2}-t_{\pi_{0}}\lambda_{\psi}+p = 0 \bmod n$ and $\lambda_{\psi}^{2}+1 = 0 \mod n$. Since $\phi$ is constructed by a GLV endomorphism, $\mathbb{Z}[\phi]\cong\mathbb{Z}[\rho]$ is either the maximal order of the endomorphism algebra of $E'$, or very close to it—so it makes sense to assume that $\mathbb{Z}[\phi]$ contains $\mathbb{Z}[\psi]$, so that $\psi = c\phi+b$, where

Theorem 2 (^[5]). With $\phi$ and $\psi$ defined as above, suppose we can construct a $4$-dimensional decomposition (see the Eq (4)) with $(1, \phi, \psi, \phi\psi)$. The vectors

generate a sublattice of determinant $\#E'(\mathbb{F}_{p^{2}})$ in $\mathcal{L}$. These vectors are short with $\left\|{\bf{b}}_{i}\right\|_{\infty} = O(n^{1/4})$ for $1 \leq i \leq 4$. If $G = E'(\mathbb{F}_{p^{2}})$, then $\mathcal{L} = \langle {\bf{b}}_{1}, {\bf{b}}_{2}, {\bf{b}}_{3}, {\bf{b}}_{4} \rangle$.

3.   Ready-made short bases on GLV+GLS of quartic and sextic twists

Smith ^[5] only considered the ready-made short bases for quadratic twisted curves over $\mathbb{F}_{p^{2}}$. In this paper, we consider the cases of twisted curves over $\mathbb{F}_{p^{2}}$ of degree $4$ and $6$ and provide ready-made short bases for $4$-dimensional decompositions on these curves.

Since $\rho$ is a GLV endomorphism, $\mathbb{Z}[\phi]\cong \mathbb{Z}[\rho]$ is the maximal order of the endomorphism algebra of $E'$ for the case $j$-invariant 0 or 1728, then $\mathbb{Z}[\psi]$ is contained in $\mathbb{Z}[\phi]$. Then $\psi = c\phi+b$, where $b, c$ can be computed as Eq (2.4) by the characteristic equations of $\phi$ and $\psi$.

Our main results are Theorems 3 and 4.

Theorem 3. For $E/\mathbb{F}_{p}$ with $j$-invariant $1728$, $E'/\mathbb{F}_{p^{2}}$ is a quartic twist of $E(\mathbb{F}_{p^{2}})$ and $\tau: E\rightarrow E'$ is the twist isomorphism defined over $\mathbb{F}_{p^{8}}$. The characteristic equations of $\phi$ and $\psi$ are $\phi^{2}+1 = 0$ and $\psi^{2}-t_{\pi_{0}}\psi+p = 0$ respectively. Moreover, when restricted on $E'(\mathbb{F}_{p^2})$, $\psi$ also satisfies $\psi^{4}+1 = 0$. We can construct a 4-dimensional decomposition with $(1, \phi, \psi, \phi\psi)$. Then vectors

generate a sublattice of determinant $\#E'(\mathbb{F}_{p^{2}})$ in $\mathcal{L}$. These vectors are short with $\left\|{\bf{b}}_{i}\right\|_{\infty} = O(n^{1/4})$ for $1 \leq i \leq 4$. If $G = E'(\mathbb{F}_{p^{2}})$, then $\mathcal{L} = \langle {\bf{b}}_{1}, {\bf{b}}_{2}, {\bf{b}}_{3}, {\bf{b}}_{4} \rangle$.

Proof. For the fact $\psi^{4}(P)+P = \mathcal{O}_{E'}$ for any $P\in E'(\mathbb{F}_{p^{2}})$ one can refer to [2,§3]. Applying Lemma 1 to the inclusion $\mathbb{Z}[\psi]\subset \mathbb{Z}[\phi]$ with $t_{\phi} = 0$ and $n_{\phi} = 1$, we obtain relations

which correspond to the vectors ${\bf{b}}_{3}$ and ${\bf{b}}_{4}$. Note that when restricted on $E'(\mathbb{F}_{p^2})$, then $\pm\psi^{2}$ has the same characteristic equation as $\phi$. Changing $\phi$ to $-\phi$ if necessary, we may identify $\phi$ with $\psi^{2}$. Multiplying the relations in (3.1) by $\lambda_{\psi}$, using $\lambda_{\psi}^{2} = \lambda_{\psi^{2}} = \lambda_{\phi} \mod n$ and $\lambda_{\phi}^{2} = -1$, we obtain new relations

which correspond to the vectors ${\bf{b}}_{1}$ and ${\bf{b}}_{2}$.

The claim that $\det \langle{\bf{b}}_{1}, {\bf{b}}_{2}, {\bf{b}}_{3}, {\bf{b}}_{4}\rangle = \#E'(\mathbb{F}_{p^{2}})$ will be proved later.

Theorem 4. For $E/\mathbb{F}_{p}$ with $j$-invariant 0, $E'/\mathbb{F}_{p^{2}}$ is a sextic twist of $E(\mathbb{F}_{p^{2}})$ and $\tau: E\rightarrow E'$ is the sextic twisted isomorphism defined over $\mathbb{F}_{p^{12}}$. The characteristic equations of $\phi$ and $\psi$ are $\phi^{2}+\phi+1 = 0$ and $\psi^{2}-t_{\pi_{0}}\psi+p = 0$ respectively. Moreover, when restricted on $E'(\mathbb{F}_{p^2})$, $\psi$ also satisfies $\psi^{4}-\psi^{2}+1 = 0$. With $\phi$ and $\psi$, we can construct a 4-dimensional decomposition with $(1, \phi, \psi, \phi\psi)$. Then short vectors

generate a sublattice of determinant $\#E'(\mathbb{F}_{p^{2}})$ in $\mathcal{L}$. These vectors are short with $\left\|{\bf{b}}_{i}\right\|_{\infty} = O(n^{1/4})$ for $1 \leq i \leq 4$. If $G = E'(\mathbb{F}_{p^{2}})$, then $\mathcal{L} = \langle {\bf{b}}_{1}, {\bf{b}}_{2}, {\bf{b}}_{3}, {\bf{b}}_{4} \rangle$.

Proof. $\psi$ satisfies $\psi^{4}-\psi^{2}+1 = 0$, one can see [2,§3]. Note that when restricted on $E'(\mathbb{F}_{p^2})$, $-\psi^{2}$ satisfies the same characteristic equation $x^{2}+x+1 = 0$ as $\phi$, we identify $\phi$ with $-\psi^{2}$ on $E'(\mathbb{F}_{p^2})$. Similar to the proof of Theorem 3 with $t_{\phi} = -1, n_{\phi} = 1$, we can get the relations

which correspond to the vectors ${\bf{b}}_{3}$ and $\left(c-b, -b, 1, 1\right) = {\bf{b}}_{4}+{\bf{b}}_{3}$. Then multiplying (3.3) by $-\lambda_{\psi}$, we get

with $\lambda_{\psi}^{2} = \lambda_{\psi^{2}} = -\lambda_{\phi} \mod n$ and $\lambda_{\phi}^{2} = -\lambda_{\phi}-1 \mod n$. We can immediately get the vectors ${\bf{b}}_{1}, {\bf{b}}_{2}$. Also, the claim that $\det \langle{\bf{b}}_{1}, {\bf{b}}_{2}, {\bf{b}}_{3}, {\bf{b}}_{4}\rangle = \#E'(\mathbb{F}_{p^{2}})$ will be proved later.

The rest proof of Theorems 3 and 4. To verify $\det \langle{\bf{b}}_{1}, {\bf{b}}_{2}, {\bf{b}}_{3}, {\bf{b}}_{4}\rangle = \#E'(\mathbb{F}_{p^{2}})$, we need recall some results for the case $q = p^{2}$ in [12,Proposition 2]. In the following, let $t_{\pi}$ be the trace of Frobenius endomorphism $\pi\in \mathrm{End}(E\times\mathbb{F}_{p^{2}})$, where $E\times\mathbb{F}_{p^{2}}$ are the base extension of $E$ to $\mathbb{F}_{p^{2}}$.

Lemma 2 (^[12]). Let $E/\mathbb{F}_{p}$ be an ordinary elliptic curve, then $\#E(\mathbb{F}_{p}) = p+1-t_{\pi_{0}}$ and $\#E(\mathbb{F}_{p^{2}}) = p^{2}+1-t_{\pi}$, where $t_{\pi} = t_{\pi_{0}}^{2}-2p$. $E'/\mathbb{F}_{p^{2}}$ is a $d$-th twist of $E(\mathbb{F}_{p^{2}})$, then the possible group orders of $E'(\mathbb{F}_{p^{2}})$ are given by the following:

Moreover, if we know $p$ and $t_{\pi_{0}}$, we can get $\#E'(\mathbb{F}_{p^{2}}) = p^{2}+1\pm t_{\pi_{0}}\sqrt{4p-t_{\pi_{0}}^{2}}$ for $d = 4$ and $\#E'(\mathbb{F}_{p^{2}}) = p^{2}+p+1-\frac{t_{\pi_{0}}^{2}\pm t_{\pi_{0}}\sqrt{3(4p-t_{\pi_{0}}^{2})} }{2}$ for $d = 6$.

When $E'/\mathbb{F}_{p^{2}}$ is a quartic twist of $E(\mathbb{F}_{p^{2}})$, with $b = \frac{t_{\pi_{0}}}{2}$ and $c^{2} = \frac{4p-t_{\pi_{0}}^{2}}{4}$ by Eq (2.4), we have

When $E'/\mathbb{F}_{p^{2}}$ is a sextic twist of $E(\mathbb{F}_{p^{2}})$, with $b = \frac{t_{\pi_{0}}+c}{2}$ and $c^{2} = \frac{4p-t_{\pi_{0}}^{2}}{3}$ by Eq (2.4), we have

In the last, we can see that the vectors produced by Theorems 3 and 4 are short: Since $\phi$ is a GLV endomorphism, both $r$ and $s$ are in $O(1)$. Hence, in view of Eq (2.4), we observe that $b$ and $c$ are both in $O(\sqrt{p})$, thus $\left\|{\bf{b}}_{i}\right\|_{\infty}$ is in $O(\sqrt{p}) = O(n^{1/4})$ for $1 \leq i \leq 4$. So far, we have completed the proof of Theorems 3 and 4.

Remark 1. For the class of sextic twisted curves $E'/\mathbb{F}_{p^{2}}$, there are six cases of Frobenius trace $t_{\pi_{0}}$ [9,Ch. 18.3,Th. 4]. According to the formula in Lemma 2 with $d = 6$, there are three cases of $\#E'(\mathbb{F}_{p^{2}})$. Hu et al. ^[10] constructed three kinds of short bases according to the order of $E'(\mathbb{F}_{p^2})$. Their method is first to find the integral solutions $(u, v)$ of quadratic form $x^{2}+xy+y^{2} = p$, then six cases of $t_{\pi_{0}}$ and three cases of $\#E'(\mathbb{F}_{p^{2}})$ can be represented by $u, v$. For each case of $\#E'(\mathbb{F}_{p^{2}})$, they described a short basis generating a sublattice of determinant $\#E'(\mathbb{F}_{p^{2}})$ in $\mathcal{L}$, the upper bound of the basis only depends on the bound of $u, v$. We note that the lattice $\mathcal{L}$ in their construction is the same as ours in Theorem 4 and there are simple linear relationships between the elements $b, c$ and $u, v$. Thus, the basis $\langle {\bf{b}}_{1}, {\bf{b}}_{2}, {\bf{b}}_{3}, {\bf{b}}_{4}\rangle$ is of the same length $O(n^{1/4})$ as their's. We give a unified short basis without discussion of the order of $E'(\mathbb{F}_{p^2})$.

4.   Examples

Here, we give two examples to immediately write down a short basis of the lattice for GLV+GLS by our Theorems 3 and 4, see the following.

Example 1 ($j = 1728$). Let $p_{1} = 2^{127}-11791$ and $\mathbb{F}_{p_{1}^{2}} = \mathbb{F}_{p_{1}}(\sqrt{7})$. Let $u^{4} = \sqrt{7}$ in $\mathbb{F}_{p_{1}^{2}}$. Let $E_{1}'/\mathbb{F}_{p_{1}^{2}}: y^{2} = x^{3}+6u^{4}x$ with $\#E_{1}'(\mathbb{F}_{p_{1}^{2}}) = 2n_{1}$, where $n_{1}$ is a 253-bit prime. $E_{1}'$ is the quartic twist of the curve $E_{1}:y^{2} = x^{3}+6x$ with the Frobenius trace $t_{\pi_{0}, 1} = -5387725816103856782$. $\phi_{1}(x, y) = [\lambda_{1}]P = (-x, iy)$ and $\psi_{1}(x, y) = [\mu_{1}]P = (u^{2(1-p_{1})}x^{p_{1}}, u^{3(1-p_{1})}y^{p_{1}})$. The characteristic equations of $\phi_{1}$ and $\psi_{1}$ are $\phi_{1}^{2}+1 = 0$ and $\psi_{1}^{2}-t_{\pi_{0}, 1}\psi_{1}+p_{1} = 0$ respectively, $\psi_{1}$ also satisfies $\psi_{1}^{4}+1 = 0$ when restricted on $E_{1}'(\mathbb{F}_{p_{1}^{2}})$. Theorem 3 constructs a short basis of $\mathcal{L}$ in GLV+GLS method with $b = -2693862908051928391$ and $c = 12762612823912321416$:

Example 2 ($j = 0$). Let $p_{2} = 2^{128}-40557$ and $\mathbb{F}_{p_{2}^{2}} = \mathbb{F}_{p_{2}}(\sqrt{-1})$. Let $u^{6} = 3+\sqrt{-1}$ in $\mathbb{F}_{p_{2}^{2}}$. Let $E_{2}'/\mathbb{F}_{p_{2}^{2}}: y^{2} = x^{3}+8u^{6}$ with $\#E_{2}(\mathbb{F}_{p_{2}^{2}}) = n_{2}$, where $n_{2}$ is a 256-bit prime. $E_{2}'$ is the sextic twist of the curve $E_{2}:y^{2} = x^{3}+8$ with the Frobenius trace $t_{\pi_{0}, 2} = 17641752181631433232$. $\phi_{2}(x, y) = (\xi x, y) \; (\xi^{3} = 1 \mod p_{2})$ and $\psi_{2}(x, y) = [\mu_{2}]P = (u^{2(1-p_{2})}x^{p_{2}}, u^{3(1-p_{2})}y^{p_{2}})$. The characteristic equations of $\phi_{2}$ and $\psi_{2}$ are $\phi_{2}^{2}+\phi_{2}+1 = 0$ and $\psi_{2}^{2}-t_{\pi_{0}, 2}\psi+p_{2} = 0$ respectively, $\psi_{2}$ also satisfies $\psi_{2}^{4}-\psi_{2}^{2}+1 = 0$ when restricted on $E_{2}'(\mathbb{F}_{p_{1}^{2}})$. Theorem 4 constructs a short basis of $\mathcal{L}$ in GLV+GLS method with $b = 18174565414845640175$ and $c = 18707378648059847118$:

Moreover, we can compute the decomposed coefficients $\left\lbrace k_{1}, k_{2}, k_{3}, k_{4}\right\rbrace$ on $E_{i}'$ of 4-dimensional decompositions $[k]P = [k_{1}]P+[k_{2}]\phi_{i}(P)+[k_{3}]\psi_{i}(P)+[k_{4}]\phi_{i}\psi_{i}(P)$ on $E_{i}'$ through the ready-made short bases, $i = 1, 2$. The scalar $k$ is a random number with 128-bit security level (See Table 1).

5.   Conclusions

We extend Simth's method on GLV+GLS to quartic and sextic twists and give ready-made short bases for $4$-dimensional decompositions. In particular, our method gives a unified short basis without discussion of the order of $E'(\mathbb{F}_{p^2})$ compared with Hu et al.'s method ^[10].

Acknowledgments

The authors are grateful to the anonymous reviewers and the editor for their detailed comments and suggestions which highly improve the presentation and quality of this paper. The second author was supported by NSFC grant 1210010386. The third author was supported by Anhui Initiative in Quantum Information Technologies grant AHY150200, NSFC grant 11571328. The fourth author was supported by NSFC (grant 61972370 and 61632013), Fundamental Research Funds for Central Universities in China grant WK3480000007.

Conflict of interest

The authors declare there is no conflict of interests.