# Hyperelliptic Covers of Different Degree for Elliptic Curves

Authors: Jing Fan; Xuejun Fan; Ningning Song; Long Wang
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

In elliptic curve cryptography (ECC) and hyperelliptic curve cryptography (HECC), the size of cipher-text space defined by the cardinality of Jacobian is a significant factor to measure the security level. Counting problems on Jacobians of elliptic curve can be solved in polynomial time by Schoof–Elkies–Atkin (SEA) algorithm. However, counting problems on Jacobians of hyperelliptic curves are solved less satisfactorily than those on elliptic curves. So, we consider the construction of the cover map from the hyperelliptic curves to the elliptic curves to convert point counting problems on hyperelliptic curves to those on elliptic curves. We can also use the cover map as a kind of cover attacks. Given an elliptic curve over an extension field of degreen, one might try to use the cover attack to reduce the discrete logarithm problem (DLP) in the group of rational points of the elliptic curve to DLPs in the Jacobian of a curve of genus g≥n over the base field. An algorithm has been proposed for finding genus 3 hyperelliptic covers as a cover attack for elliptic curves with cofactor 2. Our algorithms are about the cover map from hyperelliptic curves of genus 2 to elliptic curves of prime order. As an application, an example of an elliptic curve whose order is a 256-bit prime vulnerable to our algorithms is given.


---

## Body

## 1. Introduction

The Weil restriction of scalar has significant implications in ECC. This idea was proposed by Frey and Gangl [1] as an attack on the elliptic curve discrete logarithm problem (ECDLP) and then developed further in [2, 3]. A nonconstant morphism ϕ:C⟶E between algebraic curve C over Fq and elliptic curve E over Fqn is a way to achieve this attack. Based on the constructive Weil restriction, Scholten [4] constructed hyperelliptic curves whose Jacobian was isogeneous to the Weil restriction of an elliptic curve and then counted points on the hyperelliptic curve by using an algorithm to count points on the elliptic curve.Jacobians of hyperelliptic curvesJH have been proposed for use in public key cryptography [5]. In ECC and HECC [6], the size of cipher-text space defined by the cardinality of Jacobian is significant to measure the security level. Specifically, the cardinality should be a prime time for a small so-called cofactor c to avoid the baby-step giant-step attack and Pohlig–Hellman attack [7]. For elliptic curves, there is a practical algorithm SEA to count the number of the points over finite fields [8–10]. However, for doing this on hyperelliptic curves, no subexponential general algorithm is currently known except for some small sets of examples [11], which is an impediment to their use. An algorithm proposed by Gaudry and Harley [12] to compute order for Jacobians of random hyperelliptic curves would run for about a week for a genus 2 curve defined over an 80-bit field. In 2003, Scholten [4] proposed a way of counting for hyperelliptic curves of special type y2=rx6+sx4+σsx2+σr, where σ is the generator of the Galois group of a quadratic extension. Inspired by Scholten, we consider that the cover map can help to count the order of Jacobians of hyperelliptic curves and the crucial point is to find the cover map from some specific hyperelliptic curves to elliptic curves.ECDLP is the fundamental building block for ECC and concerned by many researchers [13–17]. For many elliptic curves over finite fields, the generally fastest algorithms to solve the ECDLP are still generic algorithms, which are the conversion of attack algorithms on DLP. But there are also many families of elliptic curves, in particular those over finite nonprime fields, where the ECDLP can be solved faster by other methods, such as summation polynomials and cover attack. The former is proposed by Semaev [18] in order to find out whether the index calculus is suitable for ECDLP or not and then Diem [14] and Gaudry [19] independently use it to calculate the ECDLP over small degree extension fields. For cover attack [20], it aims at reducing the DLP in the group of the rational points of an elliptic curve over Fqn to DLP in the Jacobian groups of a curve C over Fq. The main idea of cover attacks is Weil descent, which is first introduced in cryptography by Frey [1]. The major difficulty in it lies in constructing the curve C, which is first solved by Gaudry, Hess, and Smart (GHS) [3] over binary field and generalized by Diem [21] in odd characteristic. For DLPs in the Jacobian groups of the curve C, decomposed attack was proposed by Gaudry [22] for hyperelliptic curves over Fq and then advanced to Fqn by Nagao [23] using Riemann–Roch spaces. To apply to all composite degree extension fields, Joux and Vitse [24] combined the Weil descent and decomposition attack. They used GHS attack for the part of Weil descent, while GHS attack can not produce a cover with small genus to make the whole attack works well when the elliptic curves have cofactor 2 over cubic extension fields. Tian et al. [25] used the results in reference [26] to fill the gap in GHS. In ECC, the elliptic curves of prime orders are of great interest, so it will be useful to focus on the elliptic curves of cofactor 1 over quadratic extension field. Inspired by reference [25], we try constructing genus 2 hyperelliptic covers for this kind of elliptic curves.The above two applications induce us to construct genus 2 hyperelliptic covers. We can use the cover to count the order of Jacobians of hyperelliptic curves and to attack the ECDLP.


### 1.1. Contribution

The contribution of our work is that we construct cover maps from a hyperelliptic curve of genus 2 to an elliptic curve with prime order over quadratic extension field. The whole process is based on the results in references [4, 25, 26]. The corresponding pattern of the map ϕ:H/Fq⟶E/Fq2 is that the Weierstrass points of the hyperelliptic curve lie over the 2-torsion points of the elliptic curve. Under the given restrictions, we can get a system of some equations, which can be computed easily and its solutions determine the cover maps.We focus on genus 2 hyperelliptic curves, which seem to be less vulnerable to attacks than others. About the equations of the hyperelliptic curvesy2=fx, we give propositions about the form of f, which offers more specific scope of the hyperelliptic curves suitable for our algorithm. There is also a relationship that #JHFq=#EFq2 when H satisfies JH/Fq2∼E2/Fq2, which is useful for counting applications. If we want to count the order of Jacobian of a hyperelliptic curve H, then the experiment can begin with the hyperelliptic curve and aim at finding the corresponding elliptic curve E. Then, SEA can be used to compute the cardinality of EFq2 to evaluate #JHFq in polynomial running time as long as the cover map ϕ:H⟶E exists. At the end of the study, we give an example in 128-bit field to show that our algorithm is faster than previous achievements.As a kind of a cover attacks, our map can transfer the DLP in the elliptic curve with prime order into DLPs in the Jacobians of a hyperelliptic curves, which can be later solved by decomposition attack of Nagao [23]. The main difference between GHS and our method is that the results of former are mainly nonhyperelliptic curves, while our algorithms have hyperelliptic curves as the final result. We can then construct isogeny from Jac H to Jacobian of nonhyperelliptic curves to reduce the time complexity. So, the method in the study has same complexity O˜q as GHS attack. The isogeny walk can also extend the scope of curves vulnerable to our attack. After experiments, we count the number of isomorphic classes of E in the specific form over relatively small fields and find that all of these elliptic curves can be attacked by our algorithm (Table 1).Inspirited by Satoh [27], we can also use our algorithms to generate the required hyperelliptic curves, which can be viewed as a by-product of counting method. For example, if a hyperelliptic curve with prime order of the Jacobian is required, then we can randomly select an elliptic curve of prime order as the input of our algorithms. If we can construct the cover map successfully, then the required hyperelliptic curve with the order of its Jacobian can be given. Otherwise, we can select another elliptic curve. The whole process can be viewed as a probabilistic polynomial-time algorithm.We have published a small part of our work [28] on Australasian Conference on Information Security and Privacy 2019. We only introduce the algorithm for the case when deg ϕ = 2 and f is reducible in detail in reference [28]. In this study, we offer more concrete proof for all of the propositions and new algorithms for the case when deg ϕ = 3, which is more complex than before. Moreover, more experiments on these new algorithms are given in Section 4.


## 1.1. Contribution

The contribution of our work is that we construct cover maps from a hyperelliptic curve of genus 2 to an elliptic curve with prime order over quadratic extension field. The whole process is based on the results in references [4, 25, 26]. The corresponding pattern of the map ϕ:H/Fq⟶E/Fq2 is that the Weierstrass points of the hyperelliptic curve lie over the 2-torsion points of the elliptic curve. Under the given restrictions, we can get a system of some equations, which can be computed easily and its solutions determine the cover maps.We focus on genus 2 hyperelliptic curves, which seem to be less vulnerable to attacks than others. About the equations of the hyperelliptic curvesy2=fx, we give propositions about the form of f, which offers more specific scope of the hyperelliptic curves suitable for our algorithm. There is also a relationship that #JHFq=#EFq2 when H satisfies JH/Fq2∼E2/Fq2, which is useful for counting applications. If we want to count the order of Jacobian of a hyperelliptic curve H, then the experiment can begin with the hyperelliptic curve and aim at finding the corresponding elliptic curve E. Then, SEA can be used to compute the cardinality of EFq2 to evaluate #JHFq in polynomial running time as long as the cover map ϕ:H⟶E exists. At the end of the study, we give an example in 128-bit field to show that our algorithm is faster than previous achievements.As a kind of a cover attacks, our map can transfer the DLP in the elliptic curve with prime order into DLPs in the Jacobians of a hyperelliptic curves, which can be later solved by decomposition attack of Nagao [23]. The main difference between GHS and our method is that the results of former are mainly nonhyperelliptic curves, while our algorithms have hyperelliptic curves as the final result. We can then construct isogeny from Jac H to Jacobian of nonhyperelliptic curves to reduce the time complexity. So, the method in the study has same complexity O˜q as GHS attack. The isogeny walk can also extend the scope of curves vulnerable to our attack. After experiments, we count the number of isomorphic classes of E in the specific form over relatively small fields and find that all of these elliptic curves can be attacked by our algorithm (Table 1).Inspirited by Satoh [27], we can also use our algorithms to generate the required hyperelliptic curves, which can be viewed as a by-product of counting method. For example, if a hyperelliptic curve with prime order of the Jacobian is required, then we can randomly select an elliptic curve of prime order as the input of our algorithms. If we can construct the cover map successfully, then the required hyperelliptic curve with the order of its Jacobian can be given. Otherwise, we can select another elliptic curve. The whole process can be viewed as a probabilistic polynomial-time algorithm.We have published a small part of our work [28] on Australasian Conference on Information Security and Privacy 2019. We only introduce the algorithm for the case when deg ϕ = 2 and f is reducible in detail in reference [28]. In this study, we offer more concrete proof for all of the propositions and new algorithms for the case when deg ϕ = 3, which is more complex than before. Moreover, more experiments on these new algorithms are given in Section 4.


