Advanced
OMPUTING THE NUMBER OF POINTS ON GENUS 3 HYPERELLIPTIC CURVES OF TYPE Y2 = X7 + aX OVER FINITE PRIME FIELDS†
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
Copyright © 2014, Korean Society of Computational and Applied Mathematics
  • Received : June 14, 2013
  • Accepted : August 26, 2013
  • Published : January 28, 2014
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 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.
Keywords
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 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
PPT Slide
Lager Image
with p ≡ 1 modulo 12. Furthermore, we present additional computational results using our algorithm.
2. Basic Facts on Hyperelliptic Curves
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 . 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 JC (
PPT Slide
Lager Image
) can be uniquely represented by a pair of polynomials ⟨ u ( x ), v ( x )⟩, where u ( x ) = Π i ( x xi ) is monic and v ( x ) is unique polynomial such that deg v ( x ) < deg u ( x ), v ( xP ) = yP for all P = ( xP , yP ) ∈ C (
PPT Slide
Lager Image
) 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 JC (
PPT Slide
Lager Image
) .
We consider the hyperelliptic curves of genus 3 defined over finite fields
PPT Slide
Lager Image
. The characteristic polynomial χ q ( t ) of the q -th power Frobenius endomorphism of JC is given as follows:
PPT Slide
Lager Image
where si ∈ ℤ. We also know that ♯ JC (
PPT Slide
Lager Image
) = χ q (1). i.e.,
PPT Slide
Lager Image
Let Mr = ( qr +1)− Nr , where Nr is the number of
PPT Slide
Lager Image
points on C for r = 1, 2, 3. Then, we have
PPT Slide
Lager Image
The following is a well-known inequality, the Hasse-Weil bound, that bounds ♯ JC (
PPT Slide
Lager Image
):
PPT Slide
Lager Image
Then, we have
PPT Slide
Lager Image
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
  • (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 p of ♯ JC
PPT Slide
Lager Image
). 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 ci the coefficient of xi in the polynomial f ( x ) (p−1)/2 . Then the Hasse-Witt matrix is given by
PPT Slide
Lager Image
In [8] , Manin showed that this matrix is related to the characteristic polynomial of the Frobenius endomorphism modulo p . For a matrix H = ( aij ), let H (p) denote the elements raised to the power p , i.e.,
PPT Slide
Lager Image
Then, we have the following theorem.
Theorem 3.2. Let C be a curve of genus g defined over a finite field
PPT Slide
Lager Image
Let H be the Hasse-Witt matrix of C and let
PPT Slide
Lager Image
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 ,
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 C : y 2 = x 7 + ax over finite fields
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 :
PPT Slide
Lager Image
where
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 :
  • 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),
Proof . First, we compute the entities cip−j of the Hasse-Witt matrix H of the curve C . From Theorem 3.1, the entities cip−j are computed by an integer k , 0 ≤ k ≤ ( p − 1)/2, for ip − j = p − 1 + 3 k from
PPT Slide
Lager Image
Since the characteristic p with p ≡ 1 (mod 12), the Hasse-Witt matrix is
PPT Slide
Lager Image
Then we have that
PPT Slide
Lager Image
On the other hand, the each si of χ( t ) has the following congruence modulo p ;
  • 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).
