Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have a Weierstrass elliptic curve (y^2=x^3+a*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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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