## 2. Preliminaries

In this section, we review some important conclusions on elliptic curves and hyperelliptic curves and we hope that the reader is familiar with the notions and results of algebraic curves [29].


### 2.1. Cover Maps

Letϕ:H⟶E be a map of degree d from a curve of genus 2 to a curve of genus 1 and let ιH be the hyperelliptic involution on H. The hyperelliptic involution ιH can induce a rational involution ιE on E that satisfies ϕ°ιH=ιE°ϕ. Let Hι=H/ιH and Eι=E/ιE be the curves of genus 0 obtained by taking the quotient by the involution. So, the quotient map πH:H⟶H/ιH ramifies at 6 points A1,A2,…,A6, which are called Weierstrass ramification points of H. The map πE:E⟶E/ιE ramifies at 4 points B1,B2,B3,B4, which can be called ramification points of E over Eι. There is also a map ϕι:H/ιH⟶E/ιE. The following lemma [26] is about the relationship among the ramification points.Lemma 1.
LetAi,i=1,2,3,4,5,6, be the Weierstrass ramification points of H and Bj,j=1,2,3,4, be the ramification points of E over Eι. The αi and βj are the image of these points in Hι and Eι respectively, and then ϕι−1βj contains αi with odd multiplicity and any other points of Hι with even multiplicity for each j.This lemma determines the pattern of the correspondence betweenαi and βj. We give the following two kinds of maps of the even degree and odd degree, respectively. In the diagram, ⊗ represents evenly ramified points, which are therefore other points of Hι.More details, such as the degree of the map and the ramification index of the map atαi, will be discussed in Section 3.


### 2.2. 2-Torsion Subgroup of the Jacobian

LetFq denote the finite field of q elements and F¯q be the algebraic closure of the prime field Fq. Then, the unique subfield of F¯q with qm elements, Fqm, is an extension field of Fq. Consider that the Jacobian of H over Fq2 is isogenous to the product of E1 and E2, which have the same number in Fq2. That is JH/Fq2∼E1/Fq2×E2/Fq2∼E12/Fq2.A hyperelliptic curveH of genus g is determined by an equation y2=fx, where f∈Fqx is a polynomial of degree 2g+1 or 2g+2 without multiple roots. The curve of degree 2g+1 (resp. 2g+2) is termed an imaginary (resp. a real) hyperelliptic curve and all of the hyperelliptic curves can be written in the form of real hyperelliptic curve. Let H be a real hyperelliptic curves and there are 2g+2 Weierstrass points, Pi=ηi,0,i∈1,2,…,2g+2,ηi∈F¯q. By the corollary in reference [30], every 2-torsion element of JH is of the form eT=∑P∈TP−#T/2∞1+∞2, where T⊆P1,…,P2g+2 and #T must be even. eT satisfies the following three properties:(i)
2eT=0;(ii)
eT1=eT2⇔T1=T2orT1=∁P1,…,P2g+2T2, where ∁ refers to the complement set;(iii)
eT1+eT2=eT1°T2, where T1°T2=T1∪T2−T1∩T2.Ifh is an Fq-rational factor of f with even degree, then a divisor D can be defined by div h=2D and the order of the divisor class D is 2 if and only if deg h≠0,2g+2. So, if f=h1h2h and the degrees of h1 and h2 are even, we can obtain two distinct divisor classes D1 and D2.


## 2.1. Cover Maps

Letϕ:H⟶E be a map of degree d from a curve of genus 2 to a curve of genus 1 and let ιH be the hyperelliptic involution on H. The hyperelliptic involution ιH can induce a rational involution ιE on E that satisfies ϕ°ιH=ιE°ϕ. Let Hι=H/ιH and Eι=E/ιE be the curves of genus 0 obtained by taking the quotient by the involution. So, the quotient map πH:H⟶H/ιH ramifies at 6 points A1,A2,…,A6, which are called Weierstrass ramification points of H. The map πE:E⟶E/ιE ramifies at 4 points B1,B2,B3,B4, which can be called ramification points of E over Eι. There is also a map ϕι:H/ιH⟶E/ιE. The following lemma [26] is about the relationship among the ramification points.Lemma 1.
LetAi,i=1,2,3,4,5,6, be the Weierstrass ramification points of H and Bj,j=1,2,3,4, be the ramification points of E over Eι. The αi and βj are the image of these points in Hι and Eι respectively, and then ϕι−1βj contains αi with odd multiplicity and any other points of Hι with even multiplicity for each j.This lemma determines the pattern of the correspondence betweenαi and βj. We give the following two kinds of maps of the even degree and odd degree, respectively. In the diagram, ⊗ represents evenly ramified points, which are therefore other points of Hι.More details, such as the degree of the map and the ramification index of the map atαi, will be discussed in Section 3.


## 2.2. 2-Torsion Subgroup of the Jacobian

LetFq denote the finite field of q elements and F¯q be the algebraic closure of the prime field Fq. Then, the unique subfield of F¯q with qm elements, Fqm, is an extension field of Fq. Consider that the Jacobian of H over Fq2 is isogenous to the product of E1 and E2, which have the same number in Fq2. That is JH/Fq2∼E1/Fq2×E2/Fq2∼E12/Fq2.A hyperelliptic curveH of genus g is determined by an equation y2=fx, where f∈Fqx is a polynomial of degree 2g+1 or 2g+2 without multiple roots. The curve of degree 2g+1 (resp. 2g+2) is termed an imaginary (resp. a real) hyperelliptic curve and all of the hyperelliptic curves can be written in the form of real hyperelliptic curve. Let H be a real hyperelliptic curves and there are 2g+2 Weierstrass points, Pi=ηi,0,i∈1,2,…,2g+2,ηi∈F¯q. By the corollary in reference [30], every 2-torsion element of JH is of the form eT=∑P∈TP−#T/2∞1+∞2, where T⊆P1,…,P2g+2 and #T must be even. eT satisfies the following three properties:(i)
2eT=0;(ii)
eT1=eT2⇔T1=T2orT1=∁P1,…,P2g+2T2, where ∁ refers to the complement set;(iii)
eT1+eT2=eT1°T2, where T1°T2=T1∪T2−T1∩T2.Ifh is an Fq-rational factor of f with even degree, then a divisor D can be defined by div h=2D and the order of the divisor class D is 2 if and only if deg h≠0,2g+2. So, if f=h1h2h and the degrees of h1 and h2 are even, we can obtain two distinct divisor classes D1 and D2.


## 3. Our Algorithms

In this section, we give algorithms to find the cover map of different degrees from hyperelliptic curves of genus 2 to elliptic curves with prime order. First, we give two basic propositions, which are about the order of Jacobians and the form of the equations of hyperelliptic curves. Then we give the algorithms for degϕ = 2, among which we find that there is a more specific form of the equations of hyperelliptic curves. Finally, we give an algorithm for deg ϕ = 3, which is more complex than that for deg ϕ = 2. We also give statistical analysis about the maps of different degrees based on the experimental results in small fields after each algorithm.


### 3.1. Theory Derivation for the Algorithms

In this subsection, we will compute the the order of the Jacobian and the equations of the hyperelliptic curves. ForC a smooth projective curve of genus g, the polynomial LqT is the numerator of the zata function:(1)ZCFq;T=exp∑n≥1#CFqnTnn=LqT1−T1−qT.The order of the group ofFq rational points on the Jacobian of C is as follows:(2)#JCFq=Lq1=χq1,where χq1 is the characteristic polynomial of the Frobenius endomorphism.Lemma 2.
LetC/Fq be a genus g curve with simple Jacobian JC and there is a nonconstant morphism ϕ/Fqg:CFqg⟶E, then JC/Fq is isogenous to the Weil restriction of E with respect to Fqg/Fq, denoted by ResE. So, the characteristic polynomial of the Frobenius endomorphism of JC is equal to that of ResE: χCT=T2g−trETg+qg with trE=qg+1−#EFqg.Proposition 1.
IfH has simple Jacobian over Fq and split Jacobian JH/Fq2∼E2/Fq2 over Fq2, then #JHFq=#EFq2.Proof.
IfH is regarded as a curve of genus 2 over Fq, from equation (2), we can obtain that(3)#JHFq=q2−trE+1.
IfH is regarded as a curve of genus 2 over Fq2, then we can obtain(4)Lq2T=q2T2−trET+12.
So(5)#JHFq2=Lq21=q2−trE+12.
Because of split JacobianJH/Fq2∼E2/Fq2, we can deduce that(6)#JHFq2=#EFq22.
Combining equations (3), (5), and (6), we can get #EFq2=#JHFq, which is important for us to evaluate #JHFq.Proposition 2.
Let H be a genus2 hyperelliptic curve and assume that H is given by y2=fx with f a polynomial of degree 6 in Fqx. If H has split Jacobian JH/Fq2∼E2/Fq2 with #JHFq an odd, then f is irreducible or a product of two irreducible polynomials with degree 3.Proof.
We have already known that the characteristic polynomial of the Frobenius endomorphismπ of JH is χHT=T4+σT2+q2 with σ=#EFq2−q2−1. Because #JHFq=χH1 is prime, σ is odd. Then, T3g≡1mod2,χH, where χH is the characteristic polynomial of Frobenius endomorphism π of JH. So, JHF¯q2=D∈JHF¯q:2D=0 is fixed by π6, which means the 2-torsion points of JH are all Fq6 rational. Hence, f is a product of linear factors over Fq6, which means the degrees of the Fq-irreducible factors of f must be factors of 6. So, if f has more than 2 factors, there will be two cases:(i)
f=h1h2h3 is a product of three Fq-irreducible polynomials and there must be a irreducible factor of degree 2. The factor of degree 2 can be factored into x−x0x−x0q over Fq2. So, we can define a divisor D1 by div hi=2x0,0+x0q,0−∞1−∞2=2D1∼0∈Pic0H. Affected by the elements in Gal Fq2/Fq, D1 has no change, which shows that D1 is a Fq-rational divisor class of order 2. That is a contradiction with our condition that #JHFq is a prime. So, this case should be excluded.(ii)
f=h1h2h3…hii≥4 and there must be deghj=deghk=1. We can define D1 by div hjhk=2D1∼0∈Pic0H, which is similar to the first case. So, this case should be excluded.


