Quadratic towers

Quadratic towers

A quadratic tower represents a binary extension element as a + b*t over a half-degree base field, with a checked relation t² + A*t + B = 0. Recursive bases build towers through binary degree 64.

This guide targets fgf 3.0.0. The tower reference defines the supported rows and specification traits.

Components are values in the base presentation

For a degree-sixteen tower over a byte field, the low byte contains a and the high byte contains b. The stable encoding is little-endian, so the constant component comes first. Components are typed base-field elements, not interchangeable bytes from another basis.

use fgf::{AES, Binary, Elem, Polynomial, Rijndael16, Tower};

type Base = Binary<8, Polynomial<AES>>;
type Extension = Binary<16, Tower<Rijndael16>>;
let a = Elem::<Base>::from_raw(0x53);
let b = Elem::<Base>::from_raw(0xca);
let z = Elem::<Extension>::from_components(a, b);
assert_eq!(z.to_components(), (a, b));
assert_eq!(z.to_raw(), 0xca53);
assert_eq!(z.to_bytes(), [0x53, 0xca]);
assert_eq!(Elem::<Extension>::ONE.to_components(), (Elem::<Base>::ONE, Elem::<Base>::ZERO));

The same low/high component convention recurses at wider degrees. Raw 1 is not a universal identity if the base uses an ordered basis; the tower embeds the base's ONE in its low component.

Deriving arithmetic from the relation

Characteristic two gives t² = A*t + B. Expanding a product and replacing t² yields:

(a + b*t)(c + d*t) = (a*c + B*b*d) + (a*d + b*c + A*b*d)*t
(a + b*t)^2       = (a^2 + B*b^2) + (A*b^2)*t
conjugate(a+b*t)  = (a + A*b) + b*t
norm(a+b*t)       = a^2 + A*a*b + B*b^2

Every coefficient operation in these equations belongs to the base field. In particular, A and B are coordinates in the declared base, not ordinary integers added to a Rust word.

Shipped specifications

Rijndael16 roots at Binary<8, Polynomial<AES>>; Rijndael32 and Rijndael64 continue that tower. FanPaar2 through FanPaar64 nest from GF(2) through the Fan–Paar relation. Each marker is a specification, used inside Binary<N, Tower<Spec>>, rather than a standalone field type.

An application chooses a local alias such as type F = Binary<16, Tower<Rijndael16>>. The shipped specification's relation and selected generator are frozen conventions. Equal degree does not make Rijndael and Fan–Paar coordinates interchangeable; embeddings change the presentation explicitly.

Define a custom relation

A custom specification declares a supported binary base, raw-coordinate relation coefficients, and a descriptive name. The example below uses the RS byte field as its base and a relation whose absolute trace check succeeds.

use fgf::{Binary, Elem, Embedding, Polynomial, RS, Tower, TowerSpec};

#[derive(Clone, Copy)]
struct RsQuadratic;
impl TowerSpec for RsQuadratic {
    type Base = Binary<8, Polynomial<RS>>;
    const LINEAR_COEFFICIENT: u64 = 2;
    const CONSTANT_COEFFICIENT: u64 = 0x80;
    const NAME: &'static str = "RS quadratic tower";
}

type Base = Binary<8, Polynomial<RS>>;
type Extension = Binary<16, Tower<RsQuadratic>>;
let a = Elem::<Base>::from_raw(0x53);
let b = Elem::<Base>::from_raw(0xca);
let linear = Elem::<Base>::from_raw(2);
let constant = Elem::<Base>::from_raw(0x80);
let z = Elem::<Extension>::from_components(a, b);
let conjugate = Elem::<Extension>::from_components(a + linear * b, b);
let expected_norm = a.square() + linear * a * b + constant * b.square();
assert_eq!(z * conjugate, Elem::<Extension>::from_components(expected_norm, Elem::<Base>::ZERO));
let base_map = Embedding::<Base, Extension>::new().unwrap();
assert_eq!(base_map.trace(z), linear * b);
assert_eq!(base_map.norm(z), expected_norm);

The relation is not valid merely because its coefficients fit. The base must have exactly half the extension degree, A must be nonzero, and absolute trace(B/A²) must be one. These conditions ensure the quadratic is irreducible. Excess coefficient bits and an invalid base are rejected as well.

Validation is evaluated when the defining constants or values require it. A type declaration alone is not proof that its relation is valid. Invalid const constructions fail compilation; the reference includes examples of the rejected cases. There is no degree-128 tower row.

A generator is optional

TowerSpec is sufficient for arithmetic, component conversion, and embeddings. TowerGeneratorSpec additionally supplies a selected generator. Its raw coordinates must represent a full-order nonzero element; the crate checks the declared tower generator's order.

The tower indeterminate t is not automatically a multiplicative generator. Algorithms that need one add a HasGenerator bound and read Elem::<F>::GENERATOR. Arithmetic-only applications need not search for or declare a generator.

Bulk operations and application boundaries

Tower degrees 8, 16, 32, and 64 provide byte-buffer arithmetic. Routing follows the description, not the spelling of a custom marker: supported shipped descriptions can reach their kernels, while other custom descriptions use the typed scalar fallback. backend_for::<F>() reports the field's backend.

Constructing a custom tower is not a general extension-field factory over arbitrary downstream Field implementations. Its base must belong to the supported binary-field vocabulary. Downstream scalar fields covers the separate open scalar contract.

Next: Coordinates and packed bytes. The extension-fields example compares binary towers with QuadMersenne31.