This is definitely the most straightforward way find the generator of a subgroup, except that you want qP = 0. If you want a NUMS property, you could take the first generator with x-coordinate greater than or equal to some hash value, or similar.
An alternative method is to obtain a point on the curve (either by brute force or with SWU or Elligator), and then multiply it by the cofactor h = #E/q, and then check that itâs not 0.
Iâm not sure what reference you would cite for either of these. Iâm pretty sure the Curve25519 spec is the least generator, as is the X448 generator. Many other specs make similar choices.
SLSIA. Iâm working on an introductory survey of ECC (the one suggested in the âClimbing the elliptic learning curveâ thread a few weeks back) and Iâm making good progress but Iâm stuck on this issue. I have, of course, found Shoofâs algorithm for counting curve points, but that only gets you so far. With that as a baseline, I can kind of imagine an algorithm for finding a base point: compute the number of curve points, factor the result, pick the largest prime factor q, and then find a generator by brute-force search for a point P such that qP=-P. Is that anywhere close to being the right answer? Is there a reference I can cite?
Curves mailing list