### 3.2. Algorithms fordegϕ = 2

Now we illustrate some concrete information about the cover mapϕ:H⟶E, which is in the form of ϕx,y=ϕ1x,ϕ2x,y. We start the experiment from a given elliptic curve. Under the existence of ϕ, it is easy to deduce map ϕ1:ℙ1⟶ℙ1, which satisfies the commutative diagram, where we represent the point x,1 in ℙ1 by x.We defineE by s2=gt∈Fq2t, where gt is an irreducible polynomial of degree 3. Otherwise, there will be a contradiction with the claim that #EFq2 is prime. So, gt can be written into the form of gt=t−βt−βq2t−βq4,β∈Fq6/Fq2.Because the degree ofϕ equals 2, the expression of ϕ1 is as follows:(7)ϕ1x=a2x2+a1x+a0x−ε2,where a0,a1,a2,ε∈Fq2 are the values that should be determined from the given E. However, the number of the values that should be determined is more than the number of the equations from restrictions, so we must fix some of them. The following lemma is helpful for reducing the number of the indeterminate values.Lemma 3.
For every automorphismψ:H/Fq2⟶H/Fq2, there is a linear fractional transformation τ:ℙ1⟶ℙ1 with τx=ax+b/cx+d for some a,b,c,d∈Fq2 with ad−bc≠0 such that the following diagram commutes:It can be proved that this map is transitive overFq2/Fq, which means the map satisfies (i) ax+b/cx+d∈Fq2/Fq for all x∈Fq2/Fq and (ii) there exist a,b,c,d∈Fq2 such that y=ax+b/cx+d for all x,y∈Fq2/Fq.From the lemma, we can fix the value ofε∈Fq2 in the expression of ϕ1x because different values of ε induce equivalent cover map ϕ. So, we can fix ε into ω, a generator of Fq2, and any other value can be mapped into it by the linear map above. Then, the expression of ϕ1 can be fixed in(8)ϕ1x=a2x2+a1x+a0x−ω2.We can also getϕ2x,y=ϕ1′xy/ψx, where ϕ1′x is derivative of ϕ1x.Next, we will respectively introduce the algorithms according to the different forms of hyperelliptic curves. All of the computation processes are done in Magma and Sage.


#### 3.2.1.f is Irreducible

Now, we discuss problems under the term thatH is defined by y2=fx and f∈Fqx is an irreducible polynomial of degree 6, which can be factored over Fq6 into fx=x−αx−αq⋯x−αq5,α∈Fq6 . The map ϕ1x∈Fq2x leads to a formula ϕ1αq2=ϕ1αq2. Based on Lemma 1, we can deduce the corresponding maps, where the ramification of ϕ1 at αqi is 1..Taking the first one as an example, we introduce how to compute theϕ1 and fx from a given E:s2=t−βt−βq2t−βq4.Choose the elementε∈Fq6 such that the 6 elements ε,εq,…,εq5 form a normal basis for Fq6 over Fq. Then, it makes sense to define(9)αi=αqi=x1εqi+x2εqi+1+⋯+x6εqi+5i∈0,1,…,5,where x1,…,x6∈Fq are the unknown values that should be computed to find out the hyperelliptic curves. Three values a0,a1,a2∈Fq2 need to be determined in the expression of ϕ1 and we can get(10)a0=x7ε+εq2+εq4+x8εq+εq3+εq5,a1=x9ε+εq2+εq4+x10εq+εq3+εq5,a2=x11ε+εq2+εq4+x12εq+εq3+εq5.where x7,…,x12 are extra six unknown values. The useful information of the map is extracted, and we can obtain the following two equations:(11)a2α02+a1α0+a0−βα0−ω2=0,(12)a2α12+a1α1+a0−βα1−ω2=0.By using these equations and the scalar restriction process, we can get a system of 12 equations of degree 3. Then, we can obtain an ideal generated by the equations and the solutions emerge because the dimension of the ideal is 0.As the results,t=ϕ1x can be submitted into the equation of E:s2=t−βt−βq2t−βq4 and the procedure can be inferred as follows:(13)s2=t−βt−βq2t−βq4=a2x2+a1x+a0x−ω2−βa2x2+a1x+a0x−ω2−βq2a2x2+a1x+a0x−ω2−βq4=a2−βa2−βq2a2−βq4x−αx−αq⋯x−αq6x−ω6=y2ga2x−ω6.So, in order to get the expression ofϕ2x,y, ga2 must be a square in Fq2.Let us retell the whole process of our algorithms. First, we examine the existence of the hyperelliptic curves, which can be mapped intoE/Fq2 and satisfy that (i) JH is simple and (ii) JH/Fq2∼E2; (iii) #JHFq is a prime. Then, we get a system consisting of 12 equations through scalar restriction of equations (11) and (12), whose Groebner basis is easy to compute. The solutions of the equations are what we want and they can make us obtain the expressions of the cover maps and the corresponding hyperelliptic curves.


#### 3.2.2.f is Reducible

In this part, we discuss that the equation ofH is reducible. Then, by Proposition 2, the equation can be factored into such two Fq-irreducible polynomials of degree 3 that we can factor it over Fq6 into fx=x−αx−αqx−αq3x−γx−γqx−γq3,α,γ∈Fq3/Fq. So, we can get the corresponding map.The whole process is similar to the case thatf is irreducible with a few differences on the expression of αi and the restricted equations:(14)αi=αqi=x1εqi+εqi+3+x2εqi+1+εqi+4+x3εqi+2+εqi+5i∈0,1,2,γi=γqi=x4εqi+εqi+3+x5εqi+1+εqi+4+x6εqi+2+εqi+5i∈0,1,2,a2α02+a1α0+a0−βα0−ω2=0,(15)a2γ02+a1γ0+a0−βγ0−ω2=0.By using the scalar restriction on equations (14) and (15), we can also get a system of 12 equations on 12 variables. Something should be noticed that dimension of the ideal generated by the system is 3. For dimension reduction, we should choose fixed value for 3 variables and then the rational points can be computed on a zero-dimension scheme. To give more information about the forms of the hyperelliptic curves in this case, we propose the following proposition.Proposition 3.
Let H be a genus 2 hyperelliptic curve and assume that H is given byy2=fx with f a polynomial of degree 6 in Fqx. If H has split Jacobian JH/Fq2∼E2/Fq2 with #JHFq, is a prime and the degree of the cover map ϕ:H/Fq⟶E/Fq2 is 2. Then, the corresponding cover map can be easily computed if f is of the form:(16)fx=x−αx−αqx−αq2x−γx−γqx−γq2,where α+γωq+ω=2αγ+ωq+1 and ω∈Fq2/Fq is the generator of Fq2, α,γ∈Fq3/Fq,Proof.
The corresponding x-coordinate map can be written into(17)ϕ1x=a2x2+a1x+a0x−ω2∈Fq2x.
So, it is clear that the ramification index ofϕ1 at ω is 2. By the Riemann–Hurwitz formula [31](18)2−2gHι=deg2−2gEι−∑eϕ−1−W,where W is the notation for wild ramification, there must be another point c0, where the ramification index of ϕ1 is 2. If ϕ1c0=t0, then we can construct an equation a2x2+a1x+a0=t0x−ω2, which has such a double root that can help us get the relationship among t0 and a2,a1,a0:(19)Δ=0⇒t0=4a0a2−a124a1ω+4a2ω2+4a0.
Substituting formula (19) into the equation ϕ1c0=t0, we can get the following expression:(20)c0=−2a0+a1ω2a2ω+a1.
The linear fractional transformationτ:x↦ax+b/cx+d is considered. Because ϕ1 is ramified at ω and c0, there are two diagrams:
It can be found thatτ≠id while τ2=id, where id means identity transformation. So(21)abcdabcd=a2+bcba+dca+dd2+bc∼1001⇒a=−d≠0.
Then, we can simplify the formula ofτ into τx=x+b/cx−1. After adjusting the coefficients of ϕ1, it is reasonable to require ϕ1x=ϕ1τx. Combining it with τω=ω, we can get(22)a0=0,(23)cω2−2ω−b=0,(24)a1+2ω−cω2a2=0.
Using the original restriction ofϕ1:ϕ1α=ϕ1γ,α≠γ, we can derive that(25)a1+2a2ωαγ+a0−a2ω2α+γ−a1ω2−2a0ω=0.
From equations (22), (24), and (25), the following equation can be derived:(26)cαγ−α+γ+2ω−cω2=0,which means τα=γ. Similarly, using ϕ1αq=ϕ1γq,ϕ1αq2=ϕ1γq2, we can get an equation system as follows:(27)α+b=cγα+1,αq+b=cγqαq+1,αq2+b=cγq2αq2+1.
From which we can find thatb,c∈Fq, which means the linear fractional transformation τ:x↦ax+b/cx+d satisfies a,b,c,d∈Fq. Now, we can get the relationship between the two points, at which the ramification index of ϕ1 is 2:(28)ω=aω+bcω+d⟹ωq=aωq+bcωq+d.
Becausec0 and ω are the only two points, which satisfy τx=x, we can have c0=ωq. Combining c0=ωq with equations (20), (25), and (28) and using ai’s proportional coefficients, we can get the final result α+γωq+ω=2αγ+ωq+1.


