The previous post gave two examples of pairs of elliptic curves in which

#(E / F_p) = q

and

#(E / F_q) = p.

That is, the curve E, when defined over integers mod p has q elements, and when defined over the integers mod q has p elements.

Pairs

Silverman and Stange [1] call this arrangement an amicable pair. They found a small pair of amicable elliptic curves:

y² = x³ + 2

with p and q equal to 13 and 19. They give many other examples, but this one is nice because it’s small enough for hand calculations, unlike the curves mentioned in the previous post that had on the order of 2²⁵⁴ elements.

Cycles

More generally, amicable curve pairs are amicable curve cycles with cycle length 3. Silverman and Stange give this example of a cycle of length 3:

y² = x³ − 25x − 8

with (p, q, r) = (83, 79, 73). That is, the curve over F₈₃ has 79 elements, the curve over F₇₉ has 73 elements, and the curve over F₇₃ has 83 elements.

The authors show that there exist cycles of every length m ≥ 2.

Application

Why does any of this matter? Cycles of elliptic curves are useful in cryptography, specifically in zero-knowledge proofs. I hope to go into this further in some future post.

Confirmation

The curves mentioned above are small enough that we can compute the orders of the curves quickly by brute force. The following Python code confirms the claimed orders above.

def order(eqn, p):
    c = 1 # The point at infinity
    for x in range(p):
        for y in range(p):
            if eqn(x, y) % p == 0:
                c += 1
    return c

eqn = lambda x, y: y**2 - x**3 - 2
assert( order( eqn, 13) == 19 )
assert( order( eqn, 19) == 13 )

eqn = lambda x, y: y**2 - x**3 + 25*x + 8
assert( order( eqn, 83) == 79 )
assert( order( eqn, 79) == 73 )
assert( order( eqn, 73) == 83 )

Related posts

• What is an elliptic curve?
• Elliptic curve used in Bitcoin and Ethereum
• Legendre and Ethereum

[1] Joseph H. Silverman and Katherine E. Stange. Amicable pairs and aliquot cycles for elliptic curves. Experimental Mathematics, 20(3):329–357, 2011.

On New Year’s Day I posted about groups of order 2024. Are there elliptic curves of order 2024?

The Hasse-Weil theorem relates the number of points on an elliptic curve over a finite field to the number of elements of the field. Namely, an elliptic curve E over a field with q elements must have cardinality

q + 1 − t

where

|t| ≤ 2√q.

So if there is an elliptic curve with 2024 points, the curve must be over a field with roughly 2024 points.

The condition on t above is necessary for the existence of an elliptic curve of a certain size, but is it sufficient? Sorta.

The order of a finite field must be a prime power, i.e. q = p^d for some prime p. There is a theorem ([1], Theorem 13.30) that there exists a curve of the size indicated in the Hasse-Weil theorem if t ≠ 0 mod p. The theorem also lists a couple more sufficient conditions that are more complicated.

So, for example, we could take q = p = 2027 and t = 4.

Now that we know the search isn’t futile, we can search for an elliptic curve over the integers mod 2027 that has 2024 points. After a brief brute force search I found

y² = x³ + 4x + 28

over the field with 2027 elements is such a curve .

Related posts

• What is an elliptic curve?
• Efficient arithmetic on Curve25519
• Elliptic curves used in cryptography

[1] Henri Coghen and Gerhard Frey. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC. 2006.

Given a field F, finite or infinite, you can construct a projective plane over F by starting with pairs of elements of F and adding “points at infinity,” one point for each direction.

Motivation: Bézout’s theorem

A few days ago I mentioned Bézout’s theorem as an example of a simple theorem that rests on complex definitions. Bézout (1730–1783) stated that in general a curve of degree n and a curve of degree m intersect in nm points. There are a lot of special cases excluded by the phrase “in general” that go away when you state Bézout’s theorem in a sophisticated context.

To make Bézout’s theorem rigorous you have to work over an algebraically complete field (e.g. the complex numbers rather than the real numbers), you have to count intersections with multiplicity, and you have to add points at infinity, i.e. you have to work in a projective plane.

Motivation: Elliptic curves

Bézout’s theorem involves infinite field ℂ, but this post is about finite projective planes. Elliptic curves over finite fields provide a motivating example of working in finite projective planes.

