Discussion:
How do you find a generator of an EC group?
(too old to reply)
Ron Garret
2016-12-11 23:12:57 UTC
Permalink
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
Permalink
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
Permalink
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
Loading...