[curves] How do you find a generator of an EC group?

Mike Hamburg mike at shiftleft.org
Sun Dec 11 15:58:10 PST 2016


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

> On Dec 11, 2016, at 3:12 PM, Ron Garret <ron at flownet.com> wrote:
> 
> 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
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3693 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161211/23f9069c/attachment.bin>


More information about the Curves mailing list