OMPUTING THE NUMBER OF POINTS ON GENUS 3 HYPERELLIPTIC CURVES OF TYPE Y2 = X7 + aX OVER FINITE PRIME FIELDS†

Journal of Applied Mathematics & Informatics.
2014.
Jan,
32(1_2):
17-26

- Received : June 14, 2013
- Accepted : August 26, 2013
- Published : January 28, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

In this paper, we present an algorithm for computing the number of points on the Jacobian varieties of genus 3 hyperelliptic curves of type
y
^{2}
=
x
^{7}
+
ax
over finite prime fields. The problem of determining the group order of the Jacobian varieties of algebraic curves defined over finite fields is important not only arithmetic geometry but also curve-based cryptosystems in order to find a secure curve. Based on this, we provide the explicit formula of the characteristic polynomial of the Frobenius endomorphism of the Jacobian variety of hyperelliptic curve
y
^{2}
=
x
^{7}
+
ax
over a finite field
with
p
≡ 1 modulo 12. Moreover, we also introduce some implementation results by using our algorithm.
AMS Mathematics Subject Classification : 14H45. 14G50. 94A60.
y
^{2}
=
x
^{5}
+
ax
over finite prime fields. Also, there are many efficient algorithms for algebraic varieties over finite fields of small characteristic, which is so called
p
-adic method
[16
,
17
,
18]
. Our approach follows
l
-adic method which is more useful for algebraic curve over large field characteristic.
In this paper, we provide an algorithm for computing the orders of the Jacobians on genus 3 hyperelliptic curves of type
y
^{2}
=
x
^{7}
+
ax
over finite prime fields. In particular, by using baby-step giant-step algorithm, we determine the order of the Jacobian of a curve defined over finite prime field with characteristic greater than the 54-bit. We also provide the explicit formula of the characteristic polynomial of the Frobenius endomorphism of the Jacobian of the hyperelliptic curves
y
^{2}
=
x
^{7}
+
ax
over
with
p
≡ 1 modulo 12. Furthermore, we present additional computational results using our algorithm.
be a finite field of
q
=
p^{n}
elements, where
p
is an odd prime. The hyperelliptic curve
C
of genus
g
over
is given by
where
f
(
x
) is a polynomial in
[
x
] of degree 2
g
+ 1 without singular points. We denote the Jacobian variety of a hyperelliptic curve
C
by
J_{C}
. Then,
J_{C}
(
) is the group of
-rational points on
J_{C}
. A semi-reduced divisor is a divisor with
k
points and no two points in the opposite side. A reduced divisor is a semi-reduced divisor of
k
≤
g
.
In
[11]
, every semi-reduced divisor on
J_{C}
(
) can be uniquely represented by a pair of polynomials ⟨
u
(
x
),
v
(
x
)⟩, where
u
(
x
) = Π
_{i}
(
x
−
x_{i}
) is monic and
v
(
x
) is unique polynomial such that deg
v
(
x
) < deg
u
(
x
),
v
(
x_{P}
) =
y_{P}
for all
P
= (
x_{P}
,
y_{P}
) ∈
C
(
) and
u
(
x
) divides
f
(
x
) −
v
(
x
)
^{2}
. ⟨1, 0⟩ is the identity element of the addition law. Cantor’s algorithm can be used to compute the sum of two reduced divisors in
J_{C}
(
) .
We consider the hyperelliptic curves of genus 3 defined over finite fields
. The characteristic polynomial χ
_{q}
(
t
) of the
q
-th power Frobenius endomorphism of
J_{C}
is given as follows:
where
s_{i}
∈ ℤ. We also know that ♯
J_{C}
(
) = χ
_{q}
(1). i.e.,
Let
M_{r}
= (
q^{r}
+1)−
N_{r}
, where
N_{r}
is the number of
points on
C
for
r
= 1, 2, 3. Then, we have
The following is a well-known inequality, the Hasse-Weil bound, that bounds ♯
J_{C}
(
):
Then, we have
S. Haloui
[19]
presented the efficient bounds of the coefficients of characteristic polynomial of genus 3 abelian varieties over finite fields.
Theorem 2.1
(
[19]
).
Let
χ(
t
) =
t
^{6}
−
s
_{1}
t
^{5}
+
s
_{2}
t
^{4}
−
s
_{3}
t
^{3}
+
qs
_{2}
t
^{2}
−
q
^{2}
s
_{1}
t
+
q
^{3}
be a polynomial with integer coefficients
.
Then
χ(
t
)
is a Weil polynomial if and only if the following conditions hold
p
of ♯
J_{C}
). Yui’s made the following theorem
[6]
.
Theorem 3.1.
Let y
^{2}
=
f
(
x
)
with
deg
f
= 2
g
+1
be the equation of a genus g hyperelliptic curve
.
Denote by c_{i} the coefficient of x^{i} in the polynomial f
(
x
)
^{(p−1)/2}
.
Then the Hasse-Witt matrix is given by
In
[8]
, Manin showed that this matrix is related to the characteristic polynomial of the Frobenius endomorphism modulo
p
. For a matrix
H
= (
a_{ij}
), let
H
^{(p)}
denote the elements raised to the power
p
, i.e.,
Then, we have the following theorem.
Theorem 3.2.
Let C be a curve of genus g defined over a finite field
Let H be the Hasse-Witt matrix of C and let
Let κ
(
t
)
be the characteristic polynomial of the matrix H_{π} and
χ(
t
)
the characteristic polynomial of the Frobenius endomorphism of the Jacobian of C
.
Then
,
C
:
y
^{2}
=
x
^{7}
+
ax
over finite fields
with
p
≡ 1 (mod 12), and show how to efficiently compute the Hasse-Witt matrix of
C
. The below theorem is a tool used to compute the Hasse-Witt matrix of
C
.
Corollary 4.1
(
[3]
).
If p
= 12
f
+ 1 =
A
^{2}
+
B
^{2}
(A
≡ 1
(mod 4)
,
B
≡ 0
(mod 2))
is prime then
Proof
. See Corollary 4.2.2 in
[3]
.
Theorem 4.2
(
[3]
).
Let p
= 12
f
+ 1 =
A
^{2}
+
B
^{2}
=
x
^{2}
+ 3
y
^{2}
be a prime with A
≡ 1
(mod 4)
,
x
≡ 1
(mod 3)
.
Then we have the following congruences modulo p
:
where
Proof
. See Theorem 15.1 in
[3]
.
Theorem 4.3.
Let C be a hyperelliptic curve defined by the equation y
^{2}
=
x
^{7}
+
ax over
with p
≡ 1
(mod 12) such that p
=
A
^{2}
+
B
^{2}
(
A
≡ 1
(mod 4), B
≡ 0
(mod 2)) and
χ(
t
)
the characteristic polynomial of the p-th power Frobenius endomorphism of C. Then s
_{1}
,
s
_{2}
and s
_{3}
in
χ(
_{t}
)
are given as follows
:
Proof
. First, we compute the entities
c_{ip−j}
of the Hasse-Witt matrix
H
of the curve
C
. From Theorem 3.1, the entities
c_{ip−j}
are computed by an integer
k
, 0 ≤
k
≤ (
p
− 1)/2, for
ip − j
=
p
− 1 + 3
k
from
Since the characteristic
p
with
p
≡ 1 (mod 12), the Hasse-Witt matrix is
Then we have that
On the other hand, the each
s_{i}
of χ(
t
) has the following congruence modulo
p
;
Let
p
= 12
f
+ 1 be a prime. Then, since (
p
− 1)/2 + 6
k
=
p
− 1 for
c_{p}
_{−1}
, we have
k
= (
p
− 1)/12 =
f
and
For
c_{2p}
_{−2}
, since (
p
− 1)/2 + 6
k
= 2
p
− 2, we have
k
= (3
p
− 3)/12 = 3
f
and
For
c_{3p}
_{−3}
, since (
p
− 1)/2 + 6
k
= 3
p
− 3, we have
k
= (5
p
− 5)/12 = 5
f
and
Hence, since
Theorem 4.2 and Corollary 4.1, we have the congruence values modulo
p
for
s
_{1}
,
s
_{2}
and
s
_{3}
.
The equation of given curve gives us to some information about 2
^{k}
-torsion subgroups of the Jacobian variety.
Lemma 4.4.
Let p be a prime number such that p
≡ 1
(mod 12) and C
:
y
^{2}
=
f
(
x
)
be a hyperelliptic curve over
where f
(
x
) =
x
^{7}
+
ax. If f
(
x
)
splits completely over
(
i.e.,a
^{(p−1)/6}
= 1),
then 64 divide
♯
J_{C}
(
).
If f
(
x
)
splits into four factors over
(
i.e, a
^{(p−1)/3}
= 1),
then 8 divide
♯
J_{C}
(
).
Otherwise, if f
(
x
)
splits into two factors of degree 3 and a factor of degree 1, or into two factors of degree 6 and 1, then 2 divide
♯
J_{C}
(
).
Proof
. Since 12 divide
p
−1, there are exists a primitive 12-th root of unity,
ζ
_{12}
, in
. The points on
C
with vanishing
y
-coordinates correspond to (1−
ζ
_{12}
)-torsion points of the Jacobian. If
f
(
x
) splits completely over
(i.e.,
a
^{(p−1)/6}
= 1), then
J_{C}
[1 −
ζ
_{12}
] is defined over
. Hence, (ℤ/2ℤ)
^{6}
is a subgroup in
J_{C}
(
) and 64 divide ♯
J_{C}
(
). Moreover precisely, in this case, there exists an element
b
∈
such that
a
=
b
^{6}
. Then we have
If
f
(
x
) splits four factors over
(i.e.,
a
^{(p−1)/3}
= 1), then the three (1−
ζ
_{12}
)-torsion points arising from the roots of
f
(
x
) are linearly independent. Hence (ℤ/2ℤ)
^{3}
≤
J_{C}
(
) and 8 divides ♯
J_{C}
(
). Moreover, in this case, there exists an element
b
∈
such that
a
=
b
^{3}
. Then we have
Otherwise,
J_{C}
(
) contains one non-trivial (1−
ζ
_{12}
)-torsion point. Moreover, in this case, there exists an element
b
∈
such that
a
=
b
^{2}
. Then we have that
Throughout this paper, we consider the case of the prime
p
=
A
^{2}
+
B
^{2}
with
A
≡ 1 (mod 4) and
B
≡ 0 (mod 2).
Theorem 4.5.
Let C be a hyperelliptic curve of the form y
^{2}
=
x
^{7}
+
ax defined over a finite field
with p
≡ 1
(mod 12), p
=
A
^{2}
+
B
^{2}
.
Then the characteristic polynomial
χ(
t
)
is as follows
:
where A
≡ 1, 2
(mod 3) and B
≡ 0
(mod 3)
.
where A
≡ 0
(mod 3) and B
≡ 1, 2
(mod 3)
.
Proof
. For the case (1), from
a
^{(p−1)/12}
= 1 and Theorem 4.3, we have
s
_{1}
≡ 6
A
(mod
p
),
s
_{2}
≡ 12
A
^{2}
(mod
p
), and
s
_{3}
≡ 8
A
^{3}
(mod
p
). By the Definition of
A
,
A
^{2}
<
p
and hence
If
p
> 37, then
s
_{1}
is uniquely determined by Hasse-Witt matrix. Hence we have that
s
_{1}
= 6
A
.
Denote
s
_{2}
=
mp
+12
A
^{2}
for
m
∈ ℤ. Since 0 < 12
A
^{2}
< 12
p
and
m
is satisfied in −9 ≤
m
≤ 3. Now we determine the value
m
. We know that χ(
t
) splits into three factors
h_{i}
(
x
) of degree 2, for
i
= 1, 2, 3. In particular, let
π_{i}
be a complex roots of χ(
t
) in ℤ[
t
] for
i
= 1, 2, 3, and
its complex conjugate. We denote
for
i
= 1, 2, 3. Then we have that
s
_{1}
= λ
_{1}
+λ
_{2}
+λ
_{3}
,
s
_{2}
= 3
p
+λ
_{1}
λ
_{2}
+λ
_{2}
λ
_{3}
+λ
_{3}
λ
_{1}
, and
s
_{3}
= 2
ps
_{1}
+λ
_{1}
λ
_{2}
λ
_{3}
. Since
we thus have
m
= 3.
We denote
Since
we have
m′
= 12
A
. Then the characteristic polynomial χ(
t
) is
For the case (3), we have that
s
_{1}
≡ 2
B
^{2}
/
A
(mod
p
),
s
_{2}
= −4
B
^{4}
/
A
^{2}
(mod
p
), and
s
_{3}
≡ −8
B
^{6}
/
A
^{3}
(mod
p
). Following as the above way, the characteristic polynomial χ(
t
) is
For the case (2),(4), we can derive the χ(
t
) in the same way.
Theorem 4.6.
Let C be a hyperelliptic curve of the form y
^{2}
=
x
^{7}
+
ax defined over a finite field
.
If a
^{(p−1)/6}
= −1
(i.e, a
^{(p−1)/3}
= 1)
and A
≡ 1, 2
(mod 3) and B
≡ 0
(mod 3)
,
then the characteristic polynomial
χ(
t
)
has the form of the following as
where c
_{1}
is
2
Aa
^{(p−1)/12}
or
−
p
+ 2
Aa
^{(p−1)/12}
,
c
_{2}
=
mp
+ 4
A
^{2}
for
−1 ≤
m
≤ 2,
and c
_{3}
is an integer with c
_{3}
≡ 0
(mod 2) for
Proof
. From
a
^{(p−1)/6}
= −1 and Theorem 4.3, we have that
s
_{1}
≡ 2
Aa
^{(p−1)/12}
(mod
p
),
s
_{2}
≡ 4
A
^{2}
(mod
p
) and
s
_{3}
≡ 8
A
^{3}
a
^{9}
^{(p−1)/12}
(mod
p
). Since Hasse-Weil bound of
s
_{1}
and
the coefficient
s
_{1}
only have 2
Aa
^{(p−1)/12}
or −
p
+ 2
Aa
^{(p−1)/12}
.
Let
s
_{2}
=
mp
+ 4
A
^{2}
for m ∈ ℤ. From the sharp bound of
s
_{2}
in Theorem 2.1, −1 ≤
m
≤ 2. For
s
_{3}
=
m′p
+ 8
A
^{3}
a
^{9(p−1)/12}
,
m′
∈ ℤ, we have
s
_{3}
≡ 0 (mod 2) since
s
_{1}
≡ 0 (mod 2) and ♯
J_{C}
(
) ≡ 0 (mod 2).
Theorem 4.7.
Let C be a hyperelliptic curve of the form y
^{2}
=
x
^{7}
+
ax defined over a finite field
with p
≡ 1
(mod 12)
.
Assume that A
≡ 1
(mod 4) and A
≡ 1, 2
(mod 3)
.
If a
^{(p−1)/3}
≠ 1
and f
(
x
)
splits three factors, then the
χ(
t
)
has the following form
where c
_{3}
is an integer for
and c
_{3}
≡ 0
(mod 2)
.
Proof
. In this case, the prime satisfies
p
=
A
^{2}
+
B
^{2}
where
A
≡ 1, 5 (mod 12) and
B
≡ 0 (mod 6). We have
a
^{(p−1)/3}
+
a
^{(p−1)/6}
+ 1 = 0. Then
s
_{1}
≡ 0 (mod
p
) and
N
_{1}
= ♯
C
(
) =
p
+1. Hence
s
_{1}
= 0. Since
we have
s
_{2}
= 0.
For the value
s
_{3}
, we denote
s
_{3}
=
mp
+8
A
^{3}
a
^{9(p−1)/12}
. From the bounds of
s
_{3}
in theorem 2.1, we have
Since ♯
J_{C}
(
) ≡ 0 (mod 2),
Then we have
c
_{3}
≡ 0 (mod 2) for
from Theorem 2.1 . Hence we have conclusion.
5.1. BSGS algorithm.
Now, we show how to determine the order of the Jacobian of a hyperelliptic curve using the BSGS algorithm. We denote by
L_{i}
(
U_{i}
) the lower (upper) bound of
s_{i}
for
i
= 1, 2, 3 in (3). According to Theorem 3.2, we denote that for
i
= 1, 2, 3
with
Then each
t_{i}
is bounded by
We substitute (2) into (1) and denote
Then, the order of the Jacobian follows the equation
We should determine the values (
t
_{1}
,
t
_{2}
,
t
_{3}
) in order to get ♯
J_{C}
(
). Assume that
N
is a positive integer(to be specified). Let
u
and
v
be integers such that
Then, the boundary for
v
is
By substituting (4) into (3), we have
Hence, ♯
J_{C}
(
) can be computed by finding the 4-tuple (
t
_{1}
,
t
_{2}
,
u
,
v
) such that
for all
D
∈
J_{C}
(
) for the above each ranges. We search for a collision between the lhs and the rhs of (5) in the corresponding ranges. Moreover, we choose
Thus the algorithm require the computation of
O
(
N
) point multiples.
5.2. Speeding up algorithm.
In this section, we discuss the some technique to speed up the algorithm during its implementation. First, we use the Cornacchia’s algorithm in order to compute the coefficients
in (2) (see
[10]
). Then we can be easily calculated the binomial coefficients. Moreover, since
if
p
> 37, then
s
_{1}
is uniquely determined by sum of
c_{p}
_{−1}
,
c
_{2p−2}
and
c
_{3p−3}
.
In
[2]
, Gonda et. al. provide the efficient arithmetic on Jacobian of genus 3 hyperelliptic curves over a finite field. Using this method, the addition operation in a Jacobian can be computed by performing 70 multiplications and 1 inversions and 113 additions. The doubling can be obtained as 71 multiplications, 1 inversion and 107 additions.
In (5) of section 5.1, the precomputation of
p
and the addition of a divisor
pN
times are needed, and an double-and-add method is used for these operations. When we search for a collision between them, the same divisors are repeatedly computed. So, we store them at first and subsequently execute the comparison test. Two divisors identical and therefore, their chord are the same. Hence, we can limit the boundary to 0 ≤
k
≤ ⌊
U
_{3}
/
N
⌋ and then avoid the computation for the inversion of a divisor.
Now, we consider an efficient value
N
for the case of Theorem 4.7. We let
c
_{3}
=
u
+
vN
with 0 ≤
u
<
N
and
For the
v
, there are
choices, and for
u
there are
N
choices. We also set the
N
as
In (2) of Theorem 4.6, the
s
_{1}
and
s
_{2}
are easily determined. We similarly set the
N
as
Therefore, the expected running time of our algorithm is
Example 6.1.
Let
p
= 12970096625951449 be a 54-bit prime and let curve
C
over
be defined by
We compute the group order of the Jacobian:
Example 6.2.
Let
p
= 26144785074025909 be a 55-bit prime and let
C
be the curve defined by
C
:
y
^{2}
=
x
^{7}
+ 4857394849
x
. The group order of the Jacobian is given by:
The number of the Jacobian is of 163 bits and the total time is 259 s.
Table 1
has the implementation results for Jacobians with a quasiprime factor greater than 160 bits.
Implementation results
y
^{2}
=
x
^{7}
+
ax
over a finite prime field. By using the baby-step giant-step method, we determined the order of the Jacobian of a curve defined over a finite prime field bigger than 55 bit. Moreover, we also provided the explicit formula of the characteristic polynomial of the Frobenius endomorphism of the Jacobian of the hyperelliptic curves
y
^{2}
=
x
^{7}
+
ax
over
with
p
≡ 1 modulo 12. Finally, we verified usefulness of the our algorithm by the simple examples.
Gyoyong Sohn received the Ph.D degree in Mathematics from Kyungpook National University in 2008. He has been an assistant professor in Department of Mathematics Education at Daegu National University since 2012. His research interests include computational algebraic geometry and cryptography.
Department of Mathematics Education, Daegu National University of Education, Daegu National University of Education, Daegu 705-715, Korea.
e-mail: gysohn@dnue.ac.kr

