[!WARNING] This library was made with the help of AI. Audit the code yourself, or with your own agent before using.

[!WARNING] fgf is variable-time throughout and guarantees no constant-time operation. Security applications are not a supported use: any handling of secret field elements, coefficients, or buffers must be audited separately.

fgf — Faster Galois Fields

fgf provides finite-field elements and high-throughput operations over packed buffers. It targets the arithmetic underneath erasure coding, proof systems, and other workloads that repeatedly scale, combine, or reconstruct rows.

fgf is an arithmetic library, not a codec. It does not construct coding matrices, own shards, invert matrices, or implement a recovery protocol.

Installation

The minimum supported Rust version is 1.93.

[dependencies]
fgf = "1.0.0"

For the portable no_std surface without allocation:

[dependencies]
fgf = { version = "1.0.0", default-features = false }

Quick start

Scalar elements expose inherent const arithmetic:

use fgf::gf16;

const A: gf16::Elem = gf16::Elem::from_raw(0x1234);
const B: gf16::Elem = gf16::Elem::from_raw(0x0108);
const PRODUCT: gf16::Elem = A.mul(B);

assert_eq!(PRODUCT.div(B), A);

Packed operations use the field marker as their generic parameter. Buffers contain consecutive little-endian elements and may be unaligned.

use fgf::{Gf8B, gf8b, ops};

let src = [0x01u8, 0x02, 0x03, 0x04];
let mut dst = [0u8; 4];

ops::mul_add::<Gf8B>(&mut dst, gf8b::Elem::from_raw(0x03), &src);
assert_eq!(dst, [0x03, 0x06, 0x05, 0x0c]);

Supported fields

All element families support arithmetic operators including unary negation, assignment operators, Sum, Product, ordering, formatting, and named raw conversions. In characteristic two negation is the identity. Import fgf::field::Elem when generic code needs the trait methods.

By convention, inversion and division are total: inv(0) == 0 and x / 0 == 0.

Packed operations

The _with forms consume prepared coefficients. Preparation does not weaken validation: prepared and one-shot operations enforce the same public geometry.

use fgf::{Gf16, gf16, ops};

let coeff = ops::Coeff::<Gf16>::new(gf16::Elem::from_raw(0x0108));
let src = 0x1234u16.to_le_bytes();
let mut dst = [0u8; 2];

for _ in 0..3 {
    ops::mul_add_with::<Gf16>(&mut dst, &coeff, &src);
}

let once = gf16::Elem::from_raw(0x1234).mul(gf16::Elem::from_raw(0x0108));
assert_eq!(dst, once.to_bytes());

Coeff<F> prepares one coefficient without allocation. With alloc, CoeffVec<F> and CoeffMatrix<F> own reusable prepared collections; a single entry borrows as CoeffRef<'_, F>, which the single-coefficient _with operations accept directly. Prepared values are process-backend-specific and should be rebuilt rather than serialized.

ops::pack, ops::unpack, and ops::pack_to_vec convert between typed elements and packed byte buffers.

Bit-packed GF(2)

The bits module stores one GF(2) element per bit, least-significant bit first. Operations that depend on the logical element count take it explicitly.

use fgf::bits;

let mut row = [0u8; 1];
bits::set_range(&mut row, 7, 0, 7);
bits::clear_range(&mut row, 7, 1, 3);

assert_eq!(row[0], 0b0111_1001);
assert_eq!(bits::weight(&row, 7), 5);

Range operations leave padding bits untouched. Whole-buffer operations process the complete supplied slices.

Features

Nothing behind internals is a compatibility promise. Normal users should use ops, which handles backend selection and capability proofs internally.

Platforms and backends

backend() reports the process-wide selection. backend_for::<F>() reports the backend implemented by a particular field. SIMD_BACKEND may request a weaker backend at process startup; unsupported upgrades are ignored.

Frozen encodings

These are the wire conventions a consumer above this crate depends on. Each is stated in full by the module that owns it.

Safety and scope

The stable API is safe, but the implementation is variable-time. Table lookups, cache behavior, and data-dependent work make fgf unsuitable for secret field elements or coefficients.

Packed prime-field operations expect canonical input lanes and preserve canonical output. Scalar prime-field operations accept any raw lane and reduce arithmetic results canonically.

Performance

BENCHMARKS.md records pinned measurements for the public operation shapes on multiple x86 hosts. The benchmark targets are:

cargo bench --bench kernels
cargo bench --bench compare

Building

cargo build
cargo build --no-default-features
cargo test --all-features

License

MIT — see LICENSE.