#### 3.2.3. Statistical Results

Elliptic curves are in the same isomorphism class if they have the samej-invariant. We count the number of the isomorphism classes that can be attacked by the algorithms of degree 2 in some small fields (Table 1). Let Total be the number of jE≠0,1728 when E/Fq2 is in the form of y2=x−βx−βq2x−βq4,β∈Fq6. Let Attack1 (resp. Attack2) be the number of jE≠0,1728 that E can be attacked by the algorithms with deg ϕx= 2 and irreducible (resp. reducible) f.Table 1
Number of isomorphism classes that can be attacked by the algorithms.
q3571113171923293137Total3816405696121176280320456Attack114478111216202024Attack23816405696121176280320456From the table, we can find that all of the isomorphic classes ofE in the form of y2=x−βx−βq2x−βq4,β∈Fq6 can be attacked by our algorithms with deg ϕx=2 and reducible f.


### 3.3. Algorithms fordegϕ = 3

The whole progress of the experiment for degϕ=3 is similar to that for deg ϕ=2 with a few differences on the cover diagram and the equation system to be solved. So, for deg ϕ=3, we only introduce one circumstance that f can be written into the product of two irreducible polynomials of degree 3 and the map is as follows:It is obvious that the expression ofϕ1 is as follows:(29)ϕ1x=a3x3+a2x2+a1x+a0x−γx−γqx−γq2,where γ is one of the roots of f over Fq6 and ai∈Fq2. The expression of α and γ is same as that in algorithm for deg ϕ = 2 and f is reducible, while there are a few changes in the variables because of the different expression of ϕ1 and the existence of ν∈Fq6/Fq2:(30)ν=x7ω+x8ωq+⋯+x12ωq5,ai=x13+2iω+ωq2+ωq4+x14+2iωq+ωq3+ωq5,i∈0,1,2,3.From Lemma1, we can derive that the function ϕ1x−β has a multiple root ν, which must not be equal to α because of Riemann–Hurwitz formula:(31)ϕ1x−β=a3x3+a2x2+a1x+a0−βx−γx−γqx−γq2x−γx−γqx−γq2=0.Becauseϕ1x−β has two different roots α and ν with ν a double root, we can get the following equation:(32)a3x3+a2x2+a1x+a0−βx−γx−γpx−γp2=a3−βx−αx−ν2.From that, we can induce three equations, which can be transferred into a system of 18 equations with 20 variables through scalar restriction:(33)a0+βγγpγp2=−a3−βν2α,(34)a2+βγ+βγp+βγp2=−a3−β2ν+α,(35)a1−βγγp−βγpγp2−βγγp2=a3−βν2+2να.We should fix the value ofa3≠0 and other 2 variables to compute on a zero-dimension scheme. To derive the expression of ϕ2x,y, the value of a3 should be classified, one is a quadratic residue and the other is a quadratic nonresidue.


#### 3.3.1. Statistical Analysis

After analyzing the solutions of a fixed hyperelliptic curve in a relatively small field, we can find thatν only has two different values ν1 and ν2 with ν2=ν1p3. Each choice of ν corresponds to an isomorphic class of elliptic curves, which conforms to the split Jacobian of H over Fq2. The relationship between the cover maps ϕ1x and Φ1x, related to ν1 and ν2 respectively, is Φ1x=ϕ1px, where the pth power over ϕ1 means pth power over each coefficient of ϕ1.It can be checked that the coefficients of the formula ofE2 equal to the pth power over those of E1, so E1 and E2 are in the same isogeny class. Because of the special relationship of ν, we consider that it may be possible to express ν by other unknown values, which will reduce 6 variables. Equations (33)–(35) can be used to preprocess these unknown data and the relationship is as follows:(36)ν=a3α+a2−βα+βγ+γp+γp22β−1.However, the substitute of the expression forν will make equation (18) forever admitted. After experiments begin with elliptic curves and hyperelliptic curves respectively, we give the following suggestions:(i)
If count#JHFq of a given hyperelliptic curve H is the goal, which means that the experiment is started with the hyperelliptic curve, ν should be expressed by ν=a3α+a2−βα+βγ+γp+γp2/2β−1, which can reduce 6 variables in the final equations. Because of the reduction in the number of both variables and restrictions, the dimension of the final ideal will decrease from 6 to 2, which will cut down the time complexity to a great extent.(ii)
If the cover attack on a given elliptic curve is the goal, which means that the experiment is started with the elliptic curve,ν can be expressed by either ν=x7ωqi+x8ωqi+1+⋯+x12ωqi+5,i∈0,1,…,5 or ν=a3α+a2−βα+βγ+γp+γp2/2β−1. The dimension of the ideal generated by restrictions is always 2 under both of the two expressions.


#### 3.3.2. Algorithm Improvement

We now try to reduce the dimension of the final ideal, which will enhance the efficiency of the algorithm. The key point is to reduce the number of the varieties. The elliptic curvey2=x−βx−βq2x−βq4 may be written as y2=xx−1x−λ,λ∈Fq6 [32]. So, the map changes.The expression ofϕ1 is as follows:(37)ϕ1x=b0x−αx−ν2x−γx−γqx−γq2,where α and γ are the roots of f over Fq6 and b0,ν∈Fq6. The variables are as follows:(38)αi=αqi=x1εqi+εqi+3+x2εqi+1+εqi+4+x3εqi+2+εqi+5i∈0,1,2,γi=γqi=x4εqi+εqi+3+x5εqi+1+εqi+4+x6εqi+2+εqi+5i∈0,1,2,νi=νqi=x7εqi+x8εqi+1+⋯+x12εqi+5i∈0,1,…,5,b0=x13ω+x14ωq+⋯+x18ωq5.The restricted equations are as follows:(39)b0α2−α0α2−ν02=α2−γ0α2−γ1α2−γ2,b0ν2−α0ν2−ν02=ν2−γ0ν2−γ1ν2−γ2,b0ν4−α0ν4−ν02=λν4−γ0ν4−γ1ν4−γ2,b0α1−α0α1−ν02=λα1−γ0α1−γ1α1−γ2,which can be transferred into a system of 24 equations with 18 variables through scalar restriction. The dimension of the final ideal is 1 which is reduced by a half.If we start with hyperelliptic curves, whenα,γ are known, then the dimension of the final ideal in the previous algorithm is 2 so that we must try all of the possible values of the two free variables. After the improvement, we can get a system of 18 equations with 12 variables and the dimension of the final ideal is 0, which will reduce the time of traversing all values of the free variables.


## 3.1. Theory Derivation for the Algorithms

In this subsection, we will compute the the order of the Jacobian and the equations of the hyperelliptic curves. ForC a smooth projective curve of genus g, the polynomial LqT is the numerator of the zata function:(1)ZCFq;T=exp∑n≥1#CFqnTnn=LqT1−T1−qT.The order of the group ofFq rational points on the Jacobian of C is as follows:(2)#JCFq=Lq1=χq1,where χq1 is the characteristic polynomial of the Frobenius endomorphism.Lemma 2.
LetC/Fq be a genus g curve with simple Jacobian JC and there is a nonconstant morphism ϕ/Fqg:CFqg⟶E, then JC/Fq is isogenous to the Weil restriction of E with respect to Fqg/Fq, denoted by ResE. So, the characteristic polynomial of the Frobenius endomorphism of JC is equal to that of ResE: χCT=T2g−trETg+qg with trE=qg+1−#EFqg.Proposition 1.
IfH has simple Jacobian over Fq and split Jacobian JH/Fq2∼E2/Fq2 over Fq2, then #JHFq=#EFq2.Proof.
IfH is regarded as a curve of genus 2 over Fq, from equation (2), we can obtain that(3)#JHFq=q2−trE+1.
IfH is regarded as a curve of genus 2 over Fq2, then we can obtain(4)Lq2T=q2T2−trET+12.
So(5)#JHFq2=Lq21=q2−trE+12.
Because of split JacobianJH/Fq2∼E2/Fq2, we can deduce that(6)#JHFq2=#EFq22.
Combining equations (3), (5), and (6), we can get #EFq2=#JHFq, which is important for us to evaluate #JHFq.Proposition 2.
Let H be a genus2 hyperelliptic curve and assume that H is given by y2=fx with f a polynomial of degree 6 in Fqx. If H has split Jacobian JH/Fq2∼E2/Fq2 with #JHFq an odd, then f is irreducible or a product of two irreducible polynomials with degree 3.Proof.
We have already known that the characteristic polynomial of the Frobenius endomorphismπ of JH is χHT=T4+σT2+q2 with σ=#EFq2−q2−1. Because #JHFq=χH1 is prime, σ is odd. Then, T3g≡1mod2,χH, where χH is the characteristic polynomial of Frobenius endomorphism π of JH. So, JHF¯q2=D∈JHF¯q:2D=0 is fixed by π6, which means the 2-torsion points of JH are all Fq6 rational. Hence, f is a product of linear factors over Fq6, which means the degrees of the Fq-irreducible factors of f must be factors of 6. So, if f has more than 2 factors, there will be two cases:(i)
f=h1h2h3 is a product of three Fq-irreducible polynomials and there must be a irreducible factor of degree 2. The factor of degree 2 can be factored into x−x0x−x0q over Fq2. So, we can define a divisor D1 by div hi=2x0,0+x0q,0−∞1−∞2=2D1∼0∈Pic0H. Affected by the elements in Gal Fq2/Fq, D1 has no change, which shows that D1 is a Fq-rational divisor class of order 2. That is a contradiction with our condition that #JHFq is a prime. So, this case should be excluded.(ii)
f=h1h2h3…hii≥4 and there must be deghj=deghk=1. We can define D1 by div hjhk=2D1∼0∈Pic0H, which is similar to the first case. So, this case should be excluded.