1. Introduction

In recent years, computing the number of points on algebraic curves over finite fields is an important task for public key cryptography. In order to generate curves suitable for cryptosystems, we must determine the order of Jacobian of a curve over a finite field. It is required that the order of Jacobian is a prime or a small cofactor times a prime.
For elliptic curves, Schoof gave a polynomial time algorithm
[7]
and there are its improved algorithm for the time and space complexity
[1
,
5
,
12]
. Gaudry and Harley extended its algorithm to genus 2 curve
[4]
. For higher genus curves, there are several efficient counting points algorithms of Jacobian varieties
[13
,
14
,
15]
. In
[9]
, authors suggest a fast point counting algorithm for genus 2 hyperelliptic curves of type
PPT Slide

Lager Image

2. Basic Facts on Hyperelliptic Curves

Let
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- (1)
- (2)
- (3)
- (4)

3. Hasse-Witt matrix

In this section, we recall the definition of the Hasse-Witt matrix in the case of hyperelliptic curves. It is a useful tool to compute the modulo characteristic
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

4. The Characteristic Polynomial of C

In this section, we present the explicit formula of the characteristic polynomial of the Frobenius endomorphism on hyperelliptic curves of type
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- 1.if A≡ 1, 2(mod 3) and B≡ 0(mod 3),then
- s1≡ 2Aa(p−1)/12(a(p−1)/3+a(p−1)/6+ 1)(mod p),
- s2≡ 4A2a(p−1)/3(a(p−1)/3+a(p−1)/6+ 1)(mod p),
- s3≡ 8A3a(9p−9)/12(mod p).
- 2.if A≡ 0(mod 3) and B≡ 1, 2(mod 3), then
- s1≡(mod p),
- s2≡(mod p),
- s3≡(mod p),

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- s1≡cp−1+c2p−2+c3p−3(modp),
- s2≡cp−1c2p−2+c2p−2c3p−3+cp−1c3p−3(modp),
- s3≡cp−1c2p−2c3p−3(modp).

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- 1.If a(p−1)/12= 1,thenχ(t) = (t2− 2At+p)3.
- 2.If a(p−1)/12= -1,andχ(t) = (t2− 2At+p)3.

