The number of points on an elliptic curve

An elliptic curve E over a finite field F consists of the set of points (x, y) satisfying the equation

with x and y in F. Typically in cryptography the field F is the integers mod p where p is a very large prime number.

The number of points on E is roughly the number of elements in F. So for a curve over the integers mod p, the curve has roughly p points.

The next section will give an intuitive argument for why the number of points on E should be roughly the number of elements in F. Then the next section will give a rigorous bound. Then after that we’ll work through an example.

For a prime p, half the non-zero integers mod p have a square root and half do not. The ones that do have a square root have two square roots. For example, look at the integers mod 7. The numbers 1, 2, and 4 have square roots but the numbers 3, 5, and 6 do not. Here’s a little bit of Python to verify this.

we’d find it equals p. That’s because (0, 0) is a point on the curve, and for (p − 1)/2 values of x there are two values of y, and for the remaining values of x there are no values of y.

To put it another way, if we pick a value of x at random, it will have two square roots or no square roots with roughly equal probability.

Now suppose we pick an x and random and compute x³ + ax + b. We might guess that this process scatters x values in an unbiased way, being no more likely to produce a square than a non-square. Our guess turns out to be approximately correct, though there may be a small bias in favor of squares or non-squares.

Hasse’s theorem gives a precise bound on the number of points on an elliptic curve E. It says

So if p is on the order of 2n, the number of points on E is also on the order of 2n because √p is far smaller than p. That’s all you need to know at a high level. The rest of this post will look at a particular example in full detail.

The NIST curve P-384 has been in the news lately. For this curve, the based field is integers modulo a 384-bit prime p and so the number of points on the curve is also 384-bit number. Specifically

and so we know a priori that the number of points on the curve equals 2384 plus or minus a factor less than 2193.

The number of points on the elliptic curve P-384 is known to be

n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643

We can verify that |t| is less than our a priori bound of 2√p.