## 3.2. Algorithms fordegϕ = 2

Now we illustrate some concrete information about the cover mapϕ:H⟶E, which is in the form of ϕx,y=ϕ1x,ϕ2x,y. We start the experiment from a given elliptic curve. Under the existence of ϕ, it is easy to deduce map ϕ1:ℙ1⟶ℙ1, which satisfies the commutative diagram, where we represent the point x,1 in ℙ1 by x.We defineE by s2=gt∈Fq2t, where gt is an irreducible polynomial of degree 3. Otherwise, there will be a contradiction with the claim that #EFq2 is prime. So, gt can be written into the form of gt=t−βt−βq2t−βq4,β∈Fq6/Fq2.Because the degree ofϕ equals 2, the expression of ϕ1 is as follows:(7)ϕ1x=a2x2+a1x+a0x−ε2,where a0,a1,a2,ε∈Fq2 are the values that should be determined from the given E. However, the number of the values that should be determined is more than the number of the equations from restrictions, so we must fix some of them. The following lemma is helpful for reducing the number of the indeterminate values.Lemma 3.
For every automorphismψ:H/Fq2⟶H/Fq2, there is a linear fractional transformation τ:ℙ1⟶ℙ1 with τx=ax+b/cx+d for some a,b,c,d∈Fq2 with ad−bc≠0 such that the following diagram commutes:It can be proved that this map is transitive overFq2/Fq, which means the map satisfies (i) ax+b/cx+d∈Fq2/Fq for all x∈Fq2/Fq and (ii) there exist a,b,c,d∈Fq2 such that y=ax+b/cx+d for all x,y∈Fq2/Fq.From the lemma, we can fix the value ofε∈Fq2 in the expression of ϕ1x because different values of ε induce equivalent cover map ϕ. So, we can fix ε into ω, a generator of Fq2, and any other value can be mapped into it by the linear map above. Then, the expression of ϕ1 can be fixed in(8)ϕ1x=a2x2+a1x+a0x−ω2.We can also getϕ2x,y=ϕ1′xy/ψx, where ϕ1′x is derivative of ϕ1x.Next, we will respectively introduce the algorithms according to the different forms of hyperelliptic curves. All of the computation processes are done in Magma and Sage.


### 3.2.1.f is Irreducible

Now, we discuss problems under the term thatH is defined by y2=fx and f∈Fqx is an irreducible polynomial of degree 6, which can be factored over Fq6 into fx=x−αx−αq⋯x−αq5,α∈Fq6 . The map ϕ1x∈Fq2x leads to a formula ϕ1αq2=ϕ1αq2. Based on Lemma 1, we can deduce the corresponding maps, where the ramification of ϕ1 at αqi is 1..Taking the first one as an example, we introduce how to compute theϕ1 and fx from a given E:s2=t−βt−βq2t−βq4.Choose the elementε∈Fq6 such that the 6 elements ε,εq,…,εq5 form a normal basis for Fq6 over Fq. Then, it makes sense to define(9)αi=αqi=x1εqi+x2εqi+1+⋯+x6εqi+5i∈0,1,…,5,where x1,…,x6∈Fq are the unknown values that should be computed to find out the hyperelliptic curves. Three values a0,a1,a2∈Fq2 need to be determined in the expression of ϕ1 and we can get(10)a0=x7ε+εq2+εq4+x8εq+εq3+εq5,a1=x9ε+εq2+εq4+x10εq+εq3+εq5,a2=x11ε+εq2+εq4+x12εq+εq3+εq5.where x7,…,x12 are extra six unknown values. The useful information of the map is extracted, and we can obtain the following two equations:(11)a2α02+a1α0+a0−βα0−ω2=0,(12)a2α12+a1α1+a0−βα1−ω2=0.By using these equations and the scalar restriction process, we can get a system of 12 equations of degree 3. Then, we can obtain an ideal generated by the equations and the solutions emerge because the dimension of the ideal is 0.As the results,t=ϕ1x can be submitted into the equation of E:s2=t−βt−βq2t−βq4 and the procedure can be inferred as follows:(13)s2=t−βt−βq2t−βq4=a2x2+a1x+a0x−ω2−βa2x2+a1x+a0x−ω2−βq2a2x2+a1x+a0x−ω2−βq4=a2−βa2−βq2a2−βq4x−αx−αq⋯x−αq6x−ω6=y2ga2x−ω6.So, in order to get the expression ofϕ2x,y, ga2 must be a square in Fq2.Let us retell the whole process of our algorithms. First, we examine the existence of the hyperelliptic curves, which can be mapped intoE/Fq2 and satisfy that (i) JH is simple and (ii) JH/Fq2∼E2; (iii) #JHFq is a prime. Then, we get a system consisting of 12 equations through scalar restriction of equations (11) and (12), whose Groebner basis is easy to compute. The solutions of the equations are what we want and they can make us obtain the expressions of the cover maps and the corresponding hyperelliptic curves.


### 3.2.2.f is Reducible

In this part, we discuss that the equation ofH is reducible. Then, by Proposition 2, the equation can be factored into such two Fq-irreducible polynomials of degree 3 that we can factor it over Fq6 into fx=x−αx−αqx−αq3x−γx−γqx−γq3,α,γ∈Fq3/Fq. So, we can get the corresponding map.The whole process is similar to the case thatf is irreducible with a few differences on the expression of αi and the restricted equations:(14)αi=αqi=x1εqi+εqi+3+x2εqi+1+εqi+4+x3εqi+2+εqi+5i∈0,1,2,γi=γqi=x4εqi+εqi+3+x5εqi+1+εqi+4+x6εqi+2+εqi+5i∈0,1,2,a2α02+a1α0+a0−βα0−ω2=0,(15)a2γ02+a1γ0+a0−βγ0−ω2=0.By using the scalar restriction on equations (14) and (15), we can also get a system of 12 equations on 12 variables. Something should be noticed that dimension of the ideal generated by the system is 3. For dimension reduction, we should choose fixed value for 3 variables and then the rational points can be computed on a zero-dimension scheme. To give more information about the forms of the hyperelliptic curves in this case, we propose the following proposition.Proposition 3.
Let H be a genus 2 hyperelliptic curve and assume that H is given byy2=fx with f a polynomial of degree 6 in Fqx. If H has split Jacobian JH/Fq2∼E2/Fq2 with #JHFq, is a prime and the degree of the cover map ϕ:H/Fq⟶E/Fq2 is 2. Then, the corresponding cover map can be easily computed if f is of the form:(16)fx=x−αx−αqx−αq2x−γx−γqx−γq2,where α+γωq+ω=2αγ+ωq+1 and ω∈Fq2/Fq is the generator of Fq2, α,γ∈Fq3/Fq,Proof.
The corresponding x-coordinate map can be written into(17)ϕ1x=a2x2+a1x+a0x−ω2∈Fq2x.
So, it is clear that the ramification index ofϕ1 at ω is 2. By the Riemann–Hurwitz formula [31](18)2−2gHι=deg2−2gEι−∑eϕ−1−W,where W is the notation for wild ramification, there must be another point c0, where the ramification index of ϕ1 is 2. If ϕ1c0=t0, then we can construct an equation a2x2+a1x+a0=t0x−ω2, which has such a double root that can help us get the relationship among t0 and a2,a1,a0:(19)Δ=0⇒t0=4a0a2−a124a1ω+4a2ω2+4a0.
Substituting formula (19) into the equation ϕ1c0=t0, we can get the following expression:(20)c0=−2a0+a1ω2a2ω+a1.
The linear fractional transformationτ:x↦ax+b/cx+d is considered. Because ϕ1 is ramified at ω and c0, there are two diagrams:
It can be found thatτ≠id while τ2=id, where id means identity transformation. So(21)abcdabcd=a2+bcba+dca+dd2+bc∼1001⇒a=−d≠0.
Then, we can simplify the formula ofτ into τx=x+b/cx−1. After adjusting the coefficients of ϕ1, it is reasonable to require ϕ1x=ϕ1τx. Combining it with τω=ω, we can get(22)a0=0,(23)cω2−2ω−b=0,(24)a1+2ω−cω2a2=0.
Using the original restriction ofϕ1:ϕ1α=ϕ1γ,α≠γ, we can derive that(25)a1+2a2ωαγ+a0−a2ω2α+γ−a1ω2−2a0ω=0.
From equations (22), (24), and (25), the following equation can be derived:(26)cαγ−α+γ+2ω−cω2=0,which means τα=γ. Similarly, using ϕ1αq=ϕ1γq,ϕ1αq2=ϕ1γq2, we can get an equation system as follows:(27)α+b=cγα+1,αq+b=cγqαq+1,αq2+b=cγq2αq2+1.
From which we can find thatb,c∈Fq, which means the linear fractional transformation τ:x↦ax+b/cx+d satisfies a,b,c,d∈Fq. Now, we can get the relationship between the two points, at which the ramification index of ϕ1 is 2:(28)ω=aω+bcω+d⟹ωq=aωq+bcωq+d.
Becausec0 and ω are the only two points, which satisfy τx=x, we can have c0=ωq. Combining c0=ωq with equations (20), (25), and (28) and using ai’s proportional coefficients, we can get the final result α+γωq+ω=2αγ+ωq+1.


