Modulo Errors

A less very, very stupid way of counting points on elliptic curves

February 9th, 2007

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 F_q This is defined as

$Z(T)=\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 F_q^r 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 F_q
We have
$Z(T)=\displaystyle\frac{P(T)}{(1-T)(1-qT)}$

such that

$P(T)=\displaystyle\prod_{i=1}^{2g}(1-\alpha_i T) \in \mathbb{Z}[T]$

with the α_i algebraic integers such that |α_i|=q^1/2.

For such α_i we then have

$\sharp C(\mathbb{F}_{q^r})=q^r+1-\displaystyle\sum_{i=1}^{2g}{\alpha_i}^r$

For F_q to be a field, q=p^r for some prime p. Thus we need only compute the zeta function over F_p to be able to retrieve #C(F_q) or indeed any higher #C(F_q^r). The question is, therefore, whether computing the zeta function for F_p is any easier than the naive point search. With Weil’s result, we can see that knowledge of #C(F_p),…,#C(F_p^2g) 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(F_q) since it would require knowledge of #C(F_q) (!) and at least #C(F_q²) 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(F_q^r) where q=p^s for a prime p with rs≥2 and E an Elliptic curve with coefficients from F_p. Then by the above we need only find #E(F_p) and #E(F_p²), which by brute force is rarely more work than finding #E(F_q^r)=#E(F_p^rs). 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 F_p

We have

$Z(T)=\displaystyle\frac{P(T)}{(1-T)(1-pT)}$

such that

$P(T)=(1-\alpha_1 T)(1-\alpha_2 T) \in \mathbb{Z}[T]$

with the α_i algebraic integers such that |α_i|=p^1/2.

For such α_i we then have

$\sharp E(\mathbb{F}_{p^r})=p^r+1-({\alpha_1}^r+{\alpha_2}^r)$

It follows that α₁, α₂ are conjugates, so over F_p we have

$Z(T)=\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)}$

$\sharp E(\mathbb{F}_{p})=p+1-({\alpha_p}+\overline{\alpha_2})$

and

$|\alpha_p|=\sqrt{p}$

So,

$\mu:=\alpha_p+\overline{\alpha_p}=p+1- \sharp E(\mathbb{F}_{p})$

meaning that the zeta function can be constructed from just #E(F_p) as it is simply:

$Z(T)=\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(F_q^r)=#E(F_p^rs) 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 p^r elements by the “very, very stupid” algorithm rapidly gets impractical. For instance, for a given elliptic curve y²=x³+Ax+b with A,B from F₅ determining the cardinality takes about 0.04s over F₅; about a second over F₂₅, around 3.7s for F₁₂₅ and a tedious 19s over F₆₂₅. Implementing the approach above, asking for the cardinality of three such curves over F₆₂₅ is rapid enough in Maple to not register on its timer. This is despite my program lazily using brute force for the #E(F₅) 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(F_q^r) we can sidestep the construction of the zeta function by working with the α_p, since

$\sharp E(\mathbb{F}_{q^r}) = \sharp E(\mathbb{F}_{p^{rs}})=p^{rs}+1-({\alpha_p}^{rs}+\overline{\alpha_p}^{rs})$

Thus if α_p=a+bi then

$a=\frac{1}{2}(\alpha_p+\overline{\alpha_p})=\frac{\mu}{2}$

and

$a^2+b^2=p$

$\alpha_p=\frac{\mu}{2}+ i\sqrt{p-\mu^2/4}$

will suffice, and again this requires only knowledge of #E(F_p).

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: y²=x³+x+2 over F_5⁴ (should be 640). The route taken is to find points over F₅, 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 F_q^r 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.

This entry was posted on Friday, February 9th, 2007 at 11:40 am and is filed under Algebra, Algebraic Geometry, Maple, Number Theory, PhD, SAGE.

One Response to “A less very, very stupid way of counting points on elliptic curves”

John Cremona Says:
February 21st, 2008 at 5:53 pm
Hello Graeme. You’ll find that in Sage 2.10.2, which will be released very soon, this has been fixed in an intelligent way.

Author

Categories

Recent Comments

Archives

Maths/Sci Blogs

Mod Errors Feeds