- 3.If a(p−1)/12= 1,then
- 4.If a(p−1)/12= -1,then

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

5. Implementation details

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

6. Computational results

In this section, we present our experimental results. We implemented our algorithm on a Pentium 2.13 GHz computer with less than 2 GB memory using Shoup’s NTL library.
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

Implementation results

PPT Slide

Lager Image

7. Conclusions

In this paper, we have presented an algorithm for computing the orders of the Jacobian varieties of genus 3 hyperelliptic curves defined by
PPT Slide

Lager Image

BIO

Elkies N.
(1998)
Elliptic and modular curves over finite fields and related computational issues, Computational perspectives on number theory
AMS/IP Stud. Adv. Math.
Math. Soc.
7
21 -
76

Gonda M.
,
Matsuo K.
,
Aoki K.
,
Chao J.
(2005)
Improvements of Addition Algorithm on Genus 3 Hyperelliptic Curves and Their Implementation
IEICE TRANS. FUNDAMENTALS
E88-A
(1)
89 -
96
** DOI : 10.1093/ietfec/E88-A.1.89**

Hudson R. H.
,
Williams K. S.
(1984)
Binomial Coefficients and Jacobi Sums
Trans. Amer. Math. Soc.
281
431 -
505
** DOI : 10.1090/S0002-9947-1984-0722761-X**

