Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Finite field computation for moduli of special form #11

Open
mratsim opened this issue Feb 15, 2020 · 0 comments · May be fixed by #445
Open

Finite field computation for moduli of special form #11

mratsim opened this issue Feb 15, 2020 · 0 comments · May be fixed by #445

Comments

@mratsim
Copy link
Owner

mratsim commented Feb 15, 2020

The library currently implements generic routine for odd field moduli.

This is motivated by the initial focus on pairing-friendly curves like BN (Barreto-Naerig) and BLS (Barreto-Lynn-Scott) as they are the main curves used in blockchain and for zero-knowledge proofs.
The pairing-curve modulus is not of special form (there are different tradeoffs to choose a pairing friendly modulus: the curve order must also be prime and all parameters must have low hamming weight.)

Routines for special field modulus form:

  • Mersenne Prime (2^k - 1 for example NIST prime P521 = 2^521 - 1),
  • Generalized Mersenne Prime (NIST Prime P256: 2^256 - 2^224 + 2^192 + 2^96 - 1)
  • Pseudo-Mersenne Prime (2^m - k for example Curve25519: 2^255 - 19 or secp256k1)
  • Golden Primes (φ^2 - φ - 1 with φ = 2^k for example Ed448-Goldilocks: 2^448 - 2^224 - 1)
    exist and can be implemented with compile-time specialization.

In particular, the field modulus for secp256k1 used in Bitcoin and Ethereum 1 is
2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 or 2^256 - 0x1000003D1 which is a pseudo-Mersenne prime.

mratsim added a commit that referenced this issue Jul 25, 2024
mratsim added a commit that referenced this issue Jul 25, 2024
mratsim added a commit that referenced this issue Jul 27, 2024
@mratsim mratsim linked a pull request Jul 27, 2024 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant