In this paper, we study the bounds of the coefficients of the characteristic polynomial of the Frobenius endomorphism of the Jacobian of dimension three over a finite field. We provide explicitly computable bounds for the coefficients of the characteristic polynomial. In addition, we present the counting points algorithm for computing a group of the Jacobian of genus 3 hyperelliptic curves over a finite field with large characteristic. Based on these bounds, we found an efficient search space that was used in the counting points algorithm on genus 3 curves. The algorithm was explained and verified through simple examples.
AMS Mathematics Subject Classification : 14H45, 14G50, 94A60.
1. Introduction
The problem of counting points on the Jacobian of algebraic curves over finite fields is very important in constructing curvebased cryptosystems. In order to obtain cryptographically suitable curves, we must determine the number of rational points on the Jacobian. If the orders of the Jacobians are sufficiently large prime numbers, then the corresponding cryptosystems are secure against various attacks.
For a long time, the counting points algorithm on elliptic and hyperelliptic curves over finite fields has been studied by numerous researchers. Schoof provided the first polynomial time algorithm for elliptic curves in all characteristics
[17]
. A detailed descriptions of Schoof’s algorithm and the improvements by Atkin and Elkies
[4]
can be found in
[2]
and
[10]
. In algebraic varieties over a finite field of small characteristic, Satoh first proposed an algorithm based on
p
adic methods for elliptic curves
[16]
. This algorithm is asymptotically faster than the Schoof’s like method.
For higher genus curves, the equivalent problem seems to be much more difficult. In small characteristic, there exist efficient practical algorithms for computing the number of points on the Jacobian of higher genus curves based on theoretical progression. Kedlaya generalized Satoh’s method to hyperelliptic curves of any genus over finite fields of odd characteristic
[9]
. The AGM method generalizes to ordinary hyperelliptic curves of any genus; however, only the genus 2 case is practical. In large characteristic, Pila
[14]
and later Adleman and Huang
[1
,
8]
described a theoretical generalization of Schoof’s approach; however, the algorithms are not practical. Currently, only the genus 2 case of this algorithm is practical
[5
,
6]
.
Throughout this paper, we concentrate on
l
adic method for genus 3 curves. The
l
adic method computes the number of points modulo sufficient small primes
l
by working in
l
torsion subgroups of the Jacobian. If the characteristic is not too large, we can use the CatierManin operator to get additional modular information of the Jacobian. Then, one applies Weil’s bounds on the coefficient of the characteristic polynomial. Hence, the final result is determined using a search algorithm such as Pollard lambda method or babystep giantstep (BSGS) algorithm. Matsuo, Chao, and Tsujii (MCT) proposed a BSGS algorithm that speeds up the last computational part. Recently, GaudrySchost presented a low memory version of MCT algorithm based on birthday paradox.
When implementing the practical counting points algorithm, it is important to determine the number of candidates on the search space. It is related to the running time of the Jacobian. In the case of genus 2 curve, Ruck provided efficient bounds of the coefficients of the characteristic polynomial
[15]
. Recently, Haloui presented the bounds of the coefficients for genus 3 curve cases
[7]
.
In this paper, we investigate the bounds of the coefficients of the characteristic polynomial of the Frobenius endomorphism of the Jacobian of dimension three over a finite field. In addition, we provide efficient computable bounds of the coefficients of the characteristic polynomial. These bounds will be used in the search method part of the counting points algorithm. Moreover, we derive the number of the search space for the counting points algorithm for the genus 3 curve. Based on this, we describe an algorithm that compute the order of the Jacobian group for genus 3 hyperelliptic curves over finite fields with a large characteristic. In the algorithm, we propose a reduced search space based on the experimental results. Finally, we verify the usefulness of the proposed method through some simple examples.
2. Basic Facts
Let
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}
.
The
zeta function ζ
(
t, C
) of
C
can be written as
where
L
(
t, C
) is the
Lpolynomial
of the curve. Let
π_{q}
be the Frobenius endomorphism of
C
and
χ_{C}
(
t
) the characteristic polynomial of
π_{q}
on the Tate module
Then
χ_{πq,C}
(
t
) =
t
^{2}
^{g}
L
(1/
t, C
). For simplicity, we write
χ
(
t
) instead of
χ
_{πq}
,
_{C}
(
t
) if the reference to the curve is clear. The polynomial
χ
(
t
) is also called a
Weil polynomial
if the complex roots of
χ
(
t
) have the absolute value
Throughout this paper, we consider the hyperelliptic curves of genus 3 over finite fields
. Then, its characteristic polynomial has the form
for certain integers
s
_{1}
,
s
_{2}
, and
s
_{3}
. We obviously have
=
χ
(1), i.e.,
Let
M_{r}
= (
q^{r}
+ 1) −
N_{r}
, where
N_{r}
is the number of
rational points on
C
for
r
= 1, 2, 3. Then, we have
Thus, to compute the number of
rational points on
J_{C}
, we need only the values of three coefficients of the characteristic polynomial or, equivalently, the number of points
N_{r}
for
r
= 1, 2, 3.
The following is a wellknown inequality, the HasseWeil bound, that bound
:
Then, we have
3. The Sharp Bounds of the Coefficients ofχ(t)
n this section we investigate the efficient bounds of the coefficients of the characteristic polynomial
χ
(
t
). S. Haloui
[7]
reported on the set of characteristic polynomials of abelian varieties of dimension 3 over finite fields.
Theorem 3.1
(
[7]
).
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
Proof
. See S Haloui
[7]
. □
Denote
U
_{3}
_{a}
(resp.
L
_{3}
_{a}
) the upper (resp. lower) bound of
s
_{3}
in (3) of Theorem 3.1, respectively, and
U
_{3}
_{b}
(resp.
L
_{3}
_{b}
) the upper (resp. lower) bound of
s
_{3}
in (4) of Theorem 3.1, respectively. The following theorem gives an efficient choice between the two upper (resp. lower) bounds for
s
_{3}
in Theorem 3.1.
Theorem 3.2.
Let χ
(
t
)
be a Weil polynomial of degree 6 defined by equation
(1).
Then, the upper bound of s
_{3}
is defined as
where
Similarly, the lower bound of s
_{3}
is defined as
where
Proof
. First, we consider the upper bounds
U
_{3}
_{a}
and
U
_{3}
_{b}
of
s
_{3}
. The difference between
U
_{3}
_{a}
and
U
_{3}
_{b}
is as follows:
If
U
_{3}
_{a}