Gaudry P.
,
Harley R.
(2000)
Counting points on hyperelliptic curves over finite fields, ANTSIV, W. Bosma ed.
LNCS
Springer-Verlag
1838
297 -
312

Blake I.
,
Seroussi G.
,
Smart N.
(1999)
Elliptic curves in cryptography
London Math. Soc. Lecture Note Series
265

Yui H.
(1987)
On the jacobian varieties of hyperelliptic curves over fields of characteristic p ≥ 2
J. Algebra
52
378 -
410
** DOI : 10.1016/0021-8693(78)90247-8**

Schoof R.
(1985)
Elliptic curves over finite fields and the computation of square roots mod p
Math. Comp.
44
483 -
494

Manin Yu. I.
(1965)
The Hasse-Witt matrix of an algebraic curve
AMS Trans. Ser. 2
45
245 -
264

Furukawa E.
,
Kawazoe M.
,
Takahashi T.
2004
Counting Points for Hyperelliptic Curves of Type y2= x5+ ax over Finite Prime Fields
LNCS
26 -
41

Buhler J.
,
Koblitz N.
(1998)
Lattics Basis Reduction, Jacobi Sums and Hyperelliptic Cryptosystems
Bull. Austral. Math. Soc.
58
147 -
154
** DOI : 10.1017/S000497270003207X**

