# How can I find the order of the group that an elliptic curve is defined over?

I have a Weierstrass elliptic curve ($y^2=x^3+a \times x+b \mod p$)

How can I find the order of the group itself? I have seen Mathematica has a GroupOrder[] command and WolframAlpha will do it for me, but how can I do it myself, mathematically?

The modulus, $p$, will be a large prime number, say 256 bits or more.

-
The idea in SEA is that by studying the action of the Frobenius automorphism on the set of $\ell$-torsion points (defined by division polynomials) allows you to calculate the order modulo $\ell$. Do this for enough many small primes $\ell$, take into account the Hasse-Weil bound, and you are done. The details of the theory (the Elkies' bit in particular) run a bit deep. – Jyrki Lahtonen Aug 23 '14 at 13:28

## 1 Answer

The number of points on the curve $|E({\mathbb F}_p)|$ is defined as $|E({\mathbb F}_p)|=p+1-t$ where $t$ is the so called trace of Frobenius. Using Hasse's theorem one can bound $t$ as $|t| \leq 2\sqrt p$, which gives you an estimation for the number of points for $E({\mathbb F}_p)$.

Now you could use a naive algorithm and simply run through all elements of ${\mathbb F}_p$ and determine whether they satisfy the curve equation to count the points, which however requires exponential time.

Luckily, you can use polynomial time point counting algorithms, such as Schoof or SEA, which allows you to efficiently determine the number of points on the curve.

For cryptographic use you will typically require a prime order subgroup $G$ of $|E({\mathbb F}_p)|$ such that the value $h = \frac{|E({\mathbb F}_p)|}{ord(G)}$, the so called cofactor, is a small integer (typically $\leq 4$).

-