U
_{3}
_{b}
= 0, then we have a line of intersection for them. After squaring the equation, we have the following
It is imply that
Since the left hand side of the second equation
is the lower bound of
s
_{2}
in (2) of Theorem 3.1, the line of intersection of
U
_{3}
_{a}
and
U
_{3}
_{b}
in the possible range
Thus we can easily check if
then
U
_{3}
_{a}

U
_{3}
_{b}
is positive, and if
then
U
_{3}
_{a}

U
_{3}
_{b}
is negative.
Similarly, we compute the difference between
L
_{3}
_{a}
and
L
_{3}
_{b}
, and if its difference is zero, then we have the following:
Then the equation
is contained within the range of
s
_{1}
and
s
_{2}
. It is the line of intersection for
L
_{3}
_{a}
and
L
_{3}
_{b}
. Thus, we have if
L
_{3}
_{a}

L
_{3}
_{b}
> 0, then
The proof is completed. □
Lemma 3.3.
If
then the lower bound of s_{3} in
(1)
is defined as L
_{3}
_{a}. If
hen the upper bound of s_{3} is defined as
U
_{3}
_{a}
.
Proof
. For
we have
Because of the previous theorem, the lower bound of
s
_{3}
is just defined as
L
_{3}
_{a}
. Similarly, we can check the upper bound of
s
_{3}
for
□
Now we discuss the inequalities of
s
_{3}
in
The following theorem shows the sharp bound of
s
_{2}
with respect to
s
_{1}
.
Theorem 3.4.
Let χ
(
t
)
be a Weil polynomial of degree 6 defined by equation
(1).
Then the lower bound of s
_{2}
is defined as
Proof
. If
χ
(
t
) is a Weil polynomial of degree 6 defined by equation (1), then each coefficient of the polynomial
χ
(
t
) should satisfy the inequalities of
s_{i}
in Theorem 3.1 for
i
= 1, 2, 3.
Note that
at the upper boundary of
for all
For
s
_{1}
≥ 0, the value of
U
_{3}
_{b}
is equal to
L
_{3}
_{a}
at the lower boundary of
for all
s
_{1}
. i.e.,
U
_{3}
_{b}
=
L
_{3}
_{a}
. Similarly,
U
_{3}
_{a}
=
L
_{3}
_{b}
at the lower boundary of
for
s
_{1}
≤ 0. From Theorem 3.2 and Lemma 3.3, in
the upper bounds of
s
_{3}
,
U
_{3}
_{a}
and
U
_{3}
_{b}
, are always bigger than the lower bounds of
s
_{3}
,
L
_{3}
_{a}
and
L
_{3}
_{b}
.
Let us consider
If
s
_{2}
≥
r
(
s
_{1}
) for
and
s
_{2}
≥
t
(
s
_{1}
) for
then the upper bounds of
s
_{3}
are always bigger than the lower bounds of
s
_{3}
. Now, let us consider
The line of intersection for
L
_{3}
_{b}
and
U
_{3}
_{b}
is
Thus if
s
_{2}
< −
q
, then the coefficient of
s
_{3}
is not satisfied with the inequalities of both condition (3) and (4) in Theorem 3.1. The inequality of
s
_{3}
in (4) can be changed to
U
_{3}
_{b}
≤
s
_{3}
≤
L
_{3}
_{b}
. Thus, the above conditions hold. □
4. Counting Points Algorithm
In this section, we describe the counting points algorithm on hyperellipitic curves of genus 3 over finite fields with a large characteristic.
4.1. MCT Algorithm.
Matsuo, Chao and Tsujii present an algorithm to determine the order of the Jacobian for hyperelliptic curves over finite fields using an improved BSGS method. Now, we describe the MCT algorithm for the computational part.
Assume that the characteristic polynomial is known modulo some positive integer
m
, i.e.,
s
_{1}
,
s
_{2}
and
s
_{3}
are known modulo
m
. Denote that for
i
= 1, 2, 3
with
Note that
s_{i}
is known and
t_{i}
is unknown. We substitute (4) into (2) 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
. Hence,
can be computed by finding the triples (
t
_{1}
,
t
_{2}
,
t
_{3}
) such that
for a random element
. For some positive integer
N
to be specified, let
u, v
be integers such that
By substituting (6) into (5),
can be computed by finding the 4tuples (
t
_{1}
,
t
_{2}
,
u, v
) such that
for a random element
in the corresponding ranges. These computations are terminated by searching for a collision between the LHS and the RHS of (7) among different candidates. Moreover, the BSGS method is used in (7). The algorithm requires the computation of
O
(
N
) group operations and storage of
O
(
N
) group elements.
4.2. The Number of The Search Space.
The value
N
of the previous method is determined by the number of different candidates in the searching space. From the HasseWeil bound, the number of the search space is 14, 400
q
^{3}
. Thus, the value of
N
is approximately 120
q
^{3/2}
/
m
^{3/2}
, which is the running time of group operations in
J_{C}
.
Then, we compute the efficient value of
N
from the results in Section 3. Assume that
s
_{1}
is a positive integer smaller than
(for the negative part of
s
_{1}
, the computation is same because the boundaries of
s_{i}
are symmetrical about
s
_{2}
in dimension 3.) Let
We compute the two parts centered by
of
s
_{1}
. For
the number of (
s
_{1}
,
s
_{2}
,
s
_{3}
) is:
For
the number of (
s
_{1}
,
s
_{2}
,
s
_{3}
) is:
Thus the number of the triples (
s
_{1}
,
s
_{2}
,
s
_{3}
) is roughly
Moreover, the number
S
of the (
t
_{1}
,
t
_{2}
,
t
_{3}
) is
We can choose a value of
N
as
Thus the algorithm requires the computation of
O
(
N
) point multiples and memory storage. Hence, we see that the number of the search space is reduced to a constant factor of about 18 compared with the Weil’s bound.
4.3. GaudrySchost Algorithm.
GaudrySchost algorithm is a lowmemory algorithm for computing the number of the Jacobian of hyperelliptic curves over finite fields
[6]
. The basic idea is the same as the kangaroo algorithm of Pollard in the van Oorschot and Wiener formulation
[13]
. We now briefly describe the GaudrySchost algorithm for genus 3 curves.
Let
BU_{i}
(rep.
BL_{i}
) be an upper (rep. lower) bound of
t_{i}
for
i
= 1, 2, 3. From (5), we wish to find integers (
t
_{1}
,
t
_{2}
,
t
_{3}
) ∈ ℤ
^{3}
,
t_{i}
∈ [
BL_{i}
,
BU_{i}
], such that
where
for a random element
. Denote the set
and
M_{i}
= ⌊
(
BL_{i}
+
BU_{i}
)/2⌋ for
i
= 1, 2, 3. The basic GaudrySchost algorithm for this problem is as follows. The tame set is defined as
and the wild set as
The Gaudry and Schost algorithm run a large number of (deterministic) pseudorandom walk. Half the walks are ”tame walks”, which means that every element in the walk is of the form
a
_{1}
·
D
_{1}
+
a
_{2}
·
D
_{2}
+
a
_{3}
·
D
_{3}
where the integer triples (
a
_{1}
,
a
_{2}
,
a
_{3}
) ∈
T
(though note that with very small probability some walks will go outside
T
). The other half are ”wild walks”, which means that every element is of the form
where the integer triples (
b
_{1}
,
b
_{2}
,
b
_{3}
) ∈
T
and
Each walk proceeds until a distinguished point is hit. This distinguished point is then stored on a server, together with the corresponding exponent vectors (
n
_{1}
,
n
_{2}
,
n
_{3}
) and a flag indicating which sort of walk it was. The collusion of two different types of walks exist if and only if
for all
i
= Then, we can find the triples (
t
_{1}
,
t
_{2}
,
t
_{3}
) such that
χ
(1) ·
D
= 0. Since a collision between the tame and wild walks can only occur in
T
∩
W
, we can easily check that
The following theorem shows the running time of the GaudrySchost algorithm in the case of genus 3 curve.
Theorem 4.1.
Given the problem by
(8)
and N is the number of the search space. The expected number of group operations in the average case of the GaudrySchost algorithm is
Proof
. We assume that
BL_{i}
= −
BU_{i}
and denote
B_{i}
for each
i
. Then, we consider the following problem instance:
with
t_{i}
∈ [−
B_{i}
,
B_{i}
] for
i
. The number of overlaps between
T
and
W
is
Therefore, we expect only about ♯(
T
∩
W
)/
N
of the walks to be in
T
∩
W
. The algorithm is based on the birthday paradox. Assume that
t
_{1}
,
t
_{2}
and
t
_{3}
are uniformly distributed. Thus the average case expected running time is
If
χ
is the known modulo
m
with
then there are many candidates for
s
_{1}
,
s
_{2}
and
s
_{3}
which have bounds in Theorem 3.1. These bounds yield the approximate bounds for
t
_{1}
,
t
_{2}
and
t
_{3}
:
Hence, the number of the search space is ♯
V
= 7680
q
^{3}
/
m
^{3}
. From Theorem 4.1, the approximate value of 2.85 then yield a running time of about 249.761
q
^{3/2}
/
m
^{3/2}
operations in
J_{C}
(
). Compared with the MCT algorithm we lost a constant factor of about 39.
In the case where
the coefficient
s
_{1}
is uniquely determined since
Then we only have to consider the corresponding bounds for
t
_{2}
and
t
_{3}
in (9). Hence, the number of the search space is ♯
V
= 640
q
^{5/2}
/
m
^{2}
. In
[6]
, the average case running time for a genus 2 curve is approximately
Thus the expected running time is 61.47
q
^{5/4}
/
m
group operations in
J_{C}
(
). This is worse than the
O
(
q
^{3/2}
/
m
^{3/2}
) complexity.
4.4. Reducing the Search Space.
In this section, we investigate the distribution of the coefficients (
s
_{1}
,
s
_{2}
,
s
_{3}
) in the search space. It was up to us to reduce the space complexity for the counting points algorithm. We first selected 10,000 random monic, squarefree polynomials of degree 7 over finite fields
with the small random prime
p
. Then, we computed the values (
s
_{1}
,
s
_{2}
,
s
_{3}
) for the corresponding curves using a wellknown algorithm. Table 4.4 shows the proportion of the curves for which each
s_{i}
is larger than some bound.
In
Table 1
, for
the proportion of the curves is approximately 0.0186. So, more than 99.9% of the curves have
Thus, we can restrict the search space to the following bounds:
where
Distribution of (s1,s2,s3)
Distribution of (s_{1}, s_{2}, s_{3})
In this case, for the fixed value
t
_{3}
, we can easily obtain the bounds of
V
_{1}
and
V
_{2}
according to the bounds in Section 3. Moreover, the overlapping factor of
W
and
T
is at least 1/4. The number of elements in
V
is reduced to 1024
q
^{3}
/
m
^{3}
so that the expected runtime is approximately 91.2
q
^{3/2}
/
m
^{3/2}
group operations. Therefore, we reduced the running time by a factor of 2.7 compared to the previous running time.
For
99.4% of the curves exists in this bound. In this case, the overlapping factor is at least
and 
s
_{2}
 > 11
