Ask SAGE for the cardinality (that is, number of points) of an elliptic curve over a finite field and, unless you happen to have a prime field, it’ll warn you that it’s resorting to the “very, very stupid” algorithm of testing every point. Can we do better?
Background: The Zeta function
Recall that the zeta function of a curve encodes information about the number of points over an infinite family of fields. For a curve C over the field Fq This is defined as
=\exp\left(\displaystyle\sum_{r=1}^{\infty} \sharp C(\mathbb{F}_{q^r})\frac{T^r}{r}\right)\,\, \in\, \mathbb{Q}[[T]])
Thus, we can recover the cardinality over Fqr by differentiating r times with respect to T, evaluating for T=0 and dividing through by (r-1)!. This is all well and good, provided that computing the zeta function is less work than simply testing points in the field directly. For this, we need a couple of results:
Weil Conjectures for curve C over Fq
We have
=\displaystyle\frac{P(T)}{(1-T)(1-qT)})
such that
=\displaystyle\prod_{i=1}^{2g}(1-\alpha_i T) \in \mathbb{Z}[T])
with the αi algebraic integers such that |αi|=q1/2.
For such αi we then have
=q^r+1-\displaystyle\sum_{i=1}^{2g}{\alpha_i}^r)
For Fq to be a field, q=pr for some prime p. Thus we need only compute the zeta function over Fp to be able to retrieve #C(Fq) or indeed any higher #C(Fqr). The question is, therefore, whether computing the zeta function for Fp is any easier than the naive point search. With Weil’s result, we can see that knowledge of #C(Fp),…,#C(Fp2g) would, via some Taylor series trickery, be enough to determine P(T) and hence Z(T). If q is a high power of p, or we are interested in high powers of q, then this is already progress. But if q was itself a (potentially very large) prime, this approach would be useless for finding #C(Fq) since it would require knowledge of #C(Fq) (!) and at least #C(Fq2) too! Fortunately SAGE does not complain about searching over prime fields- there are a couple of algorithms - so we can restrict our attention to the original problem, that of composite q.
Elliptic Curves
Let us consider then the problem of finding #E(Fqr) where q=ps for a prime p with rs≥2 and E an Elliptic curve with coefficients from Fp. Then by the above we need only find #E(Fp) and #E(Fp2), which by brute force is rarely more work than finding #E(Fqr)=#E(Fprs). But, since the genus is 1 the various results allow us to cut down our workload still further:
Weil Conjectures for Elliptic curve E over Fp
We have
=\displaystyle\frac{P(T)}{(1-T)(1-pT)})
such that
=(1-\alpha_1 T)(1-\alpha_2 T) \in \mathbb{Z}[T])
with the αi algebraic integers such that |αi|=p1/2.
For such αi we then have
=p^r+1-({\alpha_1}^r+{\alpha_2}^r))
It follows that α1, α2 are conjugates, so over Fp we have
=\displaystyle\frac{(1-\alpha_p T)(1-\overline{\alpha_p} T)}{(1-T)(1-pT)}= \displaystyle\frac{1-(\alpha_p+\overline{\alpha_p})T+pT^2}{(1-T)(1-pT)})
=p+1-({\alpha_p}+\overline{\alpha_2}))
and
So,
)
meaning that the zeta function can be constructed from just #E(Fp) as it is simply:
=\displaystyle\frac{(1-\alpha_p T)(1-\overline{\alpha_p} T)}{(1-T)(1-pT)}= \displaystyle\frac{1-\mu T+pT^2}{(1-T)(1-pT)})
This then allows us to recover #E(Fqr)=#E(Fprs) as desired, by repeated differentiation to recover the rs‘th coefficient.
Comparison
For an elliptic curve over a finite field, using SAGE to calculate the cardinality over a field of pr elements by the “very, very stupid” algorithm rapidly gets impractical. For instance, for a given elliptic curve y2=x3+Ax+b with A,B from F5 determining the cardinality takes about 0.04s over F5; about a second over F25, around 3.7s for F125 and a tedious 19s over F625. Implementing the approach above, asking for the cardinality of three such curves over F625 is rapid enough in Maple to not register on its timer. This is despite my program lazily using brute force for the #E(F5) calculations! (The same machine, with a 2.6ghz celeron processor, was used for each run; with Maple on Windows XP and SAGE in Xubuntu Linux; SAGE timings were for CPU rather than wall time.)
Smarter Still
In fact, if we only wish to determine a single #E(Fqr) we can sidestep the construction of the zeta function by working with the αp, since
 = \sharp E(\mathbb{F}_{p^{rs}})=p^{rs}+1-({\alpha_p}^{rs}+\overline{\alpha_p}^{rs}))
Thus if αp=a+bi then
=\frac{\mu}{2})
and
So
will suffice, and again this requires only knowledge of #E(Fp).
Maple Source
The file ellCount contains Maple procedures for finding the cardinality of elliptic curves over finite fields (with coefficients from the prime subfield). Simply put, CountPoints(F,q) will find the number of points over the field of q elements for an Elliptic curve F=0. For instance, CountPoints(y^2-x^3-x-2,625) gives the cardinality of E: y2=x3+x+2 over F54 (should be 640). The route taken is to find points over F5, determine α then directly calculate from the formula in the previous section. You can retrieve the zeta function with ellZeta(F,q), or ellZetap(F,p), if you know that q is prime (which saves Maple trying to determine the prime factor). Thus the number of points over Fqr can be retrieved with getZetaCoeffr(Z,r) which performs the appropriate differentiation and scaling; this is useful to avoid having to calculate the number of solutions over the prime field, or indeed determine the prime, every time. ZetaCountPoints(F,q) behaves as CountPoints except it follows this alternative route.
