Advanced
AN EFFICIENT SEARCH SPACE IN COUNTING POINTS ON GENUS 3 HYPERELLIPTIC CURVES OVER FINITE FIELDS
AN EFFICIENT SEARCH SPACE IN COUNTING POINTS ON GENUS 3 HYPERELLIPTIC CURVES OVER FINITE FIELDS
Journal of Applied Mathematics & Informatics. 2015. Jan, 33(1_2): 145-155
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : June 11, 2014
  • Accepted : October 16, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
GYOYONG SOHN

Abstract
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.
Keywords
1. Introduction
The problem of counting points on the Jacobian of algebraic curves over finite fields is very important in constructing curve-based 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 Catier-Manin 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 baby-step giant-step (BSGS) algorithm. Matsuo, Chao, and Tsujii (MCT) proposed a BSGS algorithm that speeds up the last computational part. Recently, Gaudry-Schost 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
PPT Slide
Lager Image
be a finite field of q = pn elements, where p is an odd prime. The hyperelliptic curve C of genus g over
PPT Slide
Lager Image
is given by
PPT Slide
Lager Image
where f ( x ) is a polynomial in
PPT Slide
Lager Image
[ x ] of degree 2 g + 1 without singular points. We denote the Jacobian variety of a hyperelliptic curve C by JC . Then, JC (
PPT Slide
Lager Image
) is the group of
PPT Slide
Lager Image
-rational points on JC .
The zeta function ζ ( t, C ) of C can be written as
PPT Slide
Lager Image
where L ( t, C ) is the L-polynomial of the curve. Let πq be the Frobenius endomorphism of C and χC ( t ) the characteristic polynomial of πq on the Tate module
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Throughout this paper, we consider the hyperelliptic curves of genus 3 over finite fields
PPT Slide
Lager Image
. Then, its characteristic polynomial has the form
PPT Slide
Lager Image
for certain integers s 1 , s 2 , and s 3 . We obviously have
PPT Slide
Lager Image
= χ (1), i.e.,
PPT Slide
Lager Image
Let Mr = ( qr + 1) − Nr , where Nr is the number of
PPT Slide
Lager Image
-rational points on C for r = 1, 2, 3. Then, we have
PPT Slide
Lager Image
Thus, to compute the number of
PPT Slide
Lager Image
-rational points on JC , we need only the values of three coefficients of the characteristic polynomial or, equivalently, the number of points Nr for r = 1, 2, 3.
The following is a well-known inequality, the Hasse-Weil bound, that bound
PPT Slide
Lager Image
:
PPT Slide
Lager Image
Then, we have
PPT Slide
Lager Image
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
PPT Slide
Lager Image
where
PPT Slide
Lager Image
Similarly, the lower bound of s 3 is defined as
PPT Slide
Lager Image
where
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
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
PPT Slide
Lager Image
It is imply that
PPT Slide
Lager Image
Since the left hand side of the second equation
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Thus we can easily check if
PPT Slide
Lager Image
then U 3 a - U 3 b is positive, and if
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
Then the equation
PPT Slide
Lager Image
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
PPT Slide
Lager Image
The proof is completed. □
Lemma 3.3. If
PPT Slide
Lager Image
then the lower bound of s3 in (1) is defined as L 3 a. If
PPT Slide
Lager Image
hen the upper bound of s3 is defined as U 3 a .
Proof . For
PPT Slide
Lager Image
we have
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Now we discuss the inequalities of s 3 in
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 si in Theorem 3.1 for i = 1, 2, 3.
Note that
PPT Slide
Lager Image
at the upper boundary of
PPT Slide
Lager Image
for all
PPT Slide
Lager Image
For s 1 ≥ 0, the value of U 3 b is equal to L 3 a at the lower boundary of
PPT Slide
Lager Image
for all s 1 . i.e., U 3 b = L 3 a . Similarly, U 3 a = L 3 b at the lower boundary of
PPT Slide
Lager Image
for s 1 ≤ 0. From Theorem 3.2 and Lemma 3.3, in
PPT Slide
Lager Image
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
PPT Slide
Lager Image
If s 2 r ( s 1 ) for
PPT Slide
Lager Image
and s 2 t ( s 1 ) for
PPT Slide
Lager Image
then the upper bounds of s 3 are always bigger than the lower bounds of s 3 . Now, let us consider
PPT Slide
Lager Image
The line of intersection for L 3 b and U 3 b is
PPT Slide
Lager Image
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
PPT Slide
Lager Image
with
PPT Slide
Lager Image
Note that si is known and ti is unknown. We substitute (4) into (2) and denote
PPT Slide
Lager Image
Then, the order of the Jacobian follows the equation
PPT Slide
Lager Image
We should determine the values ( t 1 , t 2 , t 3 ) in order to get
PPT Slide
Lager Image
. Hence,
PPT Slide
Lager Image
can be computed by finding the triples ( t 1 , t 2 , t 3 ) such that
PPT Slide
Lager Image
for a random element
PPT Slide
Lager Image
. For some positive integer N to be specified, let u, v be integers such that
PPT Slide
Lager Image
By substituting (6) into (5),
PPT Slide
Lager Image
can be computed by finding the 4-tuples ( t 1 , t 2 , u, v ) such that
PPT Slide
Lager Image
for a random element
PPT Slide
Lager Image
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 Hasse-Weil 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 JC .
Then, we compute the efficient value of N from the results in Section 3. Assume that s 1 is a positive integer smaller than
PPT Slide
Lager Image
(for the negative part of s 1 , the computation is same because the boundaries of si are symmetrical about s 2 in dimension 3.) Let
PPT Slide
Lager Image
We compute the two parts centered by
PPT Slide
Lager Image
of s 1 . For
PPT Slide
Lager Image
the number of ( s 1 , s 2 , s 3 ) is:
PPT Slide
Lager Image
For
PPT Slide
Lager Image
the number of ( s 1 , s 2 , s 3 ) is:
PPT Slide
Lager Image
Thus the number of the triples ( s 1 , s 2 , s 3 ) is roughly
PPT Slide
Lager Image
Moreover, the number S of the ( t 1 , t 2 , t 3 ) is
PPT Slide
Lager Image
We can choose a value of N as
PPT Slide
Lager Image
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. Gaudry-Schost Algorithm. Gaudry-Schost algorithm is a low-memory 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 Gaudry-Schost algorithm for genus 3 curves.
Let BUi (rep. BLi ) be an upper (rep. lower) bound of ti for i = 1, 2, 3. From (5), we wish to find integers ( t 1 , t 2 , t 3 ) ∈ ℤ 3 , ti ∈ [ BLi , BUi ], such that
PPT Slide
Lager Image
where
PPT Slide
Lager Image
for a random element
PPT Slide
Lager Image
. Denote the set
PPT Slide
Lager Image
and Mi = ⌊ ( BLi + BUi )/2⌋ for i = 1, 2, 3. The basic Gaudry-Schost algorithm for this problem is as follows. The tame set is defined as
PPT Slide
Lager Image
and the wild set as
PPT Slide
Lager Image
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
PPT Slide
Lager Image
where the integer triples ( b 1 , b 2 , b 3 ) ∈ T and
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
The following theorem shows the running time of the Gaudry-Schost 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 Gaudry-Schost algorithm is
PPT Slide
Lager Image
Proof . We assume that BLi = − BUi and denote Bi for each i . Then, we consider the following problem instance:
PPT Slide
Lager Image
with ti ∈ [− Bi , Bi ] for i . The number of overlaps between T and W is
PPT Slide
Lager Image
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
PPT Slide
Lager Image
If χ is the known modulo m with
PPT Slide
Lager Image
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 :
PPT Slide
Lager Image
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 JC (
PPT Slide
Lager Image
). Compared with the MCT algorithm we lost a constant factor of about 39.
In the case where
PPT Slide
Lager Image
the coefficient s 1 is uniquely determined since
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Thus the expected running time is 61.47 q 5/4 / m group operations in JC (
PPT Slide
Lager Image
). 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, square-free polynomials of degree 7 over finite fields
PPT Slide
Lager Image
with the small random prime p . Then, we computed the values ( s 1 , s 2 , s 3 ) for the corresponding curves using a well-known algorithm. Table 4.4 shows the proportion of the curves for which each si is larger than some bound.
In Table 1 , for
PPT Slide
Lager Image
the proportion of the curves is approximately 0.0186. So, more than 99.9% of the curves have
PPT Slide
Lager Image
Thus, we can restrict the search space to the following bounds:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
Distribution of (s1,s2,s3)
PPT Slide
Lager Image
Distribution of (s1, s2, s3)
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
PPT Slide
Lager Image
99.4% of the curves exists in this bound. In this case, the overlapping factor is at least
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
therefore it is not close to any border of the bounds. The group of points has cardinality
PPT Slide
Lager Image
Example 5.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:
PPT Slide
Lager Image
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 Jungang-daero, Deagu 705-715, Korea.
e-mail: gysohn@dnue.ac.kr
References
Adleman L. , Huang M. D. (1996) Counting rational points on curves and abelian varieties over finite fields, in H. Cohen (ed.), ANTS-II, LNCS 1122 Springer-Verlag 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/s00145-004-0231-y
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, ANTS-IV, W. Bosma ed., LNCS 1838 Springer-Verlag 297 - 312
Gaudry P. , Schost E. 2004 A low-memory parallel version of Matsuo, Chao and Tsujii’s algorithm, In D. A. Buell, editor Springer-Verlag 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
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
Kedlaya K.S. (2001) Counting points on hyperelliptic curves using Monsky-Washnitzer 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 Hasse-Witt 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 Springer-Verlag Proceedings of Algorithm Number Theory Symposium-ANTS 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
Pila J. (1990) Frobenius maps of abelian varieties and finding roots of unity in finite fields Math. Comp. 55 (192) 745 - 763    DOI : 10.1090/S0025-5718-1990-1035941-X
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 one-dimensional family of genus 3 nonhyperelliptic curves over finite fields J. Appl. Math. & Informatics 30 101 - 109