Introductions to elliptic curves often start by saying that elliptic curves have the form
y² = x³ + ax + b.
where 4a³ + 27b² ≠ 0. Then later they say “except over fields of characteristic 2 or 3.”
What does characteristic 2 or 3 mean? The order of a finite field is the number of elements it has. The order is always a prime or a prime power. The characteristic is that prime. So another way to phrase the exception above is to say “except over fields of order 2n or 3n.”
If we’re looking at fields not just of characteristic 2 or 3, but order 2 or 3, there can’t be that many of them. Why not just list them? That’s what I plan to do here.
General form of elliptic curves
All elliptic curves over a finite field have the form
y² + a1xy + a3y = x³ + a2x² + a4x + a6,
even over fields of characteristic 2 or 3.
When the characteristic of the field is not 2, this can be simplified to
y² = 4x³ + b2x² + 2b4x + b6
where
b2 = a1² + 4a4,
b4 = 2a4 + a1a3, and
b6 = a3² + 4a6.
When the characteristic is at least 5, the form can be simplified further to the one at the top with just two parameters.
General form of the discriminant
The discriminant of an elliptic curve is something like the discriminant of a quadratic equation. You have an elliptic curve if and only if it is not zero. For curves of characteristic at least five, the condition is 4a³ + 27b², but it’s more complicated for characteristic 2 and 3. To define the discriminant, we’ll need to use b2, b4, and b6 from above, and also
b8 = a1²a6 + 4a2a6 – a1a3a4 + a2a3² − a4².
Now we can define the discriminant Δ in terms of all the b‘s.
Δ = −b2²b8 − 8b4³ − 27b6² + 9b2b4b6.
See Handbook of Finite Fields page 423.
Enumerating coefficients
Now we can enumerate which parameter combinations yield elliptic curves with the following Python code.
from itertools import product
def discriminant(a1, a2, a3, a4, a6):
b2 = a1**2 + 4*a4
b4 = 2*a4 + a1*a3
b6 = a3**2 + 4*a6
b8 = a1**2*a6 + 4*a2*a6 - a1*a3*a4 + a2*a3**2 - a4**2
delta = -b2**2*b8 - 8*b4**3 - 27*b6**2 + 9*b2*b4*b6
return delta
p = 2
r = range(p)
for (a1, a2, a3, a4, a6) in product(r,r,r,r,r):
if discriminant(a1, a2, a3, a4, a6)%p != 0:
print(a1, a2, a3, a4, a6)
The code above does return the values of the a‘s that yield an elliptic curve, but in some sense it returns too many. For example, there are 32 possible combinations of the a‘s when working over GF(2), the field with two elements, and 16 of these lead to elliptic curves. But some of these must lead to the same set of points because there are only 4 possible (x, y) affine points on the curve, plus the point at infinity.
Now we get into a subtle question: when are two elliptic curves the same? Can two elliptic curves have the same set of points and yet be algebraically different? Sometimes, but not usually. Lenstra and Pila [1] proved that two elliptic curves can be equal as sets but not equal as groups if and only if the curve has 5 points and the field has characteristic 2. [2]
Lenstra and Pila give the example of the two equations
y² + y = x³ + x²
and
y² + y = x³ + x
over GF(2). Both determine the same set of points, but the two curves are algebraically different because (0,0) + (0,0) equals (1,1) on the first curve and (1,0) on the second.
Enumerating points on curves
The following Python code will enumerate the set of points on a given curve.
def on_curve(x, y, a1, a2, a3, a4, a6, p):
left = y**2 + a1*x*y + a3*y
right = x**3 + a2*x**2 + a4*x + a6
return (left - right)%p == 0
def affine_points(a1, a2, a3, a4, a6, p):
pts = set()
for x in range(p):
for y in range(p):
if on_curve(x, y, a1, a2, a3, a4, a6, p):
pts.add((x,y))
return pts
We can use this code, along with Lenstra and Pila’s result, to enumerate all elliptic curves of small order.
All elliptic curves over GF(2)
Now we can list all the elliptic curves over the field with two elements.
Curves of order 5
The two curves in the example of Lendstra and Pila are the only ones over GF(2) with five points. So the two curves of order 5 over GF(2) are
y² + y = x³ + x²
y² + y = x³ + x.
They determine the same set of points but are algebraically different.
Curves of order 4
There are four curves of order 4.They contain different sets of points, i.e. each omits a different one of the four possible affine points.
y² + xy = x³ + 1
y² + xy = x³ + x² + x
y² + xy + y = x³ + x²
y² + xy + y = x³ + x² + x
Curves of order 3
There are two distinct curves of order 3, each determined by two equations.
The first curve is determined by either of
y² + y = x³
y² + y = x³ + x² + x
and the second by either of
y² + xy + y = x³ + 1
y² + y = x³ + x² + x + 1
Curves of order 2
There are 4 curves of order two; each contains a different affine point.
y² + xy + y = x³ + 1
y² + xy + y = x³ + x + 1
y² + xy = x³ + x² + 1
y² + xy = x³ + x² + x
Curves of order 1
These are curves containing only the point at infinity
y² + y = x³ + x + 1
y² + y = x³ + x² + 1
There are no affine points because the left side is always 0 and the right side is always 1 for x and y in {0, 1}.
All elliptic curves over GF(3)
There are too many elliptic curves over GF(3) to explore as thoroughly as we did with GF(2) above, but I can report the following results that are obtainable using the Python code above.
An elliptic curve over GF(3) contains between 1 and 7 points. Here are the number of parameter combinations that lead to each number of points.
1: 9
2: 22
3: 26
4: 15
5: 26
6: 22
7: 9
Obviously there’s only one curve with one point, the point at infinity, so the nine coefficient combinations that lead to a curve of order 1 determine the same curve.
There are 9 distinct curves of order 2 and 12 distinct curves of order 3. All the curves of orders 4, 5, 6, and 7 are distinct.
Related posts
[1] H. W. Lenstra, Jr and J. Pila. Does the set of points of an elliptic curve determine the group? Computational Algebra and Number Theory, 111-118.
[2] We are not considering isomorphism classes here. If two curves have a different set of points, or the same set of points but different group properties, we’re considering them different.
