Counting points on an elliptic curve

Suppose you have an elliptic curve

y^2 = x^3 + ax + b

over a finite field F_pfor 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 thep possibilities forx and fory 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^2) 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 parametersa andb. 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 ys. For each x, test determine whether

x^3 + ax + b

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

from sympy import legendre_symboldef 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 largep 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.

Ifp 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^3 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 post Counting points on an elliptic curve first appeared on John D. Cook.