Hasse’s theorem

If we have an elliptic curve over GF(q)

y2 = x3 + ax + b

then we should expect to have roughly q points on this curve.

In a finite field, roughly half of the elements have a square root, so if the cubic x3 + ax + b takes on values that are roughly representative of the entire field GF(q), then we should get a value that has a square root roughly half the time. Each of these values for x gives us two possible values for y, so we should expect about 2 x (q/2) = q points on such a curve.

It’s actually possible to prove that that has to be the case. If we write #E(GF(q)) for the number of points on an elliptic curve over GF(q), then Hasse’s theorem tells us that this is the case. It actually tells us that we have to have

-2√q ≤ #E(GF(q)) – (q + 1) ≤ 2√q

which we can also write as

q + 1 -2√q ≤ #E(GF(q))  ≤ q + 1 + 2√q

or

(√– 1)2 ≤ #E(GF(q)) ≤ (√q + 1)2

It's even possible to generalize Hasse’s theorem to hyperelliptic curves, where it turns out that the Jacobian of a curve of genus g over GF(q) has to have about qg points. This shouldn't be too surprising. If we think of the typical element of the Jacobian as

P = (P1) + … + (Pg) – g(O)

then we should expect about q ways to pick P1, q ways to pick P2, etc, for a total of qg ways to pick P1 through Pg.

It's even possible to show that for a hyperelliptic curve of genus g, we can put the following limits (the Hasse-Weil bound) on the size of the Jacobian #J(GF(q)):

(√– 1)2g ≤ #J(GF(q)) ≤ (√q + 1)2g

This means that we can easily get a Jacobian that’s big enough to make it comparable in size to an elliptic curve group, and we can actually do this by using a value of q that’s smaller than we would need for the elliptic curve group.

On the other hand, while the best way to calculate discrete logs in an elliptic curve group is by using an algorithm like Pollard’s rho algorithm that doesn’t use the structure of the elliptic curve at all, there are ways to calculate discrete logs in the Jacobian of a hyperelliptic curve that are faster than Pollard’s rho algorithm. That doesn’t mean that hyperelliptic curves aren’t useful. It means that things just aren’t as good as we’d like them to be. Maybe that's a topic for a future post.

Leave a Reply

Your email address will not be published. Required fields are marked *