### 3.2.3. Statistical Results

Elliptic curves are in the same isomorphism class if they have the samej-invariant. We count the number of the isomorphism classes that can be attacked by the algorithms of degree 2 in some small fields (Table 1). Let Total be the number of jE≠0,1728 when E/Fq2 is in the form of y2=x−βx−βq2x−βq4,β∈Fq6. Let Attack1 (resp. Attack2) be the number of jE≠0,1728 that E can be attacked by the algorithms with deg ϕx= 2 and irreducible (resp. reducible) f.Table 1
Number of isomorphism classes that can be attacked by the algorithms.
q3571113171923293137Total3816405696121176280320456Attack114478111216202024Attack23816405696121176280320456From the table, we can find that all of the isomorphic classes ofE in the form of y2=x−βx−βq2x−βq4,β∈Fq6 can be attacked by our algorithms with deg ϕx=2 and reducible f.


## 3.2.1.f is Irreducible

Now, we discuss problems under the term thatH is defined by y2=fx and f∈Fqx is an irreducible polynomial of degree 6, which can be factored over Fq6 into fx=x−αx−αq⋯x−αq5,α∈Fq6 . The map ϕ1x∈Fq2x leads to a formula ϕ1αq2=ϕ1αq2. Based on Lemma 1, we can deduce the corresponding maps, where the ramification of ϕ1 at αqi is 1..Taking the first one as an example, we introduce how to compute theϕ1 and fx from a given E:s2=t−βt−βq2t−βq4.Choose the elementε∈Fq6 such that the 6 elements ε,εq,…,εq5 form a normal basis for Fq6 over Fq. Then, it makes sense to define(9)αi=αqi=x1εqi+x2εqi+1+⋯+x6εqi+5i∈0,1,…,5,where x1,…,x6∈Fq are the unknown values that should be computed to find out the hyperelliptic curves. Three values a0,a1,a2∈Fq2 need to be determined in the expression of ϕ1 and we can get(10)a0=x7ε+εq2+εq4+x8εq+εq3+εq5,a1=x9ε+εq2+εq4+x10εq+εq3+εq5,a2=x11ε+εq2+εq4+x12εq+εq3+εq5.where x7,…,x12 are extra six unknown values. The useful information of the map is extracted, and we can obtain the following two equations:(11)a2α02+a1α0+a0−βα0−ω2=0,(12)a2α12+a1α1+a0−βα1−ω2=0.By using these equations and the scalar restriction process, we can get a system of 12 equations of degree 3. Then, we can obtain an ideal generated by the equations and the solutions emerge because the dimension of the ideal is 0.As the results,t=ϕ1x can be submitted into the equation of E:s2=t−βt−βq2t−βq4 and the procedure can be inferred as follows:(13)s2=t−βt−βq2t−βq4=a2x2+a1x+a0x−ω2−βa2x2+a1x+a0x−ω2−βq2a2x2+a1x+a0x−ω2−βq4=a2−βa2−βq2a2−βq4x−αx−αq⋯x−αq6x−ω6=y2ga2x−ω6.So, in order to get the expression ofϕ2x,y, ga2 must be a square in Fq2.Let us retell the whole process of our algorithms. First, we examine the existence of the hyperelliptic curves, which can be mapped intoE/Fq2 and satisfy that (i) JH is simple and (ii) JH/Fq2∼E2; (iii) #JHFq is a prime. Then, we get a system consisting of 12 equations through scalar restriction of equations (11) and (12), whose Groebner basis is easy to compute. The solutions of the equations are what we want and they can make us obtain the expressions of the cover maps and the corresponding hyperelliptic curves.


## 3.2.2.f is Reducible

In this part, we discuss that the equation ofH is reducible. Then, by Proposition 2, the equation can be factored into such two Fq-irreducible polynomials of degree 3 that we can factor it over Fq6 into fx=x−αx−αqx−αq3x−γx−γqx−γq3,α,γ∈Fq3/Fq. So, we can get the corresponding map.The whole process is similar to the case thatf is irreducible with a few differences on the expression of αi and the restricted equations:(14)αi=αqi=x1εqi+εqi+3+x2εqi+1+εqi+4+x3εqi+2+εqi+5i∈0,1,2,γi=γqi=x4εqi+εqi+3+x5εqi+1+εqi+4+x6εqi+2+εqi+5i∈0,1,2,a2α02+a1α0+a0−βα0−ω2=0,(15)a2γ02+a1γ0+a0−βγ0−ω2=0.By using the scalar restriction on equations (14) and (15), we can also get a system of 12 equations on 12 variables. Something should be noticed that dimension of the ideal generated by the system is 3. For dimension reduction, we should choose fixed value for 3 variables and then the rational points can be computed on a zero-dimension scheme. To give more information about the forms of the hyperelliptic curves in this case, we propose the following proposition.Proposition 3.
Let H be a genus 2 hyperelliptic curve and assume that H is given byy2=fx with f a polynomial of degree 6 in Fqx. If H has split Jacobian JH/Fq2∼E2/Fq2 with #JHFq, is a prime and the degree of the cover map ϕ:H/Fq⟶E/Fq2 is 2. Then, the corresponding cover map can be easily computed if f is of the form:(16)fx=x−αx−αqx−αq2x−γx−γqx−γq2,where α+γωq+ω=2αγ+ωq+1 and ω∈Fq2/Fq is the generator of Fq2, α,γ∈Fq3/Fq,Proof.
The corresponding x-coordinate map can be written into(17)ϕ1x=a2x2+a1x+a0x−ω2∈Fq2x.
So, it is clear that the ramification index ofϕ1 at ω is 2. By the Riemann–Hurwitz formula [31](18)2−2gHι=deg2−2gEι−∑eϕ−1−W,where W is the notation for wild ramification, there must be another point c0, where the ramification index of ϕ1 is 2. If ϕ1c0=t0, then we can construct an equation a2x2+a1x+a0=t0x−ω2, which has such a double root that can help us get the relationship among t0 and a2,a1,a0:(19)Δ=0⇒t0=4a0a2−a124a1ω+4a2ω2+4a0.
Substituting formula (19) into the equation ϕ1c0=t0, we can get the following expression:(20)c0=−2a0+a1ω2a2ω+a1.
The linear fractional transformationτ:x↦ax+b/cx+d is considered. Because ϕ1 is ramified at ω and c0, there are two diagrams:
It can be found thatτ≠id while τ2=id, where id means identity transformation. So(21)abcdabcd=a2+bcba+dca+dd2+bc∼1001⇒a=−d≠0.
Then, we can simplify the formula ofτ into τx=x+b/cx−1. After adjusting the coefficients of ϕ1, it is reasonable to require ϕ1x=ϕ1τx. Combining it with τω=ω, we can get(22)a0=0,(23)cω2−2ω−b=0,(24)a1+2ω−cω2a2=0.
Using the original restriction ofϕ1:ϕ1α=ϕ1γ,α≠γ, we can derive that(25)a1+2a2ωαγ+a0−a2ω2α+γ−a1ω2−2a0ω=0.
From equations (22), (24), and (25), the following equation can be derived:(26)cαγ−α+γ+2ω−cω2=0,which means τα=γ. Similarly, using ϕ1αq=ϕ1γq,ϕ1αq2=ϕ1γq2, we can get an equation system as follows:(27)α+b=cγα+1,αq+b=cγqαq+1,αq2+b=cγq2αq2+1.
From which we can find thatb,c∈Fq, which means the linear fractional transformation τ:x↦ax+b/cx+d satisfies a,b,c,d∈Fq. Now, we can get the relationship between the two points, at which the ramification index of ϕ1 is 2:(28)ω=aω+bcω+d⟹ωq=aωq+bcωq+d.
Becausec0 and ω are the only two points, which satisfy τx=x, we can have c0=ωq. Combining c0=ωq with equations (20), (25), and (28) and using ai’s proportional coefficients, we can get the final result α+γωq+ω=2αγ+ωq+1.


## 3.2.3. Statistical Results

Elliptic curves are in the same isomorphism class if they have the samej-invariant. We count the number of the isomorphism classes that can be attacked by the algorithms of degree 2 in some small fields (Table 1). Let Total be the number of jE≠0,1728 when E/Fq2 is in the form of y2=x−βx−βq2x−βq4,β∈Fq6. Let Attack1 (resp. Attack2) be the number of jE≠0,1728 that E can be attacked by the algorithms with deg ϕx= 2 and irreducible (resp. reducible) f.Table 1
Number of isomorphism classes that can be attacked by the algorithms.
q3571113171923293137Total3816405696121176280320456Attack114478111216202024Attack23816405696121176280320456From the table, we can find that all of the isomorphic classes ofE in the form of y2=x−βx−βq2x−βq4,β∈Fq6 can be attacked by our algorithms with deg ϕx=2 and reducible f.


