Suppose you have an elliptic curve

y² = x³ + ax + b

over a finite field F_p for prime p. How many points are on the curve?

Brute force

You can count the number of points on the curve by brute force, as I did here. Loop through each of the p possibilities for x and for y and count how many satisfy the curve’s equation, then add one for the point at infinity. This is the most obvious but slowest approach, taking O(p²) time.

Here’s a slight variation on the code posted before. This time, instead of passing in the function defining the equation, we’ll assume the curve is in the form above (short Weierstrass form) and pass in the parameters a and b. This will work better when we refine the code below.

def order(a, b, p):
    c = 1 # The point at infinity
    for x in range(p):
        for y in range(p):
            if (y**2 - x**3 - a*x - b) % p == 0:
                c += 1
    return c

Better algorithm

A better approach would be to loop over the x values but not the y‘s. For each x, test determine whether

x³ + ax + b

is a square mod p by computing the Legendre symbol. This takes O(log³ p) time [1], and we have to do it for p different values of x, so the run time is O(p log³ p).

from sympy import legendre_symbol

def order2(a, b, p):
    c = 1 # The point at infinity
    for x in range(p):
        r = x**3 + a*x + b
        if r % p == 0:
            c += 1 # y == 0
        elif legendre_symbol(r, p) == 1:
            c += 2
    return c

Schoof’s algorithm

There’s a more efficient algorithm, Schoof’s algorithm. It has run time O(log^k p) but I’m not clear on the value of k. I’ve seen k = 8 and k = 5. I’ve also seen k left unspecified. In any case, for very large p Schoof’s algorithm will be faster than the one above. However, Schoof’s algorithm is much more complicated, and the algorithm above is fast enough if p isn’t too large.

Comparing times

Let’s take our log to be log base 2; all logs are proportional, so this doesn’t change the big-O analysis.

If p is on the order of a million, i.e. around 2²⁰, then the brute force algorithm will have run time on the order of 2⁴⁰ and the improved algorithm will have run time on the order of 2²⁰ × 20³ ≈ 2³³. If k = 8 in Schoof’s algorithm, its runtime will be on the order of 20⁸ ≈ 2³⁴, so roughly the same as the previous algorithm.

But if p is on the order of 2²⁵⁶, as it often is in cryptography, then the three algorithms have runtimes on the order of 2⁵¹², 2²⁷⁰, and 2⁶⁴. In this case Schoof’s algorithm is expensive to run, but the others are completely unfeasible.

[1] Note that log^k means (log q)^k, not log applied k times. It’s similar to the convention for sine and cosine.

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.