Maybe the best thing to be said is this is a good example of what *not* to do. This is a very naive way to construct field extensions and I suspect it's a very slow way to compute anything. Doing things in assembler would improve things by an order of magnitude, but it'd still be too slow to be practical.

As Blake et.al. point out, "computing modular functions is a challenge". The efficiency gained is several orders of magnitude over the "naive" Schoof's algorithm, so anyone going into the realm of counting the number of points on an arbitrary elliptic curve should figure it out.

The file field2n.h contain prototypes and creates the lowest level storage data sizes. The fundamental data type is FIELD2N which is basicly an array of unsigned longs.

The file eliptic.h contains the definition of CURVE, but it's not used much.

The file multipoly.h contains the definitions of multivariate polynomials. This is where life begins to get hairy.

The file ring.c contains the low level math. This is the "all ones polynomial" fields which are the same thing as Type I ONB, but simpler since it's done as a polynomial basis (we can just shift and add, there's no bit scrambling).

The file multi_mem.c does the memory management. This is probably inefficient and is the core of what not to do. I ran into serious problems allocating huge chunks of space with Linux, so doing it all myself bypassed bugs I didn't understand.

The file multi_ring.c deals with multivariate polynomials. It computes add, multiply, divide, gcd as basic multivariate polynomials (which are polynomials of polynomials). It also computes the division polynomials for a particular curve as well as x^q modulo one of those division polynomials. This is the guts required for Schoof's algorithm. Call xqmodf() to find eigen values of the frobenius and twice to find eigen values of the trace. See Menezes "Elliptic curve cryptosystems" chapter 7. This is the "old" way to do things, see Lercier for better ones.

the file eigen_search.c tests the above code. This is pretty incomplete in terms of solving Schoof's algorithm, but it contains several checks to ensure things were working. There are several multivariate routines designed to solve for the sign of the eigen value using the curve equation to the 2^m power, but it's not clear this worked. As is, it only checks how much time it takes to find x^q modulo some very large polynomials (field size 148, prime up to 31 or 37). These are ~500 degree polynomials which take up about 20*500 bytes of storage per number. Squaring these 148 times takes about 10 minutes on a 400 MHz celeron.

counting points via complex multiplication is trivial compared to this. There are plenty of good CM curves. I think I'll stick with that! If you want some help with Schoof's algorithm, here's an example of the hard way to do things. Don't do this, do better!