# Computing the Characteristic Polynomials of a Class of Hyperelliptic Curves for Cryptographic Applications

Authors: Lin You; Guangguo Han; Jiwen Zeng; Yongxuan Sang
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

Hyperelliptic curves have been widely studied for cryptographic applications, and some special
hyperelliptic curves are often considered to be used in practical cryptosystems. Computing Jacobian group orders is an important operation in constructing hyperelliptic curve cryptosystems,
and the most common method used for the computation of Jacobian group orders is by computing
the zeta functions or the characteristic polynomials of the related hyperelliptic curves. For the
hyperelliptic curveCq: v2=up+au+b over the field 𝔽q with q being a power of an odd prime p, Duursma and Sakurai obtained its characteristic polynomial for q=p, a=−1, and b∈𝔽p. In
this paper, we determine the characteristic polynomials of Cq over the finite field 𝔽pn for n=1, 2 and a, b∈Fpn. We also give some computational data which show that many of those curves
have large prime factors in their Jacobian group orders, which are both practical and vital for the
constructions of efficient and secure hyperelliptic curve cryptosystems.


---

## Body

## 1. Introduction and Main Results

### 1.1. Hyperelliptic Curves and Cryptosystems

A hyperelliptic curveC of genus g over 𝔽q is defined by an equation of the form(1.1)v2+h(u)v=f(u),
where h(u), f(u)∈𝔽q[u] with degu(h)≤g and degu(f)=2g+1, and the equation system v2+h(u)v=f(u), 2v+h(u)=0, and h′(u)v-f′(u)=0 has no solutions in 𝔽¯q×𝔽¯q.For an extension𝕂 of 𝔽q, the set (1.2)C(K)={(x,y)∈K×K∣y2+h(x)y=f(x)}∪{∞}
is called the set of 𝕂-rational points on C. The symbol ∞ is called the point at infinity, and the other points are called finite points.AdivisorD is defined as a finite formal sum of finite points or the infinity ∞, while the Jacobian group (or simply calledJacobian) of the curve C over 𝕂 is an Abelian group composed of some special divisors (i.e., reduced divisors) on C. This Jacobian group is generally denoted as 𝕁C(𝕂). A hyperelliptic curve cryptosystem (HECC) is a cryptosystem constructed on the Jacobian group of the hyperelliptic curve over a finite field. For example, the hyperelliptic curve digital signature algorithm (HECDSA) is a hyperelliptic curve version of an elliptic curve digital signature algorithm (ECDSA). The security of an HECC is based on the discrete logarithm problems in the corresponding Jacobian group.Since HECC was invented by Koblitz [1] in 1989, it has been extensively researched, and now it has been considered for practical cryptographic applications. For a certain number of classes of hyperelliptic curves with some specific parameters, the corresponding HECC can even possess lower complexities than an elliptic curve cryptosystem but with the same level of security [2].In order to construct a secure HECC, one first has to choose a hyperelliptic curve over a finite field and then compute the order of the hyperelliptic curve Jacobian group. If the order does not have a large prime factor, then the discrete logarithm problems in this Jacobian group may not be hard enough to guarantee the security of the HECC, and so the hyperelliptic curve is not suitable for cryptographic uses and should be chosen again to ensure that the Jacobian group order has some large prime factor. But, in most cases, this computation is a very time-consuming task. Hence, the computation of Jacobian group order is a very important step for the efficient implementation of HECC.


### 1.2. Zeta Functions and Jacobian Group Orders

The most common method used for the computation of Jacobian group orders is by computing the numerator of the zeta functions of the related hyperelliptic curves, or by computing the characteristic polynomial of the hyperelliptic curve. The following results are due to the Weil's theorem [3, 4] and Kedlaya's algorithm [5].LetC be a hyperelliptic curve of (1.1) over 𝔽q. For any positive integer r, let Nr denote the number of 𝔽qr-rational points on C. The zeta function of C is defined as (1.3)Z(t)=Z(C;t)=exp⁡(∑r=1∞Nrtrr).Then(a)
Z(t) is a rational function over ℤ and can be written as Q(t)/(1-t)(1-qt), where Q(t)∈ℤ[t],(b)
there exist complex numbersτi(i=1,…,2g) with |τi|=q such that
(1.4)Q(t)=∏i=12g(1-τit),Nr=qr+1-∑i=12gτir,(c)
the integer coefficient polynomial(1.5)P(t)=t2gQ(1t)=∏i=12g(t-τi)
is called the characteristic polynomial of the Frobenius endomorphism on 𝕁C(𝔽q) (it is also called the characteristic polynomial of C over 𝔽q), and it is can be expressed as
(1.6)P(t)=t2g+a1t2g-1+⋯+agtg+qag-1tg-1+⋯+qg-1a1t+qg,
where for 1≤i≤g,
(1.7)iai=(Ni-qi-1)+(Ni-1-qi-1-1)a1+⋯+(N1-q-1)ai-1,(d)
for any positive integern, the order of 𝕁C(𝔽qn) is given as
(1.8)#JC(Fqn)=∏i=12g(1-τin).Hence, for any positive integern, the order of 𝕁C(𝔽qn) can be computed if P(t) is determined or if Nr(1≤r≤g) are computed.For a positive integerj, the quadratic character χj of 𝔽qj is defined as (1.9)χj:α⟼{1ifαisaquadraticresidueinFqj,0ifα=0,-1ifαisanon-quadraticresidueinFqj.Obviously,χj(αβ)=χj(α)χj(β) holds for any α,β∈𝔽qj. By using χj, we can compute Nj as(1.10)Nj=1+|{(x,y)∈Fqj×Fqj∣y2=f(x)}|=1+∑x∈Fqj(χj(f(x))+1)=qj+1+∑x∈Fqjχj(f(x)).
While for any positive integer j and every field element α∈𝔽qj, the value of the extended quadratic character χj at α can be computed as χj(α)=α(qj-1)/2 in 𝔽q.


### 1.3. Our Main Results

