# All Elliptic Curves Over Fields of Order 2 and 3

# All Elliptic Curves Over Fields of Order 2 and 3

What does characteristic 2 or 3 mean?

Join the DZone community and get the full member experience.

Join For Free**Bias comes in a variety of forms, all of them potentially damaging to the efficacy of your ML algorithm. Read how Alegion's Chief Data Scientist discusses the source of most headlines about AI failures here.**

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*_{1}*xy* + *a*_{3}*y* = *x*³ + *a*_{2}*x*² + *a*_{4}*x* + *a*_{6},

even over fields of characteristic 2 or 3.

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

*y*² = 4*x*³ + *b*_{2}*x*² + 2*b*_{4}*x* + *b*_{6}

where

*b*_{2} = *a*_{1}² + 4*a*_{4},*b*_{4} = 2*a*_{4} + *a*_{1}*a*_{3}, and*b*_{6} = *a*_{3}² + 4*a*_{6}.

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*_{2}, *b*_{4}, and *b*_{6} from above, and also

*b*_{8} = *a*_{1}²*a*_{6} + 4*a*_{2}*a*_{6} – *a*_{1}*a*_{3}*a*_{4} + *a*_{2}*a*_{3}² – *a*_{4}².

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

Δ = –*b*_{2}²*b*_{8} – 8*b*_{4}³ – 27*b*_{6}² + 9*b*_{2}*b*_{4}*b*_{6}.

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.

**Your machine learning project needs enormous amounts of training data to get to a production-ready confidence level. Get a checklist approach to assembling the combination of technology, workforce and project management skills you’ll need to prepare your own training data.**

Published at DZone with permission of John Cook , DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

## {{ parent.title || parent.header.title}}

{{ parent.tldr }}

## {{ parent.linkDescription }}

{{ parent.urlSource.name }}