Let p = 12 f + 1 be a prime. Then, since ( p − 1)/2 + 6 k = p − 1 for cp −1 , we have k = ( p − 1)/12 = f and
PPT Slide
Lager Image
For c2p −2 , since ( p − 1)/2 + 6 k = 2 p − 2, we have k = (3 p − 3)/12 = 3 f and
PPT Slide
Lager Image
For c3p −3 , since ( p − 1)/2 + 6 k = 3 p − 3, we have k = (5 p − 5)/12 = 5 f and
PPT Slide
Lager Image
Hence, since
PPT Slide
Lager Image
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
PPT Slide
Lager Image
where f ( x ) = x 7 + ax. If f ( x ) splits completely over
PPT Slide
Lager Image
( i.e.,a (p−1)/6 = 1), then 64 divide JC (
PPT Slide
Lager Image
). If f ( x ) splits into four factors over
PPT Slide
Lager Image
( i.e, a (p−1)/3 = 1), then 8 divide JC (
PPT Slide
Lager Image
). 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 JC (
PPT Slide
Lager Image
).
Proof . Since 12 divide p −1, there are exists a primitive 12-th root of unity, ζ 12 , in
PPT Slide
Lager Image
. The points on C with vanishing y -coordinates correspond to (1− ζ 12 )-torsion points of the Jacobian. If f ( x ) splits completely over
PPT Slide
Lager Image
(i.e., a (p−1)/6 = 1), then JC [1 − ζ 12 ] is defined over
PPT Slide
Lager Image
. Hence, (ℤ/2ℤ) 6 is a subgroup in JC (
PPT Slide
Lager Image
) and 64 divide ♯ JC (
PPT Slide
Lager Image
). Moreover precisely, in this case, there exists an element b
PPT Slide
Lager Image
such that a = b 6 . Then we have
PPT Slide
Lager Image
If f ( x ) splits four factors over
PPT Slide
Lager Image
(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 JC (
PPT Slide
Lager Image
) and 8 divides ♯ JC (
PPT Slide
Lager Image
). Moreover, in this case, there exists an element b
PPT Slide
Lager Image
such that a = b 3 . Then we have
PPT Slide
Lager Image
Otherwise, JC (
PPT Slide
Lager Image
) contains one non-trivial (1− ζ 12 )-torsion point. Moreover, in this case, there exists an element b
PPT Slide
Lager Image
such that a = b 2 . Then we have that
PPT Slide
Lager Image
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
PPT Slide
Lager Image
with p ≡ 1 (mod 12), p = A 2 + B 2 . Then the characteristic polynomial χ( t ) is as follows :
  • 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.
where A ≡ 1, 2 (mod 3) and B ≡ 0 (mod 3) .
  • 3.If a(p−1)/12= 1,then
  • 4.If a(p−1)/12= -1,then
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
m is satisfied in −9 ≤ m ≤ 3. Now we determine the value m . We know that χ( t ) splits into three factors hi ( 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
PPT Slide
Lager Image
its complex conjugate. We denote
PPT Slide
Lager Image
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
PPT Slide
Lager Image
we thus have m = 3.
We denote
PPT Slide
Lager Image
Since
PPT Slide
Lager Image
we have m′ = 12 A . Then the characteristic polynomial χ( t ) is
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
. 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 ♯ JC (
PPT Slide
Lager Image
) ≡ 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
where c 3 is an integer for
PPT Slide
Lager Image
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 (
PPT Slide
Lager Image
) = p +1. Hence s 1 = 0. Since
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Since ♯ JC (
PPT Slide
Lager Image
) ≡ 0 (mod 2),
PPT Slide
Lager Image
Then we have c 3 ≡ 0 (mod 2) for
PPT Slide
Lager Image
from Theorem 2.1 . Hence we have conclusion.
5. Implementation details
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 Li ( Ui ) the lower (upper) bound of si for i = 1, 2, 3 in (3). According to Theorem 3.2, we denote that for i = 1, 2, 3
PPT Slide
Lager Image
with
PPT Slide
Lager Image
Then each ti is bounded by
PPT Slide
Lager Image
We substitute (2) into (1) 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 ♯ JC (
PPT Slide
Lager Image
). Assume that N is a positive integer(to be specified). Let u and v be integers such that
PPT Slide
Lager Image
Then, the boundary for v is
PPT Slide
Lager Image
By substituting (4) into (3), we have
PPT Slide
Lager Image
Hence, ♯ JC (
PPT Slide
Lager Image
) can be computed by finding the 4-tuple ( t 1 , t 2 , u , v ) such that
PPT Slide
Lager Image
for all D JC (
PPT Slide
Lager Image
) 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
in (2) (see [10] ). Then we can be easily calculated the binomial coefficients. Moreover, since
PPT Slide
Lager Image
if p > 37, then s 1 is uniquely determined by sum of cp −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
PPT Slide
Lager Image
For the v , there are
PPT Slide
Lager Image
choices, and for u there are N choices. We also set the N as
PPT Slide
Lager Image
In (2) of Theorem 4.6, the s 1 and s 2 are easily determined. We similarly set the N as
PPT Slide
Lager Image
Therefore, the expected running time of our algorithm is
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.
Example 6.1. Let p = 12970096625951449 be a 54-bit prime and let curve C over
PPT Slide
Lager Image
be defined by
PPT Slide
Lager Image
We compute the group order of the Jacobian:
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Implementation results
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 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
PPT Slide
Lager Image
with p ≡ 1 modulo 12. Finally, we verified usefulness of the our algorithm by the simple examples.
BIO
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
References
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