LetCq be the curve with the equation(1.11)Cq:v2=up+au+boverFq,
where a≠0 and q is a power of an odd prime p. Then Cq is a hyperelliptic curve of genus (p-1)/2. In [6], Duursma and Sakurai presented Q(t) of Cq for q=p and a=-1. That is, the numerator of the corresponding zeta function is given as(1.12)Q(t)=∏k=1p-1(1-(kp)ζkp̃t)or∏k=1p-1(1+(kp)ζkp̃t),
respectively, where p̃=(-1/p)p, p̃=-(-1/p)∑k=1p-1(k/p)ζk, ζ is a p-th unity root, and (k/p) denotes the Legendre symbol.In this paper, we compute the characteristic polynomials ofCq with a,b∈𝔽q (q=pn, n=1,2) and get the following Table 1.Table 1
The characteristic polynomials of the curvev2=up+au+b over 𝔽pn.
nabP(t) over 𝔽pnNotes1−1b=0(t2-p̃)(p-1)/21b∈𝔽p(t2+p)(p-1)/2a primitive root modulopb∈𝔽ptp-1+p(p-1)/2ord𝔽p*(a)=mb∈𝔽p(tm+(-1/p)(-p)m/2)(p-1)/mm is even2<m<p-1(t2m+pm)(p-1)/2mm is odd2−1b=0(t-p̃)p-1b(≠0)∈𝔽p2(tp-p̃p)/(t-p̃)1b∈𝔽p(t+p)p-1b∉𝔽p(tp+pp)/(t+p)a primitive root ofpb∈𝔽p2(t(p-1)/2+p(p-1)/2)2ord𝔽p*(a)=mb∈𝔽p2(tm/2+(-1/p)(-p)m/2)2(p-1)/mm is even2<m<p-1(tm+pm)(p-1)/mm is odda∉𝔽p, m=ord𝔽p2*(a)b∈𝔽p2(te+(-1)e(p+1)/m+e-1pe)(p-1)/ee(>1) is the smallest s.t. m∣e(p+1).a∉𝔽p, ap+1=1b=0, or a=b1-p(t+a(p+1)/2p)p-1b≠0, a≠b1-p(tp+pp)/(t+p)From the characteristic polynomials of the hyperelliptic curveCp over 𝔽pn, the orders of Jacobian groups 𝕁Cp(𝔽pn) can be easily computed as(1.13)#JCp(Fpn)=∏i=1p-1(1-τin).
For example, if a is a primitive element modulo p, then the characteristic polynomial of Cp is (1.14)P(t)=tp-1+p(p-1)/2=∏ζp-1=1(t-ζλp),
where λ satisfies λp-1+1=0. Hence, the order of the Jacobian group of Cp over 𝔽pn is
(1.15)#JCp(Fpn)=∏ζp-1=1(1-(ζλp)n).Ifn is an integer coprime to p-1, let η=ζn; then η will also run through all these roots when ζ runs through the all roots of xp-1-1=0. Hence, we have (1.16)∏ζp-1=1(1-(ζλp)n)=∏ζp-1=1(1-ζn(λp)n)=∏ηp-1=1(1-η(λp)n)=1-((λp)n)p-1=1-(λp-1)n((p)n)p-1=1-(-1)n(p)n(p-1)=1+pn(p-1).Ifn is an integer not coprime to p-1, let d be the factor of n such that gcd(n/d,p-1)=1, then we have (1.17)∏ζp-1=1(1-(ζλp)n)=∏ζp-1=1(1-((ζλp)n/d)d)=∏ζp-1=1(∏ξd=1(1-ξ(ζλp)n/d))=∏ξd=1(∏ζp-1=1(1-ξ(ζλp)n/d))=∏ξd=1(∏ζp-1=1(1-ζn/d(ξd/nλp)n/d))=∏ξd=1(1-((ξd/nλp)n/d)p-1)=∏ξd=1(1-ξp-1λn(p-1)/dpn(p-1)/d)=∏ξd=1(1-λn(p-1)/dpn(p-1)/d)=(1-(-1)n/dpn(p-1)/d)d.
That is, for any positive integer n, the order of the Jacobian group of the curve Cp over 𝔽pn with a being a primitive element modulo p can be computed as (1.18)#JCp(Fpn)=(1-(-1)n/dpn(p-1)/d)d,
where d is the factor of n such that gcd(n/d,p-1)=1.In Table2, we give some essential parameters with which the Jacobian group order of Cq has some large prime factors, which shows that the Cq with these parameters may be used for cryptographic applications.Table 2
Some cases in whichCq have reducible characteristic polynomials.
nab−1011∈𝔽p2<ord𝔽p*(a)<p-1∈𝔽p−101∈𝔽p2a primitive root ofp∈𝔽p22<ord𝔽p*(a)<p-1∈𝔽p2a∉𝔽p, a nonprimitive root of p2∈𝔽p2a∉𝔽p,ap+1=10 ora=b1-p


## 1.1. Hyperelliptic Curves and Cryptosystems

A hyperelliptic curveC of genus g over 𝔽q is defined by an equation of the form(1.1)v2+h(u)v=f(u),
where h(u), f(u)∈𝔽q[u] with degu(h)≤g and degu(f)=2g+1, and the equation system v2+h(u)v=f(u), 2v+h(u)=0, and h′(u)v-f′(u)=0 has no solutions in 𝔽¯q×𝔽¯q.For an extension𝕂 of 𝔽q, the set (1.2)C(K)={(x,y)∈K×K∣y2+h(x)y=f(x)}∪{∞}
is called the set of 𝕂-rational points on C. The symbol ∞ is called the point at infinity, and the other points are called finite points.AdivisorD is defined as a finite formal sum of finite points or the infinity ∞, while the Jacobian group (or simply calledJacobian) of the curve C over 𝕂 is an Abelian group composed of some special divisors (i.e., reduced divisors) on C. This Jacobian group is generally denoted as 𝕁C(𝕂). A hyperelliptic curve cryptosystem (HECC) is a cryptosystem constructed on the Jacobian group of the hyperelliptic curve over a finite field. For example, the hyperelliptic curve digital signature algorithm (HECDSA) is a hyperelliptic curve version of an elliptic curve digital signature algorithm (ECDSA). The security of an HECC is based on the discrete logarithm problems in the corresponding Jacobian group.Since HECC was invented by Koblitz [1] in 1989, it has been extensively researched, and now it has been considered for practical cryptographic applications. For a certain number of classes of hyperelliptic curves with some specific parameters, the corresponding HECC can even possess lower complexities than an elliptic curve cryptosystem but with the same level of security [2].In order to construct a secure HECC, one first has to choose a hyperelliptic curve over a finite field and then compute the order of the hyperelliptic curve Jacobian group. If the order does not have a large prime factor, then the discrete logarithm problems in this Jacobian group may not be hard enough to guarantee the security of the HECC, and so the hyperelliptic curve is not suitable for cryptographic uses and should be chosen again to ensure that the Jacobian group order has some large prime factor. But, in most cases, this computation is a very time-consuming task. Hence, the computation of Jacobian group order is a very important step for the efficient implementation of HECC.


## 1.2. Zeta Functions and Jacobian Group Orders

The most common method used for the computation of Jacobian group orders is by computing the numerator of the zeta functions of the related hyperelliptic curves, or by computing the characteristic polynomial of the hyperelliptic curve. The following results are due to the Weil's theorem [3, 4] and Kedlaya's algorithm [5].LetC be a hyperelliptic curve of (1.1) over 𝔽q. For any positive integer r, let Nr denote the number of 𝔽qr-rational points on C. The zeta function of C is defined as (1.3)Z(t)=Z(C;t)=exp⁡(∑r=1∞Nrtrr).Then(a)
Z(t) is a rational function over ℤ and can be written as Q(t)/(1-t)(1-qt), where Q(t)∈ℤ[t],(b)
there exist complex numbersτi(i=1,…,2g) with |τi|=q such that
(1.4)Q(t)=∏i=12g(1-τit),Nr=qr+1-∑i=12gτir,(c)
the integer coefficient polynomial(1.5)P(t)=t2gQ(1t)=∏i=12g(t-τi)
is called the characteristic polynomial of the Frobenius endomorphism on 𝕁C(𝔽q) (it is also called the characteristic polynomial of C over 𝔽q), and it is can be expressed as
(1.6)P(t)=t2g+a1t2g-1+⋯+agtg+qag-1tg-1+⋯+qg-1a1t+qg,
where for 1≤i≤g,
(1.7)iai=(Ni-qi-1)+(Ni-1-qi-1-1)a1+⋯+(N1-q-1)ai-1,(d)
for any positive integern, the order of 𝕁C(𝔽qn) is given as
(1.8)#JC(Fqn)=∏i=12g(1-τin).Hence, for any positive integern, the order of 𝕁C(𝔽qn) can be computed if P(t) is determined or if Nr(1≤r≤g) are computed.For a positive integerj, the quadratic character χj of 𝔽qj is defined as (1.9)χj:α⟼{1ifαisaquadraticresidueinFqj,0ifα=0,-1ifαisanon-quadraticresidueinFqj.Obviously,χj(αβ)=χj(α)χj(β) holds for any α,β∈𝔽qj. By using χj, we can compute Nj as(1.10)Nj=1+|{(x,y)∈Fqj×Fqj∣y2=f(x)}|=1+∑x∈Fqj(χj(f(x))+1)=qj+1+∑x∈Fqjχj(f(x)).
While for any positive integer j and every field element α∈𝔽qj, the value of the extended quadratic character χj at α can be computed as χj(α)=α(qj-1)/2 in 𝔽q.