Mumford D.
1984
Tata Lectures on Theta II
Progress in Mathematics
Birkhäuser
43

Lercier R.
1997
Algorithmique des courbes elliptiques dans les corps finis.
Thèse, Ècole polytechnique

Adleman L.
,
Huang M. D.
(2001)
Counting points on curves and abelian varieties over finite fields
J. Symb. Comp.
32
(3)
171 -
189
** DOI : 10.1006/jsco.2001.0470**

Huang M. D.
,
Ierardi D.
(1998)
Counting points on curves over finite fields
J. Symb. Comp.
25
(1)
1 -
21
** DOI : 10.1006/jsco.1997.0164**

Pila J.
(1990)
Frobenius maps of abelian varieites and finding roots of unity in finite fields
Math. Comp.
55
(192)
745 -
763
** DOI : 10.1090/S0025-5718-1990-1035941-X**

Kedlaya K.S.
(2001)
Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology
J. Ramanujan Math. Soc.
16
323 -
338

Satoh T.
(2000)
The canonical lift of an ordinary elliptic curve over a finite field and its point counting
J. Ramanujan Math. Soc.
15
247 -
270

Denef J.
,
Vercauteren F.
(2006)
An Extension of Kedlaya’s Algorithm to Hyperelliptic Curves in Characteristic 2
J. Cryptology
19
1 -
25
** DOI : 10.1007/s00145-004-0231-y**

Haloui S.
2011
The characteristic polynomials of abelain varieites of dimensions 3 over finite fields
J. number theory

Citing 'OMPUTING THE NUMBER OF POINTS ON GENUS 3 HYPERELLIPTIC CURVES OF TYPE Y2 = X7 + aX OVER FINITE PRIME FIELDS†
'

@article{ E1MCA9_2014_v32n1_2_17}
,title={OMPUTING THE NUMBER OF POINTS ON GENUS 3 HYPERELLIPTIC CURVES OF TYPE Y2 = X7 + aX OVER FINITE PRIME FIELDS†}
,volume={1_2}
, url={http://dx.doi.org/10.14317/jami.2014.017}, DOI={10.14317/jami.2014.017}
, number= {1_2}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={SOHN, GYOYONG}
, year={2014}
, month={Jan}