This blog is served over HTTPS and so serving up its pages involves public key cryptography. And depending on what protocol your browser negotiates with my server, you may be using elliptic curve cryptography to view this page.

An elliptic curve over a finite field is not an ellipse and not a curve, at least not a curve in the sense of a continuum of points. Elliptic curves over ℝ really are curves in the usual sense, but the definition is then abstracted in a way that extends to any field, including finite fields.

Homogeneous coordinates

In order to make this idea of “points at infinity” rigorous, we have to introduce a new coordinate system. We now describe points by (equivalence classes of) triples of field elements rather than pairs of field elements. The benefit of this added complexity is that points at infinity can be handled perfectly rigorously. Often the third coordinate can be ignored, but then you pay attention to it when you need to be careful.

In homogeneous coordinates, we consider two points (x, y, z) and (x′, y′, z′) equivalent if there is a λ ≠ 0 such that

(x, y, z) = (λx′, λy′, λz′).

Also, we require that not all three coordinates are 0, i.e. (0, 0, 0) is not an element of the projective plane.

We associate a point (x, y) with the triple (x, y, 1) and all its equivalents, i.e. all triples of the form (λx, λy, λ) with λ ≠ 0.

Points at infinity

A point at infinity is simply a point with third coordinate 0.

In the post mentioning Bézout’s theorem I said in passing that the lines y = 5 and y = 6 meet at infinity. Here’s how we can make this rigorous. The line y = 5 in the finite plane is the set of points of the form (x, 5), which embed in the projective plane as

(x, 5, 1)

and these points are equivalent to the set of points

(1, 5/x, 1/x)

Now take the limit as x → ∞ and we get (1, 0, 0). We consider this addition point to be part of the line y = 5 when the line is considered part of the projective plane. You can see that the line y = 6 contains the same point. So we can be very specific about where the lines y = 5 and y = 6 intersect: they intersect at (1, 0, 0).

You can go through a similar exercise to show that the lines y = x and y = x – 57 also intersect “at infinity” but at a different point at infinity, namely at (1, 1, 0) and its equivalents.This also shows that although the lines y = 5 and y = x both go off to infinity, they “reach” infinity at different points. The former goes to the point at infinity associated with horizontal lines and the latter goes to the point at infinity associated with 45 degree lines.

Note also that parallel lines meet at one point at infinity, not two. You might want to say, for example, that y = 5 and y = 6 meet twice, once at positive infinity and once at negative infinity. You could construct a system that works that way, but that’s not now projective planes work. Since non-zero multiples of a point are equivalent, (1, 0, 0) and (-1, 0, 0) are in the same equivalence class.

See this post for practical examples of when you might choose to have one or two points at infinity depending on your application.

Finite projective planes

We can construct projective planes containing a finite number of points by repeating the construction above using a finite field F. Finding finite projective planes not isomorphic to one constructed this way is hard [1].

Let F be a finite field with q elements. Then q is necessarily either a prime or a power of a prime, though that fact isn’t needed here.

The points of the finite projective plane over F are the points of the finite plane over F, i.e. pairs of elements of F, and the additional “points at infinity.” We can say exactly what these points at infinity are and count them.

A point (x, y) is embedded in the projective plane as (x, y, 1) and all points in its equivalence class. So for starters we have at least q² points in the finite projective plane, one for each pair (x, y).

First consider the case x ≠ 0. Then (x, y, 1) is equivalent to (1, y/x, 1/x) and so without loss of generality we can assume x = 1 (the multiplicative identity of the field). So for each y, (1, y, 0) is a point at infinity. That gives us q more elements of the finite projective plane.

Next consider the case x = 0. Then (0, y, 0) is another point at infinity as long as y ≠ 0. It’s only one point, because all non-zero multiples of (0, 1, 0) are in the same equivalence class.

So all together we have q² + q + 1 points, represented by the following elements of their equivalence classes:

• (x, y, 0) for all x, y in F,
• (1, y, 0) for all y, and
• (0, 1, 0).

Related posts

• Elliptic curves used in cryptography
• Vector spaces over finite fields
• Curve 25519

[1] There are for non-isomorphic finite projective planes of order 9, i.e. planes with 9² + 9 + 1 = 91 points. And there are other examples of finite projective planes not isomorphic to planes constructed as outlined here. However, so far all such planes have the same number of points as a finite projective plane constructed as above.