6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Aug 23, 2014 at 13:28

1 Answer 1

5
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.