## 1.3. Our Main Results

LetCq be the curve with the equation(1.11)Cq:v2=up+au+boverFq,
where a≠0 and q is a power of an odd prime p. Then Cq is a hyperelliptic curve of genus (p-1)/2. In [6], Duursma and Sakurai presented Q(t) of Cq for q=p and a=-1. That is, the numerator of the corresponding zeta function is given as(1.12)Q(t)=∏k=1p-1(1-(kp)ζkp̃t)or∏k=1p-1(1+(kp)ζkp̃t),
respectively, where p̃=(-1/p)p, p̃=-(-1/p)∑k=1p-1(k/p)ζk, ζ is a p-th unity root, and (k/p) denotes the Legendre symbol.In this paper, we compute the characteristic polynomials ofCq with a,b∈𝔽q (q=pn, n=1,2) and get the following Table 1.Table 1
The characteristic polynomials of the curvev2=up+au+b over 𝔽pn.
nabP(t) over 𝔽pnNotes1−1b=0(t2-p̃)(p-1)/21b∈𝔽p(t2+p)(p-1)/2a primitive root modulopb∈𝔽ptp-1+p(p-1)/2ord𝔽p*(a)=mb∈𝔽p(tm+(-1/p)(-p)m/2)(p-1)/mm is even2<m<p-1(t2m+pm)(p-1)/2mm is odd2−1b=0(t-p̃)p-1b(≠0)∈𝔽p2(tp-p̃p)/(t-p̃)1b∈𝔽p(t+p)p-1b∉𝔽p(tp+pp)/(t+p)a primitive root ofpb∈𝔽p2(t(p-1)/2+p(p-1)/2)2ord𝔽p*(a)=mb∈𝔽p2(tm/2+(-1/p)(-p)m/2)2(p-1)/mm is even2<m<p-1(tm+pm)(p-1)/mm is odda∉𝔽p, m=ord𝔽p2*(a)b∈𝔽p2(te+(-1)e(p+1)/m+e-1pe)(p-1)/ee(>1) is the smallest s.t. m∣e(p+1).a∉𝔽p, ap+1=1b=0, or a=b1-p(t+a(p+1)/2p)p-1b≠0, a≠b1-p(tp+pp)/(t+p)From the characteristic polynomials of the hyperelliptic curveCp over 𝔽pn, the orders of Jacobian groups 𝕁Cp(𝔽pn) can be easily computed as(1.13)#JCp(Fpn)=∏i=1p-1(1-τin).
For example, if a is a primitive element modulo p, then the characteristic polynomial of Cp is (1.14)P(t)=tp-1+p(p-1)/2=∏ζp-1=1(t-ζλp),
where λ satisfies λp-1+1=0. Hence, the order of the Jacobian group of Cp over 𝔽pn is
(1.15)#JCp(Fpn)=∏ζp-1=1(1-(ζλp)n).Ifn is an integer coprime to p-1, let η=ζn; then η will also run through all these roots when ζ runs through the all roots of xp-1-1=0. Hence, we have (1.16)∏ζp-1=1(1-(ζλp)n)=∏ζp-1=1(1-ζn(λp)n)=∏ηp-1=1(1-η(λp)n)=1-((λp)n)p-1=1-(λp-1)n((p)n)p-1=1-(-1)n(p)n(p-1)=1+pn(p-1).Ifn is an integer not coprime to p-1, let d be the factor of n such that gcd(n/d,p-1)=1, then we have (1.17)∏ζp-1=1(1-(ζλp)n)=∏ζp-1=1(1-((ζλp)n/d)d)=∏ζp-1=1(∏ξd=1(1-ξ(ζλp)n/d))=∏ξd=1(∏ζp-1=1(1-ξ(ζλp)n/d))=∏ξd=1(∏ζp-1=1(1-ζn/d(ξd/nλp)n/d))=∏ξd=1(1-((ξd/nλp)n/d)p-1)=∏ξd=1(1-ξp-1λn(p-1)/dpn(p-1)/d)=∏ξd=1(1-λn(p-1)/dpn(p-1)/d)=(1-(-1)n/dpn(p-1)/d)d.
That is, for any positive integer n, the order of the Jacobian group of the curve Cp over 𝔽pn with a being a primitive element modulo p can be computed as (1.18)#JCp(Fpn)=(1-(-1)n/dpn(p-1)/d)d,
where d is the factor of n such that gcd(n/d,p-1)=1.In Table2, we give some essential parameters with which the Jacobian group order of Cq has some large prime factors, which shows that the Cq with these parameters may be used for cryptographic applications.Table 2
Some cases in whichCq have reducible characteristic polynomials.
nab−1011∈𝔽p2<ord𝔽p*(a)<p-1∈𝔽p−101∈𝔽p2a primitive root ofp∈𝔽p22<ord𝔽p*(a)<p-1∈𝔽p2a∉𝔽p, a nonprimitive root of p2∈𝔽p2a∉𝔽p,ap+1=10 ora=b1-p


## 2. Isomorphic Curves, Twisted Curves, and Their Characteristic Polynomials

