Finite field computation for moduli of special form #11
Description
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.