Kim-Ee Yeoh on Fri, 17 Nov 2000 15:28:20 -0600 (CST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
GP/Pari program for Satoh-FGH elliptic curve point-counting |
Dear colleagues, I have written a GP/Pari program for computing the cardinality of points on an elliptic curve over a finite field of characteristic 2 using the Satoh-FGH algorithm. It is available at http://www.cs.wisc.edu/~yeoh/nt/satoh-fgh.gp The intro section of the file summarizes what it does and gives sample usage; it is appended below for reference. I appreciate any comments on the code and hope it will be useful for research into similar point-counting algorithms. It is also hoped that this would go a small way towards filling in Pari's lack of algorithms for computing the cardinality of an elliptic curve over finite field extensions. Could Pari's developers be prevailed upon to provide this in a future release? I volunteer my assistance for this project. Sincerely, Kim-Ee Yeoh Computer Sciences Department University of Wisconsin-Madison /* satoh-fp.gp Copyright(c) 2000 Kim-Ee Yeoh (yeoh@cs.wisc.edu) This is basically a straight-forward non-optimized implementation in GP/Pari of the algorithm described in the preprint "An extension of Satoh's algorithm and its implementation" by Fouquet, Gaudry, and Harley. The only significant departure is that we perform the lift on the elliptic curve coefficient A_i directly via its modular polynomial fi(X,Y) given below instead of lifting the curve's j-invariant by phi(X,Y). This follows the suggestion given at the end of Section 4.3.1 in the cited paper. A few example curves are also provided. The first example comes directly from the small example given in Section 6.1 of the paper. The polynomial degree-11 polynomial p1=t^11+t^2+1 specifies the GF(2^11) extension field over which the curve y^2+xy=x^3+a1 is defined, where a1=Mod( Mod(1,2)*(t^4+t^2+t), p1 ). The following GP transcript shows how the main function ecpc(p,a) is used to compute #E, the cardinality of points on this curve. ? ecpc(p1,a1) lift A to prec 2 lift A to prec 4 lift A to prec 7 %1 = 2080 ? c %2 = -31 The value c is the same as that of the paper, namely, q+1-#E, where q=2^11 is the cardinality of the finite field. The second example is included to provide a comparison to the demo ECPC program found at http://www.xent.com/~harley/ that is mentioned in the paper. The constant coefficient (given as a2) of the curve corresponds to the j-invariant Mod( Mod(1,2)*t, t^120 + t^4 + t^3 + t + 1 ), which is entered in the demo program as "0x2". Suffice to say, both programs agree on the result, which of course, is not to be construed as a statement testifying to the correctness of either. There are two other examples used for testing. This code is released into the public-domain; the usual caveats apply. */