Two hyperelliptic curves of the same genus over the field𝔽 are called isomorphic over 𝔽 if they are isomorphic as projective varieties over 𝔽. If C1 and C2 are isomorphic over 𝔽, then their Jacobian groups 𝕁C1(𝔽) and 𝕁C2(𝔽) are also isomorphic [7]. Hence, the hyperelliptic curve cryptosystem based on the Jacobian group of C1 is equivalent to that based on the Jacobian group of C2.From [8], we know how to the hyperelliptic curves are isomorphic. Precisely, suppose C1 and C2 are two hyperelliptic curves of the equation forms Hi:v2+hi(u)v=fi(u)(i=1,2), respectively, with hi(u), fi(u) (monic) ∈𝔽[u], deg(hi(u))≤g, and deg(fi(u))=2g+1. Then C1 and C2 are isomorphic over 𝔽 if and only if there exist s∈𝔽⋆, t∈𝔽, and r(u)∈𝔽[u] with deg(r(u))≤g, such that H1 can be transformed into H2 through the coordinate change: (2.1)(u,v)⟼(s2u+t,s2g+1v+r(u)).In our case, a hyperelliptic curveCq′ is isomorphic to the hyperelliptic curve Cq if and only if there exist s∈𝔽q* and t∈𝔽q such that Cq′  has the equation form (2.2)v2=up+s2(p-1)au+s2p(tp+at+b).Ifq=p, then Cq′ has the equation form (2.3)v2=up+au+s2((1+a)t+b),s≠0.By using (1.10), we can easily show that if C1 and C2 are isomorphic then their characteristic polynomials P1(t) and P2(t) are equal.Theorem 2.1.
Leta0=1 and
(2.4)C:v2=∑i=02g+1aiu2g+1-i
be a hyperelliptic curve of genus g over 𝔽q of odd characteristic p, and P(t)  its characteristic polynomial. Let γ be a quadratic nonresidue in 𝔽q. Then, the hyperelliptic curve
(2.5)C′:v2=∑i=02g+1γiaiu2g+1-i
has the characteristic polynomial P′(t)=P(-t).Proof.
LetNj′ denote the number of rational points of the hyperelliptic curve C′ over 𝔽qj and χj denote the extended quadratic character of 𝔽qj. Then, since
(2.6)χj(γ)=γ((q-1)/2)(qj-1+⋯+q+1)=(χ1(γ))qj-1+⋯+q+1=(-1)j,
hence, according to (1.10), we have
(2.7)Nj′=qj+1+∑x∈Fqjχj(∑i=02g+1γiaix2g+1-i)=qj+1+∑x∈Fqjχj(∑i=02g+1γiai(γx)2g+1-i)=qj+1+∑x∈Fqjχj(γ)2g+1χj(∑i=02g+1aix2g+1-i)=qj+1+∑x∈Fqj(-1)jχj(∑i=02g+1aix2g+1-i)={Nj,jiseven,2(qj+1)-Nj,jisodd.
It follows P′(t)=P(-t) from (1.6), (1.7), and (1.10).The hyperelliptic curveC′ is called atwisted curve of C over 𝔽q by γ. For the curve Cq, its twisted curve is a hyperelliptic curve of the equation (2.8)v2=up+γp-1au+γpb
with γ a quadratic nonresidue in 𝔽q.In the following, we compute the characteristic polynomials ofCq over 𝔽q with q=pn.Case 1.
For the curveCp:v2=up+au+b with a=-1 and 0≠b∈𝔽p, Cp has (p-1)/2 isomorphic curves over 𝔽p, which are
(2.9)v2=up-u+s2b,s=1,2,⋯,(p-1)2.
Hence, there are three isomorphism classes of hyperelliptic curves Cp over 𝔽p which are denoted as 𝒞p(-1,0), 𝒞p(-1,+) and 𝒞p(-1,-), respectively,
(2.10)Cp(-1,0)={v2=up-u},Cp(-1,+)={v2=up-u+b+∣b+isaquadraticresiduemodulop},Cp(-1,-)={v2=up-u+b-∣b-isaquadraticnonresiduemodulop}.
Ifv2=up-u+b+∈𝒞p(-1,+) and γ is a quadratic nonresidue modulo p, then its twisted curve v2=up-γp-1u+γpb+ or v2=up-u+γb+ belongs to 𝒞p(-1,-).
According to [9], we know that the characteristic polynomial of the hyperelliptic curve v2=up-u over 𝔽p is
(2.11)PCp(-1,0)(t)=(t2-p̃)(p-1)/2.
While for all the curves in𝒞p(-1,+) or 𝒞p(-1,-), their characteristic polynomials were proved by Duursma [9] to be
(2.12)∏k=1p-1(t-(kp)ζkp̃)or∏k=1p-1(t+(kp)ζkp̃),
respectively.For examples, the curvev2=u5-u over 𝔽5 and the curve v2=u7-u over 𝔽7 have the characteristic polynomial (t2-5)2 and P(t)=(t2+7)3, respectively. The curves in 𝒞5(-1,+) or 𝒞7(-1,+) have the characteristic polynomial t4+5t3+15t2+25t+25 or t6+7t5+21t4+49t3+147t2+343t+343, respectively. The curves in 𝒞5(-1,-) or 𝒞7(-1,-) have the characteristic polynomial t4-5t3+15t2-25t+25 or t6-7t5+21t4-49t3+147t2-343t+343, respectively.Case 2.
Over𝔽p2, the hyperelliptic curve v2=up+u is a quotient of the Hermitian curve vp+1=up+u which is maximal, and this leads to that over 𝔽p2, v2=up+u has the characteristic polynomial [10](2.13)P(t)=(t+p)p-1.Based on the following Theorem2.6, for any b∈𝔽p, the curve v2=up+u+b is isomorphic to v2=up+u. Thus, v2=up+u+b over 𝔽p2 also has the characteristic polynomial (2.13). And it follows that the characteristic polynomial of v2=up+u+b over 𝔽p equals to(2.14)P(t)=(t2+p)(p-1)/2.Case 3.
Supposea≠0,±1. Then for the fixed a and all b∈𝔽p, all the hyperelliptic curves v2=up+au+b are isomorphic. Hence, each of these curves is isomorphic to its twisted curve. Thus, the coefficients of the terms of odd degrees in their corresponding characteristic polynomials are zero. In fact, we have the following Lemma 2.2.Lemma 2.2.
Supposep is an odd prime number, a∈𝔽p, and r is a positive integer satisfying 1≤r≤(p-1)/2. Then
(2.15)∑x∈Fprχr(xp+ax)=0
holds if one of the following three conditions is satisfied:(1)
r=2 or r is odd;(2)
r(>2) is even and a is a primitive root modulo p.Proof.
Supposer is odd, and let γ be a quadratic nonresidue in 𝔽p. Then, we have
(2.16)∑x∈Fprχr(xp+ax)=∑xγ∈Fprχr((xγ)p+axγ)=∑x∈Fprχr(γ)χr(xp+ax)=(-1)r∑x∈Fprχr(xp+ax)=-∑x∈Fprχr(xp+ax),
and it follows ∑x∈𝔽prχr(xp+ax)=0.
Letr=2 or r even and a a primitive root modulo p. We first show that xp+ax will run through 𝔽pr if x runs through 𝔽pr. It is equivalent to show that for any x∈𝔽pr, if x≠0, then xp+ax≠0. That is, we have to show that the equation xp+ax=0 has no nonzero solution in 𝔽pr.
Assume thatx0 is a nonzero root of xp+ax=0 in 𝔽pr, that is, x0p=-ax0. Then we have x0p2=-ax0p=(-1)2a2x0, and it follows x0pr=(-a)r-1x0p=(-1)rarx0, that is, x0=arx0 or x0(1-ar)=0. Thus, x0=0 or ar=1, it is impossible. Therefore,
(2.17)∑x∈Fprχr(xp+ax)=∑x∈Fprχr(x)=0.Lemma 2.3.
For any odd prime numberp, we have
(2.18)∑x∈Fprχr(xp+x)={0ifrisodd,(-1)r/2-1pr/2(p-1)ifrisevenandnolargerthanp.Proof.
∑x∈𝔽prχr(xp+x)=0 comes directly from Lemma 2.2 if r is odd.
Supposer is even and r≤p-1. Let ak(0≤k≤p-1) be the coefficients of the characteristic polynomial (2.14); then ak=0 if k is odd, and
(2.19)ak=pk/2⋅(p-1)(p-3)⋯(p-k+1)2k/2⋅(k/2)!
if k is even. Thus, from (1.7), we have
(2.20)kak=∑x∈Fpkχk(xp+x)+a2∑x∈Fpk-2χk-2(xp+x)+⋯+ak-2∑x∈Fp2χ2(xp+x).
From this above equation and (2.19), we can inductively show
(2.21)∑x∈Fprχr(xp+x)=(-1)r/2-1pr/2(p-1).Theorem 2.4.
Supposep is an odd prime number and  a(≠0,±1)∈𝔽p. Let  m be the order of  a in the multiplicative group  𝔽p*. Then, the characteristic polynomial of the curve  v2=up+au+b over  𝔽p is
(2.22)P(t)={(tm+(-1p)(-p)m/2)(p-1)/mifmiseven,(t2m+pm)(p-1)/2mifmisodd.Proof.
Sincev2=up+au+b is isomorphic to v2=up+au, we only have to consider the curve v2=up+au over 𝔽p.
Letp-1=ml, then amk=1 for k=1,2,…,l. For any even positive integer r not divided by m, since ar≠1, the mapping x↦xp+ax is a one-to-one mapping in 𝔽pr, hence, we have
(2.23)∑x∈Fprχr(xp+ax)=∑x∈Fprχr(x)=0.
It follows that ar=0 based on (1.7) and Lemma 2.2. Thus, for all positive integer r satisfying r∤m, the coefficients ar of v2=up+au's characteristic polynomial are equal to 0.
Letθ be a generator of the cyclic multiplicative group 𝔽pm*, then there exists an integer k(1<k<(pm-1)/2) such that (pm-1)/m∣k and a=θk, and it follows that there exists an integer r satisfying 1≤r≤m-1, (r,m)=1 and
(2.24)(θr(∑i=0m-1pi/m))p-1=a.
Let c=θr(∑i=0m-1pi/m); then cp-1=a and
(2.25)χm(cp)=(cp)(pm-1)/2=(cp-1)(pm-1+pm-2+⋯+p+1)/2=a(pm-1+pm-2+⋯+p+1)/2.
From p-1=ml or p=ml+1, we know that there exist integers sk such that
(2.26)pk=m2l2sk+kml+1,
and it follow that there exists an integer s such that
(2.27)∑k=0m-1pk=m2l2s+m(m-1)2⋅ml+m.
If m is even, then we have
(2.28)(pm-1+pm-2+⋯+p+1)2≡m2(m-1)l4+m2mod⁡m.
Hence,(2.29)χm(cp)=a∑k=0m-1pk/2=(am/2)(m-1)ml/2+1=(-1)(m-1)ml/2+1=(-1)ml/2+1=(-1)(p+1)/2.
Thus, from (2.21), we have
(2.30)∑x∈Fpmχm(xp+ax)=∑x∈Fpmχm(cp((xc)p+acp-1⋅xc))=χm(cp)∑x∈Fpmχm((xc)p+xc)=χm(cp)∑x∈Fpmχm(xp+x)=(-1)(p+m-1)/2pm/2(p-1).
In addition, for any positive integerk, we have
(2.31)χmk(cp)=(cp)(pmk-1)/2=(-1)(p+1)k/2.
And so for k≤(p-1)/m, based on (2.21), we have
(2.32)∑x∈Fpmkχmk(xp+ax)=∑x∈Fpmkχmk(cp((xc)p+acp-1⋅xc))=χmk(cp)∑x∈Fpmkχmk((xc)p+xc)=χmk(cp)∑x∈Fpmkχmk(xp+x)=(-1)(p+1+m)k/(2-1)pmk/2(p-1).
Therefore, fork=1,…,⌊(p-1)/2m⌋, we have the coefficients amk of the corresponding characteristic polynomial P(t) as follows:
(2.33)amk=(-1p)k((p-1)/mk)(-p)mk/2.
Hence, the characteristic polynomial for even m is
(2.34)P(t)=(tm+(-1p)(-p)m/2)(p-1)/m.
Especially, if a is a primitive element modulo p, we have
(2.35)P(t)=tp-1+p(p-1)/2.
Supposem is odd. Then 2m∣(p-1) and 2m is the smallest even positive integer satisfying a2m=1. According to the equalities (2.25) and (2.27), we have
(2.36)χ2m(cp)=(cp)(p2m-1)/2=(cp-1)p∑i=02m-1pi/2=(am)∑i=02m-1pi/2m=1,
where c=θr1(∑i=02m-1pi/2m) for some integer r1. And it follows that χ2mk(cp)=1 holds for any positive integer k.
Since for any odd integerk, we have amk=0. Hence, similar to the proof of the formula (2.21), for any positive integer k(1≤k≤⌊(p-1)/4m⌋), we have
(2.37)∑x∈Fp2mkχ2mk(xp+ax)=(-1)k-1pmk(p-1).
Hence, the corresponding characteristic polynomial coefficient a2mk for 1≤k≤⌊(p-1)/4m⌋ equals to
(2.38)((p-1)/2mk)pmk.
Thus, the corresponding characteristic polynomial is
(2.39)P(t)=∑k=0(p-1)/2m((p-1)/2mk)(pm)kt(p-1)-2mk=(t2m+pm)(p-1)/2m.For example, letp=13, then a=5 is not a primitive root of modulo p=13. In fact, we have 54≡1mod13, and the characteristic polynomial of the curve v2=u13+5u over 𝔽13 is (t4+169)3.Case 4.
Now we consider the curvesv2=up+au+b over 𝔽p2.Theorem 2.5.
Supposep is an odd prime number.   (1)
The curvev2=up-u over 𝔽p2 has the characteristic polynomial
(2.40)(t-p̃)p-1.(2)
For any nonzero elementb∈𝔽p2, the all roots of the equation
(2.41)xp-x+b-2-1(b+bp)=0
are in 𝔽p2. Therefore, for every nonzero element b∈𝔽p2, the hyperelliptic curve v2=up-u+b over 𝔽p2 has the characteristic polynomial
(2.42)∏ζp=1,ζ≠1(t-ζp̃).Proof.
(1) Ifxp-x≠0 for x∈𝔽p2, then we have
(2.43)(xp-x)(p2-1)/2=((xp-x)p(xp-x)-1)(p+1)/2=(-1)(p+1)/2=-(-1p).
Hence,
(2.44)∑x∈Fp2χ2(xp-x)=(p2-p)(-(-1p)).
It follows that if αi(i=1,…,p-1) are the all roots of the characteristic polynomial of v2=up-u over 𝔽p2, then
(2.45)∑i=1p-1αi=(p2-p)(-1p)=(p-1)((-1p)p),
and so we have
(2.46)∑i=1(p-1)/2(αi+αi¯-2(-1p)p)=0,αiαi¯=p2.
It follows αi=(-1/p)p=p̃ for i=1,2,…,(p-1)/2. Hence, the characteristic polynomial of the curve v2=up-u over 𝔽p2 is
(2.47)(t-p̃)p-1.
(2) Letβ be a root of xp-x+b-2-1(b+bp)=0, then βp=β-b+2-1(b+bp), and it follows βp2=β, which means β∈𝔽p2.
For any elementb(≠0) in 𝔽p2, let s be a root of the equation x2=2(b+bp)-1 in 𝔽p2 and t a root of xp-x+b-2-1(b+bp)=0. Then s,t∈𝔽p2, and so the curve v2=up-u+b is isomorphic to v2=up-u+1. Hence, for any nonzero element b∈𝔽p2, all the curve v2=up-u+b has the characteristic polynomial
(2.48)∏ζp=1,ζ≠1(t-ζp̃).For example, letν be a root of u2+u+2=0mod5, then the curve C-1,ν: v2=u5-u+ν over 𝔽52 has the characteristic polynomial (2.49)P(t)=∏ζp=1,ζ≠1(t-ζ(-15)5)=t4+5t3+25t2+125t+625.
Since ν is a quadratic nonresidue in 𝔽52, the curve C′-1,ν: (2.50)v2=u5-ν4u+ν6orv2=u5-(2+3ν)u+2
is one twisted curve of C-1,ν. Hence, C′-1,ν's characteristic polynomial is (2.51)P′(t)=t4-5t3+25t2-125t+625.Supposeξ is a root of x2+x+3=0mod7. Then the curve C-1,ξ: v2=u7-u+ξ over 𝔽72 has the characteristic polynomial (2.52)P(t)=t6-7t5+49t4-343t3+2401t2-16807t+117649.
Since ξ is a quadratic nonresidue in 𝔽72, the curve C′-1,ξ: (2.53)v2=u7-(4+5ξ)u+3overF72
is one twisted curve of C-1,ξ. C′-1,ξ has the characteristic polynomial (2.54)P′(t)=t6+7t5+49t4+343t3+2401t2+16807t+117649.Theorem 2.6.
Supposep is an odd prime number. Then, (1)
the equation(2.55)xp+x+b=0
has roots in 𝔽p2 if and only if b∈𝔽p.
For anyb∈𝔽p2, the curve v2=up+u+b=0 is isomorphic to the curve v2=up+u over 𝔽p2 if and only if b∈𝔽p.
(2) For anyb,c∈𝔽p2∖𝔽p, the curve v2=up+u+b is isomorphic to the curve v2=up+u+c over 𝔽p2.Proof.
(1) Supposeb∈𝔽p and x0∈𝔽p2p is a root of up+u+b=0. Then, x0p=-x0-b and it follows x0p2=x0, which implies x0∈𝔽p2. On the other hand, if x0 is a root of up+u+b=0 in 𝔽p2, then b-bp=0, which implies b∈𝔽p.
Letx0 be a root of v2=up+u+b=0 in 𝔽p2p, then x0∈𝔽p2, and over 𝔽p2, the curve v2=up+u+b is isomorphic to the curve v2=up+u+(x0p+x0+b), that is, v2=up+u.
(2)  Supposeb and c are two different elements in 𝔽p2∖𝔽p. Then, obviously, (c-cp)(b-bp)-1∈𝔽p. Let s be a square root of (c-cp)(b-bp)-1 in 𝔽p2, and let b̃=b-cs-2. Then, b̃=(cbp-bcp)(c-cp)-1∈𝔽p.
According to (1), the equationxp+x+b̃=0 has roots in 𝔽p2. Let t∈𝔽p2 be a root of xp+x+b̃=0; then, over 𝔽p2, the curve v2=up+u+b is isomorphic to the curve
(2.56)v2=up+s2(p-1)u+s2p(tp+t+b).
That is, v2=up+u+b is isomorphic to v2=up+u+c over 𝔽p2 since we have
(2.57)s2(p-1)=1,s2p(tp+t+b)=s2(-b̃+b)=s2(cs-2)=c.For anyb∈𝔽p2∖𝔽p, the curve v2=up+u+b has the same characteristic polynomial.Theorem 2.7.
Supposep is an odd prime number and  b∈𝔽p2∖𝔽p. If  p≡1mod4, then for every  b∈𝔽p2∖𝔽p, the curve  v2=up+u+b is a twisted curve of some curve of the form  v2=up-u+b′ with  b′∈𝔽p2. If  p≡-1mod4, then for every  b∈𝔽p2∖𝔽p, the curve  v2=up+u+b is isomorphic to the curve  v2=up-u+1 over  𝔽p2.
Hence, over𝔽p2, the characteristic polynomial of the curve v2=up+u+b with b∈𝔽p2∖𝔽p is
(2.58)∏ζp=1,ζ≠1(t+ζp).Proof.
Letθ be a generator of the cyclic multiplicative group 𝔽p2*.
(1) Assumep≡1mod4. Set γ=θ(p+1)/2; then
(2.59)γp-1=(θ(p+1)/2)p-1=-1,γp=-γ,χ(γ)=(θ(p2-1)/2)(p+1)/2=(-1)(p+1)/2=-1.
It follows that γ is a quadratic nonresidue in 𝔽p2, and the curve v2=up+u+b is a twist of the curve v2=up-u-θ(2p-3)(p+1)/2b. Hence, due to Theorems 2.1 and 2.5, the curve v2=up+u+b has the characteristic polynomial
(2.60)∏ζp=1,ζ≠1(-t-ζp̃)or∏ζp=1,ζ≠1(t+ζp̃).
(2) Assumep≡-1mod4. Let s=θ(p-2)(p+1)/4, t=0, and b=θ(p+1)/2. Then, s,b∈𝔽p2∖𝔽p, and the curve v2=up+u+b is isomorphic to the curve
(2.61)v2=up+s2(p-1)u+s2pb.
It follows that v2=up+u+b is isomorphic to the curve v2=up-u+1 since s2(p-1)=-1 and s2pb=θ-(p+1)/2b=1. Therefore, for every b∈𝔽p2∖𝔽p, the curve v2=up+u+b has the same characteristic polynomial as the curve v2=up-u+1 over 𝔽p2, that is,
(2.62)∏ζp=1,ζ≠1(t-ζp̃).
In a word, for any odd prime number, the characteristic polynomial of the curve v2=up+u+b is
(2.63)∏ζp=1,ζ≠1(t+(-1p)ζp̃)or∏ζp=1,ζ≠1(t+ζp).Theorem 2.8.
Supposep is an odd prime number,  a,b∈𝔽p2, and  a≠0,±1. Let  m be the order of  a in  𝔽p* if  a∈𝔽p, that is,  m=ord𝔽p*(a). And let  m=ord𝔽p2*(a) and  e(>1) be the smallest positive integer such that  m∣e(p+1) if  a∈𝔽p2∖𝔽p. (1)
Supposeap+1=1. Then a∈𝔽p2∖𝔽p, and the characteristic polynomial is
(2.64)P(t)={(t+a(p+1)/2p)p-1ifb≠0,a=b1-p,orb=0,∏ζp=1,ζ≠1(t+ζp)ifa≠b1-p.(2)
Supposeap+1≠1; then the characteristic polynomial of the curve v2=up+au+b over 𝔽p2 is
(2.65)P(t)={(t(p-1)/2+p(p-1)/2)2ifa∈Fp,m=p-1,(tm/2+(-1p)(-p)m/2)2(p-1)/mifa∈Fp,m<p-1,miseven,(tm+pm)(p-1)/mifa∈Fp,m<p-1,misodd,(te+(-1)e(p+1)/m+e-1pe)(p-1)/eifa∈Fp2∖Fp.Proof.
(1)  Ifap+1=1, then a∉𝔽p since a2≠1. Let θ be a generator of the cyclic multiplicative group 𝔽p2. Then, there exists an integer e satisfying 1≤e≤p, e≠(p+1)/2, and a=θe(p-1).
Ifa(p+1)/2=-1, then e is odd. Let γ=θp+1-e, then
(2.66)γ(p2-1)/2=θ(p+1-e)(p2-1)/2=θ-e(p2-1)/2=(θ(p2-1)/2)-e=(-1)e=-1;
it means that γ is a quadratic nonresidue in 𝔽p2. Hence, the curve v2=up+au+b has a twisted curve defined by the equation
(2.67)v2=up+γp-1au+γpb,thatis,v2=up+u+θp+1-epb.
If θp+1-epb∈𝔽p, then b=0, or b≠0 and (θp+1-epb)p-1=1 which means a=b1-p. Hence, the curve v2=up+u+θp+1-epb is isomorphic to the curve v2=up+u. Thus, over 𝔽p2, the curve v2=up+au+b has the characteristic polynomial (-t+p)p-1, that is, (t-p)p-1.
Ifθp+1-epb∉𝔽p, that is, b≠0 and a≠b1-p, then according to Theorem 2.7, v2=up+u+θp+1-epb has the characteristic polynomial ∏ζp=1,ζ≠1(t+ζp).
Ifa(p+1)/2=1, then e is even. Let s=θe/2 and t=0, then the curve v2=up+au+b, that is,
(2.68)v2=up+s2(p-1)u+s2p(tp+t+b1)
is an isomorphic curve of the curve
(2.69)v2=up+u+b1withb1=s-2pb=θ-epb.
It is clear thatb1=θ-epb∈𝔽p if and only if a=b1-p. Hence, based on Theorems 2.6 and 2.7, the curve v2=up+au+b has the characteristic polynomial
(2.70)(t+p)p-1fora=b1-por∏ζp=1,ζ≠1(t+ζp)fora≠b1-p.
Forb=0, we can also show our result as follows.
Setαk=θe+(p+1)(2k+1)/2 with 0≤k≤p-2. Then, αk are the p-1 different nonzero roots of xp+ax=0 in 𝔽p2. Hence, if x is a nonzero root of xp+ax=0 in 𝔽p2, we have
(2.71)χ1*(xp+ax)=(xp+ax)(p2-1)/2=((xp+ax)p(xp+ax)-1)(p+1)/2=(ap(ax+xp)(xp+ax)-1)(p+1)/2=(a(p+1)/2)p=a(p+1)/2.
Thus, according to (1.4) and (1.10), each root of the corresponding characteristic polynomial equals to -a(p+1)/2p. It follows that the corresponding characteristic polynomial is
(2.72)P(t)=(t+a(p+1)/2p)p-1.
(2)  Ifap+1≠1, then (1-ap+1)-1(apb-bp) is a root of up+au+b=0. Set s=1 and t=(1-ap+1)-1(apb-bp), then, over the field 𝔽p2, v2=up+au+b is isomorphic to v2=up+s2(p-1)au+s2p(tp+at+b), that is, v2=up+au. Hence, we only have to compute the characteristic polynomial of the curve v2=up+au over 𝔽p2.
(i) Ifa∈𝔽p, then ap+1≠1 means a≠±1. Suppose a is a primitive root of p; then the equation xp+ax=0 has only zero root in 𝔽p2r for any positive integer r:1≤1≤(p-3)/2, and it follows that the r-th coefficient ar of the characteristic polynomial of v2=up+au is 0.
Now we compute the(p-1)/2-th coefficient a(p-1)/2. Let θ be a generator of the cyclic multiplicative group 𝔽(p2)(p-1)/2*; then there exists an integer r satisfying 1≤r≤p-2, (r,p-1)=1, and (θr(∑i=0p-2pi/p-1))p-1=a.
Setc=θr(∑i=0p-2pi/(p-1)); then c∈𝔽pp-1*, cp-1=a, and χ(p-1)/2*(cp)=χp-1(cp)=(-1)(p+1)/2. Hence, based on Lemma 2.3, we have
(2.73)∑x∈F(p2)(p-1)/2χ(p-1)/2*(xp+ax)=∑x∈F(p2)(p-1)/2χ(p-1)/2*(cp((xc)p+acp-1⋅xc))=χp-1(cp)∑x∈Fpp-1χp-1(xp+x)=(-1)(p+1)/2(-1)p(p-1)/2(p-1)=p(p-1)/2(p-1),
where χk* denotes the extended quadratic character of the degree k extension of 𝔽p2(i.e., 𝔽p2k), which is equivalent to χ2k, the extended quadratic character of the degree 2k extension of 𝔽p. Thus,
(2.74)a(p-1)/2=1(p-1)/2⋅p(p-1)/2(p-1)=2p(p-1)/2.
Therefore, the corresponding characteristic polynomial is
(2.75)P(t)=tp-1+2p(p-1)/2t(p-1)/2+(p2)(p-1)/2=(t(p-1)/2+p(p-1)/2)2.
(ii) Supposea∈𝔽p and m<p-1; then similar to the proof of Theorem 2.4, we have the corresponding characteristic polynomial coefficients as the the following if m is even:
(2.76)amk/2=(-1)(p-1)k/2(-p)mk/2(2(p-1)/mk)
for 1≤k≤(p-1)/m, while the other coefficients are equal to zero. Hence, the corresponding characteristic polynomial is
(2.77)(tm/2+(-1p)(-p)m/2)2(p-1)/m.
By the same way, we can show that ifm is odd, the corresponding characteristic polynomial is (tm+pm)(p-1)/m.
(iii) Supposea∈𝔽p2∖𝔽p, then m∤(p+1). If an integer k satisfies 1≤k≤(p-1)/2 and m∤k(p+1), then the corresponding characteristic polynomial is tp-1+pp-1.
Now supposee is the smallest integer such that 2≤e≤(p-1)/2 and m∣e(p+1). Then e∣(p-1). Otherwise, let p-1=de+e1 with d being an integer and 1≤e1<e. Then, (p+1)(p-1)=de(p+1)+e1(p+1), and it follows m∣e1(p+1), which contradicts e being the smallest integer satisfying m∣e(p+1). Set p-1=el, e(p+1)=mt. Clearly, (e,t)=1.
For any positive integerk satisfying e∤k, since xp+ax=0 has no nonzero root in 𝔽p2k, we have
(2.78)∑x∈F(p2)kχk*(xp+ax)=∑x∈Fp2kχk*(x)=∑x∈Fp2kχ2k(x)=0,
which implies the corresponding characteristic polynomial coefficient ak=0.
Hence, we only have to compute the characteristic polynomial coefficientsaer for r=1,…,⌊l/2⌋.
Letθ be a generator of the cyclic multiplicative group 𝔽(p2)e* or 𝔽p2e*. Then there exists an integer k(1≤k≤p2-2) such that a=θk∑i=0e-1p2i. Since ae(p+1)=1, we have
(2.79)1=(θk∑i=0e-1p2i)e(p+1)=θke(p+1)∑i=0e-1p2i=θ(k/l)(p-1)(p+1)∑i=0e-1p2i=θ(k/l)(p2e-1),
and it follows that k/l must be a positive integer. Set k=lk′, where k′ is some positive integer satisfying (e,k′)=1 due to the smallest of e.
Fromp-1=el or p=el+1, we can deduce that there exists a positive integer n such that
(2.80)∑i=0e-1p2i=e2l2n+e2(e-1)l+e.
Hence, we have
(2.81)a=θlk′(e2l2n+e2(e-1)l+e)=θ(el)k′(el2n+e(e-1)l+1)=θ(p-1)k′(el2n+e(e-1)l+1).
Let δ=θk′(el2n+e(e-1)l+1); then a=δp-1, and for every integer r:2≤r≤⌊l/2⌋, we have
(2.82)χre*(δp)=χ2re(δp)=(δp)(p2re-1)/2=(δp)((p2e-1)/2)∑i=0r-1p2ei=((δp)(p2e-1)/2)∑i=0r-1p2ei=((-1)e(p+1)/m)∑i=0r-1p2ei=(-1)re(p+1)/m.
And according to (2.21), we obtain
(2.83)∑x∈F(p2)reχre*(xp+ax)=∑x∈Fp2reχ2re(xp+ax)=∑x∈Fp2reχ2re(δp)((xδ)p+aδp-1⋅xδ)=χ2re(δp)∑x∈Fp2reχ2re(xp+x)=(-1)r(e(p+1)/m+e)-1pre(p-1).
Therefore, the corresponding characteristic polynomial coefficient are can be computed as follows:
(2.84)are=1re∑i=0r-1∑x∈F(p2)(r-i)eχ(r-i)e*(xp+ax)aie=1re∑i=0r-1(-1)(r-i)(e(p+1)/m+e)-1p(r-i)e(p-1)aie=((-1)e(p+1)/m+e-1pe)r((p-1)/er),
and it follows that the corresponding characteristic polynomial is
(2.85)P(t)=(te+(-1)e(p+1)/m+e-1pe)(p-1)/e.


## 3. Some Hyperelliptic CurvesCq Suitable for Cryptographic Applications

Due to the Pollard's rho algorithm, Index-calculus algorithm or their modified versions [11–14], the order of the Jacobian group should have a large prime factor or an almost large prime factor (i.e., the order should be a large prime times a small integer, and the hyperelliptic curves of genus greater than 3 may not be secure for cryptographic applications). Otherwise, the discrete logarithm problems on the Jacobian group may probably be solved in a subexponential time complexity or even in a polynomial time complexity. Hence, the characteristic polynomial of Cq should be irreducible over the rational number field, and the field characteristic p should be no larger than 7 when the curve Cq is considered for cryptographic uses. The following Table 2 lists some values of (n,a,b) with which Cq have reducible characteristic polynomials in rational number field and so they are not secure for cryptographic applications.According to the Theorem 1 in [15], the curve v2=up+u+b over 𝔽p is supersingular and thus the parameters (the characteristic p and the extension degree of 𝔽p) have to be chosen carefully to defend against an MOV-type attack where the group is embedded in the multiplicative group of a finite field. Furthermore, the curves have a large automorphism group [16], and the size of the Jacobian should be large enough to defend against a parallelized Pollard rho-type attack.If the characteristic polynomialP(t) of a hyperelliptic curve Cq over 𝔽q is determined, then for any positive integer m, the Jacobian group order #𝕁C(𝔽qm) can be computed as (1.8).But if finding the roots ofP(t) is of some high computational complexity, then one can obtain the Jacobian group order by computing the determinant of the (2g×2g)-matrix Am-I, where A is the companion matrix of P(t), that is, (3.1)A=(010⋯0001⋯0⋯⋯000⋯1-qgqg-1a1qg-2a2⋯a1).For a positive integerm, by taking tm-1 modulo P(t) in the polynomial ring ℤ[t] and setting ξ(t)=tm-1modP(t), then we get that ξ(t) is a monic polynomial of degree no larger than 2g-1 and (3.2)#JC(Fqm)=∏i=12g(1-τim)=∏i=12gξ(τi),
which may be another more efficient method for the computation of the Jacobian group order if the field extension degree m is very large. For Cq with q=p, a=-1, and b(≠0)∈𝔽p, Duursma and Sakurai gave a table about the bit-sizes of the large prime factors of the orders of the Jacobian groups #𝕁Cq(𝔽qm) for some parameters (p,m) in [6]. In Table 3, we list some parameters (q,a,b,m) with which the Jacobian group orders #𝕁Cq(𝔽qm) have large prime factors, together with the corresponding characteristic polynomials, the largest prime factors, and their bit sizes. Where “Bits" in Table 3 denotes the bit-sizes of the largest prime factors of the corresponding Jacobian group orders, ν is a root of u2+u+2=0mod5 and ξ is a root of x2+x+3=0mod7.Table 3
Some parameters forCq whose Jacobian group orders have large prime factors.
qmabP(t)The largest prime factors of#𝕁Cq(𝔽qm)Bits523546571335200077066054710975060110329133440267382831314954763421645531287560113037510241095096183757930733363918820917976121139432,3b∈𝔽5t4+2513233155474316354191628436487846050493311864914759115740982234809846938460212895728805200607070205251∖694425477091079721084007850060127067867036788162169620124638326439573933801961942760108098070∖137001674880648146509971591712929383803692714308830143367297266327762922660863388853347980739∖393305286488942808508821182176421386864643895241973136252231b∉𝔽p, b∉𝔽52t4-5t3+25t2-125t+62552995840190087188953270566801358938715238435286688832414118937654418058067838415738219243693599843014730577527147788290∖112235894097137712335917972446864776131241302432661799107117404163951962923697369817504003965405048∖4305241622066418383435029921996634876705928703134443186303988308322090874478781582395496784216892901472776234∖265934523703793689640932250840283571890263537379757908396138053291610525781490940421443140715914231197410552825810130042∖681253630419471155500509947792484684708874327987628732648∖4890398278925389108639532224688148435ν1t4+625751114601164400963558298106851275193494354988352771579238∖81898164755096450781289000127953992546266896549276402616168146585251329055676315885009163∖311765166575856031713035384955676431972387484913025322167∖25848240632224583606232145967336811435885959208445641343491054920374120171960655193293∖219265977895989598373705302211662541119647190380393508253∖771113342078436606690357719421008432512113722632406302690∖5654908750003900016137173,5b∈𝔽5t6+240163899174854308211303745600942029347776643823314925101087819444250339960209489699235199115942108498312937463∖65778360121631103602441708018848525107155829768304755490441636535691297∖466019095049513724037494238893933995748902489762221251946925169471844835131661∖333855087397989688385273799604896250931261182588286429822∖182832014057237−1ξt6-7t5+49t4-343t3+2401t2-16807t+117649917978970173748828722717246665778119436009819029423573386∖999458698539060819171142807825459514676666724494347570300∖567475059845500333611945223150557819388250184737538915006485086145065087672198550975∖23919363757100260013725747296622615055064026410595294739016073226621769583063595146∖246922263428126791770055382936328803135692863434055321280∖473083651131176444146403955371064616929027577273326083639∖513054667512206604717132883032684181757524995846173061-4-5ξ3t6-7t5+49t4-343t3+2401t2-16807t+1176498895270249059563599185595938219020670590896314104535959964∖8016164505006377256389546604468613493539182920809346771675∖9773506416632242948638670510523462330304278108981369417392∖1982072102810157541240855736144227613689662410423301535608∖9640174996978462560103065338025939666322591200406677474989964716059483980039244877047243971289932877368693248030007997563∖4051109664747243238974088293635840393750782605275018285648∖0050394746490410269339276185366728255286611777338282539843∖0750963323653238944701113108662166958149626807014450213296∖6079886234998846359954447034509585472485237180044828118247∖9810721772951291013For the listed parameters(q,a,b,m) in Table 3, the corresponding Jacobian group orders are almost large primes, and so these hyperelliptic curves Cq are suitable for secure hyperelliptic curve cryptographic applications.


## 4. Conclusion

The computation of hyperelliptic curve Jacobian group orders is an essential step during constructing HECC. At the present, the most common method used for the computation of Jacobian group orders is by computing the zeta functions or the characteristic polynomials of the related hyperelliptic curves. Hence, computing the characteristic polynomials of hyperelliptic curves is a very useful work, and it is often a challenging work.In this paper, we determine the characteristic polynomials ofCq over the finite field 𝔽pn for n=1,2 and a,b∈𝔽pn. By using the characteristic polynomials one can easily compute out the Jacobian group orders. And we also describe some parameters with which the Jacobian group orders of Cq have large prime factors.The hyperelliptic curves of genus larger than 3 are not secure for cryptographic applications since the corresponding hyperelliptic curve discrete logarithm problems can be solved by the Index-calculus algorithm or its modified versions in some subexponential time. Hence, we should be careful when the curveCq with p>11 is used for practical cryptosystems. If the implementation speed is the first consideration in the construction of HECC, while the security is not in high demand, then one may choose the curve Cq with some high genus or with the Jacobian group order not having so much large prime factor. Besides, some special hyperelliptic curves having fast arithmetic over finite fields can be found efficient applications in pairing-based cryptosystems or identity-based cryptosystems ([15, 17]).Since the (divisor) scalar multiplication computation is the most extremely time-consuming operation, we will employ the characteristic polynomials ofCq obtained here to develop some efficient scalar multiplication algorithms on Cq in our future work.



---

*Source: 437541-2011-05-22.xml*