# How to find the order of a generator on an elliptic curve?

I was looking out to find optimum generator for an elliptic curve $E$ over a prime field $\mathbb F_p$. I found the following algorithm:

1. Choose random point $P$ on the curve.
2. Find the order of a generator $\ell$.
3. Calculate the number of points $n=\#E(\mathbb F_p)$.
4. Calculate the cofactor $h=n/\ell$.
5. Calculate a generator as $G=[h]P$.

Here I can find $n=\#E(\mathbb F_p)$ using Schoof's algorithm. I need to find $\ell$. How is that possible? How can I find the order of a generator/base point of an elliptic curve defined over a prime field?

• This might help: how to find a primitive point on an elliptic curve Commented Feb 22, 2017 at 4:21
• For cryptographic purposes, the group order should be prime. This means, you should use the subgroup of E with the biggest prime order. That implies that your randomly chosen point P may not be optimal. I would suggest the following algorithm: First factor #E and choose the biggest prime factor q. Then choose random points P until one of it satisfies P*q = 0.
– user27950
Commented Feb 22, 2017 at 5:55
• I'm voting to close this question as off-topic because it is about general mathematics. Commented Feb 22, 2017 at 6:34
• @fkraiem: As a mathematician, you can surely give me an exact definition what question refers to cryptography and what to general mathematics ;-)
– user27950
Commented Feb 22, 2017 at 11:54
• This question is similar to: How to find out what the order of the base point of the elliptic curve is?. If you believe it’s different, please edit the question, make it clear how it’s different and/or how the answers on that question are not helpful for your problem. Commented Jul 7 at 14:48

Due to the Pohlig-Hellman algorithm, the hardness of discrete logarithms is dominated by the largest prime factor $$\ell$$ of the group order $$n$$. In particular, one typically works in a subgroup of order $$\ell$$ of the curve group, since the additional factors $$h$$ in a generator's order would not significantly contribute to security.

In that, note that $$\ell$$ depends on the group order $$n$$: You cannot just decide for some order $$\ell$$ and then find a point $$G$$ of that order on an arbitrary fixed curve, since it general such a point will not exist. (However, there is the complex multiplication method, which generates a new curve of given order.) Therefore, steps 2 and 3 of the algorithm given in the question must be swapped: You first compute the curve group order $$n$$, factor it, and determine $$\ell$$ from the factorization. (And if $$\ell$$ is too small, you should start over with a new curve. For example, Curve25519 has cofactor $$h=8$$.)

Other than that, the algorithm is fine, except that you might want to check whether $$G=\infty$$ and start over in that case. However, this only happens with probability $$1/\ell$$, so it should never occur in practice for cryptographically-sized curves. (Moreover, you would compute and factor the group order only once and find a good $$P$$ afterwards, but this does not impact the expected runtime much as $$P$$ usually is good at the first try.)

Thus, we have the following algorithm:

1. Compute the curve order $$n=\#E(\mathbb F_p)$$.
2. Factor $$n$$ to determine its largest prime factor $$\ell$$. (Note that you do not need to fully factor $$n$$: If the remainder after removing a few "small" divisors is not prime, the cofactor is going to be too big anyway.)
3. Compute the cofactor $$h=n/\ell$$. If $$h$$ is "too big", start over with a new curve.
4. Choose a random point $$P\in E(\mathbb F_p)$$ and let $$G=[h]P$$.
5. If $$G$$ is the point at infinity, go back to choosing a new $$P$$. Else, $$G$$ has order $$\ell$$.
• Doesn't Pohlig-Hellman only apply to multiplicative groups? Commented Feb 22, 2017 at 19:15
• @user13741 No, Wikipedia is wrong in this respect (and it has long been on my to-do list to improve that article). The algorithm applies to any finite abelian group, as long as a factorization of the group order is known. Commented Feb 22, 2017 at 20:23
• @yyyyyyy Can you point me in a direction on how to compute curve order n? Commented Aug 7, 2022 at 17:22
• @RomeoSierra Does this help? Commented Aug 7, 2022 at 22:27
• @yyyyyyy Let me check... Thanks a bunch! Commented Aug 8, 2022 at 4:10