Counting points on an elliptic curve

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(p 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.