Bignum Arithmetic 10: Prime-Field Arithmetic

Bignum arithmetic notes / 10

Prime-field arithmetic

A prime-field layer is a bignum layer with a stronger invariant: every operation is interpreted modulo one fixed prime.

For prime \(p\), the field \(\mathbb F_p\) consists of residue classes modulo \(p\). The implementation chooses a representation: canonical limbs, Montgomery residues, or a specialized radix.

Field element contract

For a canonical representation:

• input: \(0\le a,b<p\);
• add/sub: return \(0\le r<p\);
• multiply/square: return \(0\le r<p\);
• inversion: if \(a\ne0\), return \(a^{-1}\bmod p\).

For Montgomery representation, the stored value of \(x\) is \(xR\bmod p\). The API must make this invisible or explicit, but never ambiguous.

This is the field contract consumed by elliptic curve equations and the elliptic field interface: point formulas are only valid when their field inputs satisfy the promised canonical or lazy ranges.

Inversion by Fermat

Since \(p\) is prime,

\[a^{p-1}=1\quad(a\ne0), \qquad a^{-1}=a^{p-2}\pmod p.\]

This uses modular exponentiation and can be made regular with a fixed addition chain for a fixed prime.

Inversion by extended Euclid

The extended Euclidean algorithm finds \(u,v\) such that

\[ua+vp=\gcd(a,p)=1.\]

Then \(u\bmod p\) is the inverse. Classical Euclid is variable-time; constant-time variants require careful bounded iteration.

Example: P-256 prime

For \(p=2^{256}-2^{224}+2^{192}+2^{96}-1\), reduction can exploit the sparse relation defining \(2^{256}\) modulo \(p\). The teaching implementation keeps the first version auditable: field elements are eight little-endian uint32_t words, and a word product is decomposed into 16-bit halves before it is accumulated.

typedef uint32_t word_t;
typedef struct { word_t v[8]; } fe256_t;

This type has mathematical radix \(B=2^{32}\). Its multiplication proof is the 32-by-32 decomposition from the schoolbook multiplication article.

Example: Curve25519-style prime

For \(p=2^{255}-19\) in the same 32-bit-word model, a uniform implementation can use eight uint32_t words. The high bit of the top word is unused for canonical residues, and reduction must fold the excess using only bounded shifts, additions, and the small public multiplier 19.

typedef struct { uint32_t v[8]; } fe_25519;

C API boundary

void fe256_add(fe256_t *r, const fe256_t *a, const fe256_t *b);
void fe256_mul(fe256_t *r, const fe256_t *a, const fe256_t *b);
void fe256_sqr(fe256_t *r, const fe256_t *a);
void fe256_inv(fe256_t *r, const fe256_t *a);
void fe256_to_mont(fe256_t *r, const fe256_t *a);
void fe256_from_mont(fe256_t *r, const fe256_t *a);
void fe256_mont_mul(fe256_t *r, const fe256_t *a, const fe256_t *b);

The type fixes the modulus and word count. That is safer than a generic (limbs, n, modulus) interface in elliptic-curve code.

SageMath verification

p = 2^256 - 2^224 + 2^192 + 2^96 - 1
F = GF(p)
def words(x):
    return [hex((Integer(x) >> (32*i)) & 0xffffffff) for i in range(8)]
for a in [1, 2, 19, p-2]:
    inv = power_mod(a, p-2, p)
    print(words(inv))
    print((a * inv) % p == 1)

Cryptographic warning

Reject noncanonical encodings at API boundaries when the protocol requires canonical encodings. Accepting multiple encodings of the same field element can break transcript binding, signature verification, or subgroup checks.