GP/Pari program for Satoh-FGH elliptic curve point-counting

[Kim-Ee Yeoh <yeoh@cs.wisc.edu>]

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.
  
*/