All Elliptic Curves Over Fields of Order 2 and 3

Introductions to elliptic curves often start by saying that elliptic curves have the form

y² = x³ + ax + b.

where 4 a³ + 27 b ² ≠ 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 2 or 3."

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² + a₁xy + a₃y = x³ + a₂x² + a₄x + a₆,

even over fields of characteristic 2 or 3.

When the characteristic of the field is not 2, this can be simplified to

y² = 4x³ + b₂x² + 2b₄x + b₆

where

b₂ = a₁² + 4a₄,
b₄ = 2a₄ + a₁a₃, and
b₆ = a₃² + 4a₆.

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 4 a³ + 27 b², but it's more complicated for characteristic 2 and 3. To define the discriminant, we'll need to use b₂, b₄, and b₆ from above, and also

b₈ = a₁²a₆ + 4a₂a₆ – a₁a₃a₄ + a₂a₃² – a₄².

Now we can define the discriminant Δ in terms of all the b 's.

Δ = –b₂²b₈ – 8b₄³ – 27b₆² + 9b₂b₄b₆.

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 contain 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.

[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.