bounty: Algorithm to find generator points

[0xJepsen]

Bounty Description

Implement a compile-time (const fn) algorithm to find generator points on elliptic curves so that we may have arbitrary generators used as compile-time constants in traits. Generator points are used to generate the cyclic subgroup used in various cryptographic protocols.

Implementation requirements

A clear and comprehensive list of the requirements for the bounty to be considered complete.

• Implement a const function to find generator points on a given elliptic curve
  • Should accept curve parameters as input and utilize ronkathon's existing random point generation function / sqrt algorithm
• Update traits that utilize generators to use this compile-time function
• Implement proper error handling and input validation
• Documentation and tests
  • Implement tests to verify the algorithm yields generators for small groups
  • Test for groups over extension fields as well as prime fields
  • Should verify that the point generates the entire group or a subgroup of desired order
  • Create comprehensive unit tests, e.g. with well-known curves (secp256k1, Curve25519)
  • Test edge cases and invalid inputs
  • Provide clear documentation and code commenting on the algorithm's operation and usage

Bonus Features

Any additional features that will enhance the value of the bounty.

• Optimize the algorithm for efficiency:
  • Implement early termination conditions
  • Use efficient methods for scalar multiplication
  • Optimizations that may obfuscate understanding must be given as an optional feature

Resources

Elliptic Curve Cryptography: A Gentle Introduction
Standards for Efficient Cryptography (SEC) 2: Recommended Elliptic Curve Domain Parameters
Elliptic Curves for Security (RFC 7748)
Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapter 9: Generating Elliptic Curves

Criteria

Bounties will be rewarded based on the following criteria:

1. Correctness and security: A thorough review of the implementation should convince our team that they are correct and secure, with all requirements met.
2. Code clarity and quality: Succinct, easy-to-follow code with appropriate naming conventions. Utilize Rust’s type system for flexibility and security (e.g., compile-time checks where possible), and avoid external crates. Optimizations should be a lower priority than clarity, but can be included behind a feature flag as a bonus.
3. Documentation quality: Provide comprehensive README’s, Cargo docs, and inline comments where code itself is not self-explanatory. Prioritize clarity and readability.

[Autoparallel]

I think this could now be implemented since we can draw random points on the curve / have access to sqrt algorithm.

[Autoparallel]

Just to be clear, if a test of the const fn is made, the prime should be small, otherwise compilation time will explode.