q
, the sets,
W
and
T
, do not overlap.
5. Experimental Results
We implemented two algorithms in C++ using Shoup’s NTL library on a Pentium 2.13 GHz computer with less than 2 GB memory.
Example 5.1.
Let prime
p
= 10
^{6}
+ 37 and
C
be the hyperelliptic curve given by
Using the classical counting points algorithm we easily computed the values of
s
_{1}
,
s
_{2}
and
s
_{3}
modulo
m
= 1874. The curve is such that
therefore it is not close to any border of the bounds. The group of points has cardinality
Example 5.2.
Let
p
= 26144785074025909 be a 55bit 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.
6. Conclusions
In this paper, we have presented algorithms for computing the orders of the Jacobian varieties of genus 3 hyperelliptic curves over finite fields. We also have computed the efficient bound of the characteristic polynomial of the Jacobian and determined the number of the search space. From these bounds, we have given the number of the search space, equivalently, the number of candidates in the counting points algorithm. We also studied the search space with the practical algorithm. Finally, we presented simple examples of random hyperelliptic curves of genus 3 over finite fields.
BIO
Gyoyong Sohn received M.Sc. and Ph.D from Kyungpook National University. He is currently an assistant professor in the Department of Mathematics Education at Deagu National University of Education. His research interests are computational algebraic geometry and cryptography.
Department of Mathematics Education, Deagu National University of Education, 219 Jungangdaero, Deagu 705715, Korea.
email: gysohn@dnue.ac.kr
Adleman L.
,
Huang M. D.
(1996)
Counting rational points on curves and abelian varieties over finite fields, in H. Cohen (ed.), ANTSII, LNCS 1122
SpringerVerlag
1 
16
Blake I.
,
Seroussi G.
,
Smart N.
(1999)
Elliptic curves in cryptography
London Math. Soc. Lecture Note Series
265
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/s001450040231y
Elkies N.
(1998)
Elliptic and modular curves over finite fields and related computational issues, Computational perspectives on number theory, vol. 7 of AMS/IP Stud. Adv. Math.
Am. Math. Soc.
21 
76
Gaudry P.
,
Harley R.
(2000)
Counting points on hyperelliptic curves over finite fields, ANTSIV, W. Bosma ed., LNCS 1838
SpringerVerlag
297 
312
Gaudry P.
,
Schost E.
2004
A lowmemory parallel version of Matsuo, Chao and Tsujii’s algorithm, In D. A. Buell, editor
SpringerVerlag
Proceedings of Algorithm Number Theory SympositumANTS VI.
volume 3076 of LNCS
208 
222
Haloui S.
2011
The characteristic polynomials of abelian varieties of dimensions 3 over finite fields
J. Number theory
Kedlaya K.S.
(2001)
Counting points on hyperelliptic curves using MonskyWashnitzer cohomology
J. Ramanujan Math. Soc.
16
323 
338
Lercier R.
1997
Algorithmique des courbes elliptiques dans les corps finis. Thése, École polytechnique
Manin Yu. I.
(1965)
The HasseWitt matrix of an algebraic curve
AMS Trans. Ser.
2
(45)
245 
264
Matsuo K.
,
Chao J.
,
Tsujii S.
2002
An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields, In C. Fiecker and D. Kohel, editors
SpringerVerlag
Proceedings of Algorithm Number Theory SymposiumANTS V.
volume 2369 of LNCS
461 
474
Oorschot V.
,
Wiener, M.J. P.C.
(1990)
Parallel collusion Search with Cryptanalytic Applications
J. Cryptology
12
1 
28
DOI : 10.1007/PL00003816
Rück H.G.
(1990)
Abelian surfaces and jacobian varieties over finite fields
Compositio Math.
76
(3)
351 
366
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
Schoof R.
(1985)
Elliptic curves over finite fields and the computation of square roots modp
Math. Comp.
44
483 
494
Sohn G.
(2012)
Pointing algorithm for onedimensional family of genus 3 nonhyperelliptic curves over finite fields
J. Appl. Math. & Informatics
30
101 
109