Big Integers (Nat)

Nat<W64> is a fixed-width unsigned integer type, stored as W64 little-endian 64-bit limbs. Every prime field in Longfellow keeps its elements as Nat instances; the field class adds modular reduction and Montgomery machinery on top. You rarely touch Nat directly — you touch it through a Field::Elt — but when you parse a modulus, deserialize untrusted bytes into a field element, or port a field to a new size, this is the primitive you are reaching through.

When to reach for it

You are defining a new prime field and need to write its modulus as a compile-time constant.
You are parsing an externally supplied integer (a curve order, a user-supplied scalar, a hex string from a test vector) and need a safe deserializer that rejects out-of-range input.
You want constant-time comparison or conditional move on a big integer without pulling in a field modulus.

Design overview

Nat<W64> is a plain value type — a std::array<uint64_t, W64> with arithmetic and parsing methods. All operations are carry-aware and use the platform intrinsics from algebra/sysdep.h (_addcarry_u64, _subborrow_u64, and friends on x86-64) so that the compiler emits native adc/sbb chains.

The type is designed around three jobs:

Bootstrapping field constants. Compile-time string constructors parse decimal or hex literals into limbs so primes, curve orders, and Montgomery R^2 values can live in header files.
Safe deserialization. of_bytes(bytes) reads a fixed-width little-endian integer; of_untrusted_string(s) validates length and digit set before parsing. Both reject malformed input rather than silently truncating.
Field-layer support. add, sub, and mac (multiply-accumulate) are the loops the Montgomery reduction in fp_generic.h runs on top of.

A tiny helper, inv_mod_b(), implements Newton’s iteration for the odd-modulus inverse mod 2^L. FpGeneric calls it once during construction to precompute -m[0]^{-1} \bmod 2^{64}, the scalar that drives Montgomery reduction.

API surface

Type and construction

template <size_t W64> class Nat — W64 = number of 64-bit limbs. Typical sizes: 2 (128-bit), 4 (256-bit), 6 (384-bit), 9 (521-bit, with a short top limb).
Nat() — zero.
Nat(uint64_t v) — one-limb value.
Nat(std::array<uint64_t, W64>) — raw limbs.
Nat(StaticString) / Nat(const char (&)[LEN]) — compile-time decimal or hex string (hex if prefixed 0x).

Parsing untrusted input

static T of_bytes(const uint8_t bytes[W64 * 8]) — little-endian byte deserialization; always succeeds and returns a Nat for the full fixed width.
static T of_bytes(const uint8_t* bytes, size_t nbits) — variable-width deserializer; masks above nbits so the caller can read a shorter integer than the limb count.
static std::optional<Nat> of_untrusted_string(const char* s) — decimal or 0x-prefixed hex. Rejects over-long strings (more than 20 × W64 digits) and non-digit characters. Returns nullopt on any failure.

Arithmetic

T& add(const Nat& b) — in-place addition; carry-out is discarded ((void) cast). Returns *this.
T& sub(const Nat& b) — in-place subtraction; borrow-out is discarded ((void) cast). Returns *this.
template <size_t WX, size_t WY> T& mac(const Nat<WX>& x, const Nat<WY>& y) — in-place *this += x * y; used by Montgomery multiplication inner loops. Requires W64 >= WX + WY.
bool operator<(const Nat& b) const — derived from sub’s borrow bit, so comparison cost matches subtraction.
T& cmovnz(limb_t nz, const Nat& src) — constant-time conditional move (nz != 0 copies src into *this). Returns *this.

Low-level helpers (`algebra/nat.h`)

template <class limb_t> static limb_t inv_mod_b(limb_t a) — returns a^{-1} mod 2^L where L is the bit-width of limb_t. Requires a to be odd. FpGeneric uses it to derive mprime_ for Montgomery reduction.

Everything above is templated on W64, so the compiler knows the limb count at every call site; there is no runtime dispatch or hidden allocation.

See it used

longfellow-zk/lib/algebra/nat_test.cc — nat_test.cc
longfellow-zk/lib/algebra/fp_generic.h — sees every Nat method in anger through Montgomery reduction.

Prime Fields — the primary consumer of Nat.
Binary Fields (GF(2^k)) — uses a parallel but separate polynomial-limb type.