# 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 – baconSoda Feb 22 '17 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 Feb 22 '17 at 5:55
• I'm voting to close this question as off-topic because it is about general mathematics. – fkraiem Feb 22 '17 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 Feb 22 '17 at 11:54

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? – user13741 Feb 22 '17 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. – yyyyyyy Feb 22 '17 at 20:23