Discussion:
How do you find a generator of an EC group?
Ron Garret
2016-12-11 23:12:57 UTC
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?

Thanks,
rg
Mike Hamburg
2016-12-11 23:58:10 UTC
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.

â Mike
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?
Thanks,
rg
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Ben Smith
2016-12-12 09:45:54 UTC
Post by Mike Hamburg
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.
It's worth noting that multiplying-by-the-cofactor is something that
you'll definitely need to do if you have larger cofactors, like if
you're in a pairing-based situation, because otherwise the probability
that your randomly generated point is even in the subgroup is
somewhere between "annoyingly small" and "negligible".

ben
--
You know we all became mathematicians for the same reason: we were lazy.
--Max Rosenlicht