## 3.3. Algorithms fordegϕ = 3

The whole progress of the experiment for degϕ=3 is similar to that for deg ϕ=2 with a few differences on the cover diagram and the equation system to be solved. So, for deg ϕ=3, we only introduce one circumstance that f can be written into the product of two irreducible polynomials of degree 3 and the map is as follows:It is obvious that the expression ofϕ1 is as follows:(29)ϕ1x=a3x3+a2x2+a1x+a0x−γx−γqx−γq2,where γ is one of the roots of f over Fq6 and ai∈Fq2. The expression of α and γ is same as that in algorithm for deg ϕ = 2 and f is reducible, while there are a few changes in the variables because of the different expression of ϕ1 and the existence of ν∈Fq6/Fq2:(30)ν=x7ω+x8ωq+⋯+x12ωq5,ai=x13+2iω+ωq2+ωq4+x14+2iωq+ωq3+ωq5,i∈0,1,2,3.From Lemma1, we can derive that the function ϕ1x−β has a multiple root ν, which must not be equal to α because of Riemann–Hurwitz formula:(31)ϕ1x−β=a3x3+a2x2+a1x+a0−βx−γx−γqx−γq2x−γx−γqx−γq2=0.Becauseϕ1x−β has two different roots α and ν with ν a double root, we can get the following equation:(32)a3x3+a2x2+a1x+a0−βx−γx−γpx−γp2=a3−βx−αx−ν2.From that, we can induce three equations, which can be transferred into a system of 18 equations with 20 variables through scalar restriction:(33)a0+βγγpγp2=−a3−βν2α,(34)a2+βγ+βγp+βγp2=−a3−β2ν+α,(35)a1−βγγp−βγpγp2−βγγp2=a3−βν2+2να.We should fix the value ofa3≠0 and other 2 variables to compute on a zero-dimension scheme. To derive the expression of ϕ2x,y, the value of a3 should be classified, one is a quadratic residue and the other is a quadratic nonresidue.


### 3.3.1. Statistical Analysis

After analyzing the solutions of a fixed hyperelliptic curve in a relatively small field, we can find thatν only has two different values ν1 and ν2 with ν2=ν1p3. Each choice of ν corresponds to an isomorphic class of elliptic curves, which conforms to the split Jacobian of H over Fq2. The relationship between the cover maps ϕ1x and Φ1x, related to ν1 and ν2 respectively, is Φ1x=ϕ1px, where the pth power over ϕ1 means pth power over each coefficient of ϕ1.It can be checked that the coefficients of the formula ofE2 equal to the pth power over those of E1, so E1 and E2 are in the same isogeny class. Because of the special relationship of ν, we consider that it may be possible to express ν by other unknown values, which will reduce 6 variables. Equations (33)–(35) can be used to preprocess these unknown data and the relationship is as follows:(36)ν=a3α+a2−βα+βγ+γp+γp22β−1.However, the substitute of the expression forν will make equation (18) forever admitted. After experiments begin with elliptic curves and hyperelliptic curves respectively, we give the following suggestions:(i)
If count#JHFq of a given hyperelliptic curve H is the goal, which means that the experiment is started with the hyperelliptic curve, ν should be expressed by ν=a3α+a2−βα+βγ+γp+γp2/2β−1, which can reduce 6 variables in the final equations. Because of the reduction in the number of both variables and restrictions, the dimension of the final ideal will decrease from 6 to 2, which will cut down the time complexity to a great extent.(ii)
If the cover attack on a given elliptic curve is the goal, which means that the experiment is started with the elliptic curve,ν can be expressed by either ν=x7ωqi+x8ωqi+1+⋯+x12ωqi+5,i∈0,1,…,5 or ν=a3α+a2−βα+βγ+γp+γp2/2β−1. The dimension of the ideal generated by restrictions is always 2 under both of the two expressions.


### 3.3.2. Algorithm Improvement

We now try to reduce the dimension of the final ideal, which will enhance the efficiency of the algorithm. The key point is to reduce the number of the varieties. The elliptic curvey2=x−βx−βq2x−βq4 may be written as y2=xx−1x−λ,λ∈Fq6 [32]. So, the map changes.The expression ofϕ1 is as follows:(37)ϕ1x=b0x−αx−ν2x−γx−γqx−γq2,where α and γ are the roots of f over Fq6 and b0,ν∈Fq6. The variables are as follows:(38)αi=αqi=x1εqi+εqi+3+x2εqi+1+εqi+4+x3εqi+2+εqi+5i∈0,1,2,γi=γqi=x4εqi+εqi+3+x5εqi+1+εqi+4+x6εqi+2+εqi+5i∈0,1,2,νi=νqi=x7εqi+x8εqi+1+⋯+x12εqi+5i∈0,1,…,5,b0=x13ω+x14ωq+⋯+x18ωq5.The restricted equations are as follows:(39)b0α2−α0α2−ν02=α2−γ0α2−γ1α2−γ2,b0ν2−α0ν2−ν02=ν2−γ0ν2−γ1ν2−γ2,b0ν4−α0ν4−ν02=λν4−γ0ν4−γ1ν4−γ2,b0α1−α0α1−ν02=λα1−γ0α1−γ1α1−γ2,which can be transferred into a system of 24 equations with 18 variables through scalar restriction. The dimension of the final ideal is 1 which is reduced by a half.If we start with hyperelliptic curves, whenα,γ are known, then the dimension of the final ideal in the previous algorithm is 2 so that we must try all of the possible values of the two free variables. After the improvement, we can get a system of 18 equations with 12 variables and the dimension of the final ideal is 0, which will reduce the time of traversing all values of the free variables.


## 3.3.1. Statistical Analysis

After analyzing the solutions of a fixed hyperelliptic curve in a relatively small field, we can find thatν only has two different values ν1 and ν2 with ν2=ν1p3. Each choice of ν corresponds to an isomorphic class of elliptic curves, which conforms to the split Jacobian of H over Fq2. The relationship between the cover maps ϕ1x and Φ1x, related to ν1 and ν2 respectively, is Φ1x=ϕ1px, where the pth power over ϕ1 means pth power over each coefficient of ϕ1.It can be checked that the coefficients of the formula ofE2 equal to the pth power over those of E1, so E1 and E2 are in the same isogeny class. Because of the special relationship of ν, we consider that it may be possible to express ν by other unknown values, which will reduce 6 variables. Equations (33)–(35) can be used to preprocess these unknown data and the relationship is as follows:(36)ν=a3α+a2−βα+βγ+γp+γp22β−1.However, the substitute of the expression forν will make equation (18) forever admitted. After experiments begin with elliptic curves and hyperelliptic curves respectively, we give the following suggestions:(i)
If count#JHFq of a given hyperelliptic curve H is the goal, which means that the experiment is started with the hyperelliptic curve, ν should be expressed by ν=a3α+a2−βα+βγ+γp+γp2/2β−1, which can reduce 6 variables in the final equations. Because of the reduction in the number of both variables and restrictions, the dimension of the final ideal will decrease from 6 to 2, which will cut down the time complexity to a great extent.(ii)
If the cover attack on a given elliptic curve is the goal, which means that the experiment is started with the elliptic curve,ν can be expressed by either ν=x7ωqi+x8ωqi+1+⋯+x12ωqi+5,i∈0,1,…,5 or ν=a3α+a2−βα+βγ+γp+γp2/2β−1. The dimension of the ideal generated by restrictions is always 2 under both of the two expressions.


## 3.3.2. Algorithm Improvement

We now try to reduce the dimension of the final ideal, which will enhance the efficiency of the algorithm. The key point is to reduce the number of the varieties. The elliptic curvey2=x−βx−βq2x−βq4 may be written as y2=xx−1x−λ,λ∈Fq6 [32]. So, the map changes.The expression ofϕ1 is as follows:(37)ϕ1x=b0x−αx−ν2x−γx−γqx−γq2,where α and γ are the roots of f over Fq6 and b0,ν∈Fq6. The variables are as follows:(38)αi=αqi=x1εqi+εqi+3+x2εqi+1+εqi+4+x3εqi+2+εqi+5i∈0,1,2,γi=γqi=x4εqi+εqi+3+x5εqi+1+εqi+4+x6εqi+2+εqi+5i∈0,1,2,νi=νqi=x7εqi+x8εqi+1+⋯+x12εqi+5i∈0,1,…,5,b0=x13ω+x14ωq+⋯+x18ωq5.The restricted equations are as follows:(39)b0α2−α0α2−ν02=α2−γ0α2−γ1α2−γ2,b0ν2−α0ν2−ν02=ν2−γ0ν2−γ1ν2−γ2,b0ν4−α0ν4−ν02=λν4−γ0ν4−γ1ν4−γ2,b0α1−α0α1−ν02=λα1−γ0α1−γ1α1−γ2,which can be transferred into a system of 24 equations with 18 variables through scalar restriction. The dimension of the final ideal is 1 which is reduced by a half.If we start with hyperelliptic curves, whenα,γ are known, then the dimension of the final ideal in the previous algorithm is 2 so that we must try all of the possible values of the two free variables. After the improvement, we can get a system of 18 equations with 12 variables and the dimension of the final ideal is 0, which will reduce the time of traversing all values of the free variables.


## 4. Comparison and Experiments in Large Field

### 4.1. Experiment fordegϕ = 2 and f is Reducible

