Prime Fields

Longfellow carries five concrete prime fields — one small testing field (fp_p128) and four NIST-size curves (fp_p256, fp_p256k1, fp_p384, fp_p521) — plus two extension-field constructions (Fp2, Fp24_6) used in pairing-heavy code paths. Every field is a specialization of the same FpGeneric template; only the Montgomery reduction step differs between them.

When to reach for it

You are starting a new statement and need to pick a field — this page has the decision list.
You are computing off-circuit (preparing a witness, decoding a signature) and need the field’s arithmetic, sampling, or byte-serialization API.
You hit a Montgomery-form gotcha (to_bytes_field returning something that is not what you expected) and need to see where the representation boundary is.

Design overview

Every prime field in Longfellow shares the same shape:

FpGeneric<W64, optimized_mul, OPS> does all the work. W64 sets the limb count, OPS is a plain struct whose only job is to hold the modulus constants and a specialized reduction_step(), and optimized_mul toggles a zero/one fast path on the multiplication loop. fp.h provides the default generic reduction step; the five specialized headers each supply a faster one tuned to their modulus shape.

Montgomery representation. All arithmetic runs in Montgomery form: the stored limbs represent a · R \bmod p where R = 2^{64·W64}. Addition and subtraction work unchanged, but multiplication is mul_Montgomery(a, b) = (a · b · R^{-1}) \bmod p, which keeps intermediate values reduced without a separate division step. The constructor precomputes rsquare_ = R^2 \bmod p so to_montgomery(x) = mul(x, rsquare_) converts external inputs. External-facing APIs (of_bytes_field, to_bytes_field, of_untrusted_string, of_scalar) always convert in and out, so callers only see standard residues.

Unsaturated limbs are not used. Every limb is full 64-bit; reductions rely on the platform adc/sbb intrinsics in sysdep.h rather than extra headroom.

Extension fields share the same skeleton. Fp2<Field> stores a pair (re, im) and does Karatsuba multiplication over the base field; Fp24_6 stores six base-field coefficients of a polynomial mod x^6 - β and uses schoolbook multiplication with a sextic reduction step. Both reuse their base field’s arithmetic for the expensive part.

API surface

Generic interface (`FpGeneric`)

All five concrete fields and the two extensions expose the same core surface.

Field::Elt — a field element in Montgomery form. Value-typed; safe to copy.
Elt Field::zero() / Elt Field::one() — the additive and multiplicative identities.
Elt Field::of_scalar(uint64_t) — embed a small scalar (Montgomery-converted).
std::optional<Elt> Field::of_bytes_field(const uint8_t bytes[Field::kBytes]) — little-endian byte deserializer; returns nullopt if the input is ≥ the modulus.
void Field::to_bytes_field(uint8_t out[Field::kBytes], const Elt&) — Montgomery → integer → little-endian bytes.
std::optional<Elt> Field::of_untrusted_string(const char*) — decimal or 0x-hex parser with bounds checking.
Elt Field::sample(RandomEngine&) — uniform random field element via rejection sampling tight to the exact bit width.

The arithmetic exists in two shapes, imperative in-place and functional:


Elt a, b;
F.add(a, b);            // a += b
F.mul(a, b);            // a *= b
Elt c = F.addf(a, b);   // c = a + b
Elt d = F.invertf(a);   // d = a^-1

invert uses constant-time binary GCD. neg is implemented as sub(zero(), x) and is also constant-time.

The five prime fields

Each specialization is a one-liner typedef pointing at FpGeneric with a reduction OPS struct that knows the modulus’s shape.

Field	Modulus	`W64`	Used for
`Fp128`	`2^128 - 2^108 + 1`	2	Tests; has high-order roots of unity for NTT
`Fp256` (P-256)	`2^256 - 2^224 + 2^192 + 2^96 - 1`	4	ECDSA over `secp256r1`
`Fp256k1`	`2^256 - 2^32 - 977`	4	ECDSA over `secp256k1`
`Fp384` (P-384)	`2^384 - 2^128 - 2^96 + 2^32 - 1`	6	NIST Suite B signatures
`Fp521` (P-521)	`2^521 - 1`	9	Mersenne-prime high-security ECC

Fp256k1 defaults optimized_mul to true, which short-circuits mul(a, b) when either operand is zero or one. That path is hit often enough in the secp256k1 scalar-multiplication inner loops to be worth the branch. All five prime-field types accept optimized_mul as a template parameter; the other four default it to false.

The specialized reduction_step() in each file exploits the modulus’s polynomial shape: for Fp256 it decomposes u · p into sparse shifts of the carry, for Fp521 it rotates a single 9-limb carry, and so on. The generic FpReduce::reduction_step() in fp.h is only used when none of the specialized headers apply.

`Fp2` — quadratic extension

Fp2<Base> builds Base[i] / (i^2 + 1) (with nonresidue_is_mone = true, the default) or a user-chosen nonresidue. Elements are pairs (re, im) and multiplication uses three base-field multiplies rather than four (Karatsuba):

Fp2::Elt::re, im — base-field components (public members).
add, sub, mul(Elt, Elt), mul(Elt, Scalar) — expected.
conj(Elt&) — in-place conjugation (negate im).
invert(Elt&) — one base-field inverse via conj(x) / (re^2 + im^2).
of_bytes_field and to_bytes_field — concatenated base-field bytes, kBytes = 2 · Base::kBytes.

Fp2 is non-copyable (deleted copy constructor and copy-assignment operator) because it holds a reference to its base field and precomputes constants based on it.

`Fp24_6` — sextic extension

Fp24_6 builds Fp24[x] / (x^6 - β) where β is supplied as a uint32_t constructor parameter (explicit Fp24_6(const BaseField& F, const uint32_t beta)), not a constant tied to any specific curve. Elements are 6-tuples of base-field coefficients:

Fp24_6::Elt::e[6] — coefficients of the polynomial in x.
add, sub — component-wise.
mul(Elt, Elt) — schoolbook 6×6 product, then reduce indices 0–4 via for (size_t i = 0; i < 5; ++i) m[i] += m[i+6] · β (5 iterations, not 6).
invert(Elt&) — Gaussian elimination on the 6×6 β-circulant matrix; the subfield case (e[1..5] == 0) shortcuts to a single base-field inverse.

Fp24_6 is non-copyable (it holds a reference to its base field and precomputes constants tied to it) and is used by the pairing code paths in Longfellow’s benchmarking targets rather than by the main ZK prover.

Serialization conventions

Every field page pins the same contract:

In: of_bytes_field takes kBytes little-endian bytes, returns nullopt if the integer is ≥ the modulus.
Out: to_bytes_field emits kBytes little-endian bytes of the standard, non-Montgomery representative.
Length constants: Field::kBytes and Field::kBits are compile-time; use them in preference to hardcoding limb counts.

See it used

longfellow-zk/lib/algebra/fp_test.cc — fp_test.cc
longfellow-zk/lib/algebra/fp2_test.cc — fp2_test.cc
longfellow-zk/lib/ec/p256.h — picks Fp256 and wires it into EllipticCurve.
longfellow-zk/lib/circuits/ecdsa/verify_circuit.h — consumes Fp256 at the circuit boundary.

Big Integers (Nat) — the limb layer underneath.
Elliptic Curves — the first big consumer.
Binary Fields (GF(2^k)) — the characteristic-two alternative.