Module gf256 

GF(2^8) — the finite field with 256 elements, the shared substrate for erasure coding, multivariate cryptography (Oil-and-Vinegar / Rainbow), and the algebraic (XL) cryptanalysis engine.

Elements are bytes; addition is XOR (characteristic two, so add == sub), and multiplication is polynomial multiplication modulo the primitive polynomial x^8 + x^4 + x^3 + x^2 + 1 (0x11d) — the reduction polynomial used by the Reed-Solomon / QR-code lineage. (Note this is NOT the AES/Rijndael polynomial 0x11b; a scheme that fixes a different field representation needs its own.)

mul/div run off a log/exp table generated once from the generator 2, whose multiplicative order is the full 255, so exp/log are true inverses across the whole nonzero field. On top of the field this module provides the linear algebra that multivariate signing and kernel extraction need: matrix invert, matmul, matvec, rank, solve (a particular solution of A x = b), and nullspace (a basis of {x : A x = 0}) — all exact, no floating point.

Functions

add

Field addition. In characteristic two this is XOR, and it is its own inverse, so subtraction is the same operation.

div

Field division a / b. 0 has no inverse, so a zero divisor yields 0 — a safe, defined sentinel (NOT a meaningful quotient) that holds identically in debug and release; callers must still treat b == 0 as a precondition violation, never as a value.

inv

Multiplicative inverse. inv(a) = a^254 since the group has order 255; inv(0) = 0 — 0 has no inverse, so this is a safe sentinel rather than the silent garbage a raw table lookup would return.

invert

Invert a k×k matrix over GF(2^8) by Gauss-Jordan elimination; None if singular.

matmul

Multiply an n×k matrix by a k×c matrix over GF(2^8).

matvec

Multiply an m×n matrix by an n-vector over GF(2^8), giving an m-vector.

mul

Field multiplication modulo 0x11d. 0 absorbs.

mul_add_region

Region multiply-accumulate over GF(2^8): dst[i] ^= c · src[i] for every byte — the inner loop of Reed-Solomon encode/reconstruct. src and dst must be the same length. The body is a per-c table lookup XORed into the destination, a shape the compiler AUTO-VECTORIZES to SSE/AVX on native and to wasm v128 under simd128 — the SIMD speedup for browser FEC, in safe Rust with no hand-written intrinsics to silently miscompile (its result is pinned byte-exact to the scalar field by the tests).

mul_table

A 256-entry lookup table for multiplication by a fixed constant c: table[b] = c · b in GF(2^8). Precompute once per coefficient; a whole region then multiplies by one table lookup per byte — the SIMD-friendly hot path of Reed-Solomon coding.

nullspace

A basis of the null space {x : A x = 0} over GF(2^8). The basis has n - rank(A) vectors of length n; together they span every solution of the homogeneous system.

pow

base^exp in GF(2^8). base^0 == 1 for every base (including 0).

rank

Rank of an m×n matrix over GF(2^8).

solve

A particular solution of A x = b over GF(2^8), or None if the system is inconsistent. a is m×n (row per equation), b has length m; the returned x has length n with free variables set to zero. When the caller knows the system is square and full-rank (Oil-and-Vinegar signing after fixing the vinegar variables), the solution is unique.

sub

Field subtraction — identical to add in characteristic two. Named for call-site clarity where the algebra reads as a subtraction.