We give a finite fieldFq, where q=2128+51. Defining the Fq2=Fqω, where ω2+2816727792924429820226\\78826339867420145ω+110523335847250297425127553909826919399=0. The elliptic curve is as follows:(40)y2=x3+172239620323233229419247395322935747591ω+709471952084141740544987103049080544x2+1340031173633824376141694586626415343ω+314722434322820250558954527683265133032x+246550361663906225233677317494912389706ω+164982211005580436237787851811362782805,whose order over Fq2 is a 256-bit prime 11579208923731619542357098500868790788814017019678814\\3794259065994099110169459, can be covered by the hyperelliptic curve:(41)y2=x6+306311310527212692259946066199443128485x5+193943191848831265697771169643215300617x4+314797135695827441215736098683454708828x3+127930997360388525283702304567680577582x2+33088624320475722625912703713756545590x+151542072040419560972364007312137119174,which can be written into x−αx−αqx−αq2x−γx−γqx−γq2. The cover map is ϕx,y=ϕ1x,ϕ2x,y with(42)ϕ1x=x2+29567739429855780381390627507299503045xx−ω2,ϕ2x,y=77929664848720938013803267758033739311ω+241747055078217882048817891777938173676denoy,where deno=x3+340282366920938463463374607431768211504ωx2+175828762885486444322087343275702374086ω+8712359379187571187991945702287453310x+158699887406621358130832199000196489929ω+64007504960173741311415206434389648547According to Proposition1, we can get #JHFq=115792089237316195423570985008687907888140170196788143794259065994099110169459, who has 128-bit classical security. It can be inspected that the bit length of #JHFq is exactly equal to that of #Fq2. To verify #JHFq=#EFq2, we choose a generator P≔x2+150913657533727611905843392768639859536x+192004685511885787947420503238744174403,158529613564563458193984811054348483327x+89887585956944706258568021473948516109,2 of JHFq and compute that #EFq2P=1,0,0.


### 4.2. Example fordegϕ  = 3 and f is Reducible

Giving the finite fieldFq with q=210+7 and Fq2=Fqω with ω2+445ω+152=0. Let us begin classically with the elliptic curve:(43)E/Fq2:y2=x3+240ω+755x2+3414ω+592x+80ω+478.It can be covered by the following hyperelliptic curve:(44)H/Fp:y2=x6+x2+968x+337.fx can be written into x−αx−αqx−αq2x−γx−γqx−γq2,α,γ∈Fq3/Fq with α a root of(45)x3+531x2+265x+211=0.and γ a root of(46)x3+500x2+233x+285=0.The cover map isϕx,y=ϕ1x,ϕ2x,y with(47)ϕ1x=ωx3+589ω+879x2+365ω+41x+355ω+506x−γx−γpx−γp2.ϕ2x,y=960ω+789x3+177ω+21x2+56ω+793x+986ω+449x6+1000x5+964x4+564x3+90x2+842x+807y.We can also get that the order of the Jacobian ofH over Fq is 1064295, whose bit length is equal to the bit length of #Fq2. This example illustrates that our algorithms can also apply to the case, in which #EFq2=#JHFq is not a prime.


### 4.3. Comparison

Here, we offer comparisons between our algorithms and existing cover attacks for ECDLP (resp. counting methods for Jacobians of hyperelliptic curves).As a kind of cover attack for ECDLP, the method in the study has same complexityO˜q as GHS attack, which is the most efficient algorithm for general elliptic curves.As a counting method for Jacobians of hyperelliptic curves, our algorithms can easily compute the cover map for hyperelliptic curvesy2=fx=x−αx−αqx−αq2x−γx−γqx−γq2, where α+γωq+ω=2αγ+ωq+1, ω∈Fq2/Fq is the generator of Fq2, α,γ∈Fq3/Fq. To be noted that, there is no subexponential general algorithm for some small sets of examples [11]. The algorithm in reference [4] dealt with hyperelliptic curves of form y2=rx6+sx4+σsx2+σr, where σ is the generator of the Galois group of a quadratic extension. For random hyperelliptic curves [12], an experiment is run for about one week for a genus 2 curve defined over an 80-bit field.


## 4.1. Experiment fordegϕ = 2 and f is Reducible

We give a finite fieldFq, where q=2128+51. Defining the Fq2=Fqω, where ω2+2816727792924429820226\\78826339867420145ω+110523335847250297425127553909826919399=0. The elliptic curve is as follows:(40)y2=x3+172239620323233229419247395322935747591ω+709471952084141740544987103049080544x2+1340031173633824376141694586626415343ω+314722434322820250558954527683265133032x+246550361663906225233677317494912389706ω+164982211005580436237787851811362782805,whose order over Fq2 is a 256-bit prime 11579208923731619542357098500868790788814017019678814\\3794259065994099110169459, can be covered by the hyperelliptic curve:(41)y2=x6+306311310527212692259946066199443128485x5+193943191848831265697771169643215300617x4+314797135695827441215736098683454708828x3+127930997360388525283702304567680577582x2+33088624320475722625912703713756545590x+151542072040419560972364007312137119174,which can be written into x−αx−αqx−αq2x−γx−γqx−γq2. The cover map is ϕx,y=ϕ1x,ϕ2x,y with(42)ϕ1x=x2+29567739429855780381390627507299503045xx−ω2,ϕ2x,y=77929664848720938013803267758033739311ω+241747055078217882048817891777938173676denoy,where deno=x3+340282366920938463463374607431768211504ωx2+175828762885486444322087343275702374086ω+8712359379187571187991945702287453310x+158699887406621358130832199000196489929ω+64007504960173741311415206434389648547According to Proposition1, we can get #JHFq=115792089237316195423570985008687907888140170196788143794259065994099110169459, who has 128-bit classical security. It can be inspected that the bit length of #JHFq is exactly equal to that of #Fq2. To verify #JHFq=#EFq2, we choose a generator P≔x2+150913657533727611905843392768639859536x+192004685511885787947420503238744174403,158529613564563458193984811054348483327x+89887585956944706258568021473948516109,2 of JHFq and compute that #EFq2P=1,0,0.


## 4.2. Example fordegϕ  = 3 and f is Reducible

Giving the finite fieldFq with q=210+7 and Fq2=Fqω with ω2+445ω+152=0. Let us begin classically with the elliptic curve:(43)E/Fq2:y2=x3+240ω+755x2+3414ω+592x+80ω+478.It can be covered by the following hyperelliptic curve:(44)H/Fp:y2=x6+x2+968x+337.fx can be written into x−αx−αqx−αq2x−γx−γqx−γq2,α,γ∈Fq3/Fq with α a root of(45)x3+531x2+265x+211=0.and γ a root of(46)x3+500x2+233x+285=0.The cover map isϕx,y=ϕ1x,ϕ2x,y with(47)ϕ1x=ωx3+589ω+879x2+365ω+41x+355ω+506x−γx−γpx−γp2.ϕ2x,y=960ω+789x3+177ω+21x2+56ω+793x+986ω+449x6+1000x5+964x4+564x3+90x2+842x+807y.We can also get that the order of the Jacobian ofH over Fq is 1064295, whose bit length is equal to the bit length of #Fq2. This example illustrates that our algorithms can also apply to the case, in which #EFq2=#JHFq is not a prime.


## 4.3. Comparison

Here, we offer comparisons between our algorithms and existing cover attacks for ECDLP (resp. counting methods for Jacobians of hyperelliptic curves).As a kind of cover attack for ECDLP, the method in the study has same complexityO˜q as GHS attack, which is the most efficient algorithm for general elliptic curves.As a counting method for Jacobians of hyperelliptic curves, our algorithms can easily compute the cover map for hyperelliptic curvesy2=fx=x−αx−αqx−αq2x−γx−γqx−γq2, where α+γωq+ω=2αγ+ωq+1, ω∈Fq2/Fq is the generator of Fq2, α,γ∈Fq3/Fq. To be noted that, there is no subexponential general algorithm for some small sets of examples [11]. The algorithm in reference [4] dealt with hyperelliptic curves of form y2=rx6+sx4+σsx2+σr, where σ is the generator of the Galois group of a quadratic extension. For random hyperelliptic curves [12], an experiment is run for about one week for a genus 2 curve defined over an 80-bit field.


## 5. Conclusion

In the article, we propose a new method to compute the cover map from hyperelliptic curves of genus 2 to the elliptic curves with prime order. To conduct the experiments successfully, we put forward some important lemmas and propositions first. Then, we propose three different algorithms according to the different degrees ofϕ and the different forms of equations of hyperelliptic curves. As an application, we also give examples in relatively large fields. Under the existence of the cover map, we can use it to substitute the GHS attack in cover and decomposition attack in some specific cases. We can also use the algorithms to evaluate the order of the Jacobians of hyperelliptic curves in polynomial time, which can be generalized to generating required hyperelliptic curves. It should be improved that our algorithms apply to a particular part of elliptic curves and hyperelliptic curves, but the method is still very useful in the ECC and HECC.For the further areas related to this work, we can probe the following two directions:(i)
About Finding the More Concrete Form of the Hyperelliptic Curves or Elliptic Curves. We take Proposition 3 as an example. According to the relationship between α and γ in Proposition 3, we can reduce the number of the variates, thus enhancing the efficiency of our algorithm. So, the more concrete form of hyperelliptic or elliptic curves may improve the efficiency.(ii)
About the Fast Solution Method Nonlinear Systems. We now use scalar restriction and Groebner basis to get the solutions of the equations, thus getting the expressions of the cover maps and the corresponding hyperelliptic curves. The further research may investigate faster way to solve nonlinear systems.



---

*Source: 9833393-2022-07-04.xml*