CompPoly/Fields/Extension/ is the computable field-extension framework for odd
characteristic. It models F[X] / f for an arbitrary monic modulus f as a dense
coefficient vector and proves it equal to AdjoinRoot f, so Mathlib field theory applies to
it. The parameters are ExtensionParams (the modulus stored by its lower coefficients);
binomials X^d - W keep the ergonomic front-end BinomialParams, mapped in by
BinomialParams.toExtensionParams.
This page owns extension-field architecture. The characteristic-2 stack is a separate,
independent development — see binary-fields-and-ntt.md.
Most extension fields used in practice by a STARK or zkVM are binomial extensions: a
degree-2 to degree-8 extension of a 31- or 32-bit prime, defined by X^d - W. When a
binomial is available, prefer it — it buys two things:
- Cheap irreducibility. Rabin's test collapses to two exponentiations in the base field (see below).
- Cheap multiplication.
X^d = Wmeans the high half of the schoolbook product folds back with a single scalar multiply, with no polynomial remainder step.
But a binomial is not always available. A degree-d binomial extension of F_q requires
d ∣ q - 1; when gcd(d, q - 1) = 1 the map x ↦ x^d is a bijection and every X^d - W
has a root. Over KoalaBear, p - 1 = 2^24 · 127, so the only binomial degrees available are the
powers of two (up to 2^24) and multiples of 127:
d |
bits | binomial? |
|---|---|---|
| 4 | 124 | yes, X^4 - 3 — but under 2^128 |
| 5 | 155 | no: 5 ∤ p - 1, so x ↦ x^5 is a bijection |
| 6 | 186 | no, and more strongly: 3 ∤ p - 1, so every W is a cube V^3 and X^6 - W = (X^2 - V)(X^4 + V X^2 + V^2) factors for every W |
| 8 | 248 | yes, but wider than needed |
Hence KoalaBear/Ext5.lean adjoins a root of the
non-binomial quintic X^5 + X^2 - 1, and
KoalaBear/Ext6.lean a root of the sextic
X^6 + X^3 + 1 = Φ₉. The general-modulus framework and the certificate-based irreducibility
pipeline below exist to make such extensions routine.
Degree 6 is the smallest KoalaBear extension that is both comfortably above 2^128 and of
composite degree, so — unlike the prime-degree quintic — it has proper subfields, which is what
makes a cheap Frobenius and a norm-based inverse possible. See "Choosing a general modulus".
| Layer | File | Owns |
|---|---|---|
| Rabin's test, general | ../../CompPoly/Data/Polynomial/Rabin.lean |
irreducible_of_rabin, irreducible_iff_rabin for any degree over any finite field |
| Factor-degree bound | ../../CompPoly/ToMathlib/Polynomial/Irreducible.lean |
exists_factor_natDegree_le_of_reducible |
| Binomial criterion | ../../CompPoly/Fields/Extension/Binomial.lean |
the collapse to base-field exponentiations; irreducible_X_pow_four_sub_C_iff |
| Rabin certificates | ../../CompPoly/Data/Polynomial/RabinCertificate.lean |
kernel-checked chains for non-binomial moduli; runChain_sound, irreducible_of_rabin_prime_degree, irreducible_of_rabin_two_prime_factors, irreducible_of_rabin_degree_six |
| Carrier and ring ops | ../../CompPoly/Fields/Extension/Defs.lean |
ExtensionParams, BinomialParams (+ toExtensionParams), Ext P, Ext.shiftReduce, Ext.monomialMod, Ext.mul (spec), Ext.red + Ext.mulTbl (compiled, via @[csimp]) |
Bridge and CommRing |
../../CompPoly/Fields/Extension/Bridge.lean |
toQuot, toQuot_shiftReduce, toQuot_mul, instCommRing |
Bijectivity and Field |
../../CompPoly/Fields/Extension/Field.lean |
ringEquivQuot, card_ext, inv, instField |
Data/Polynomial/Rabin.lean generalizes the degree-128/GF(2) specialization
irreducible_of_rabin_128_passed_over_GF2 in Fields/Binary/BF128Ghash/Basic.lean, but does not
yet replace it — Binary/ is deliberately untouched, so there are currently two Rabin
soundness proofs in the repo. Rebasing the GHASH one onto irreducible_of_rabin is a named
follow-up; until then, a fix to the argument needs applying in both places.
Concrete instances live next to their base field:
KoalaBear/Ext4.lean (X^4 - 3),
BabyBear/Ext4.lean (X^4 - 11),
Hachi/Ext4.lean (X^4 - 2), and the non-binomial
KoalaBear/Ext5.lean (X^5 + X^2 - 1, with its
irreducibility proof in
KoalaBear/Ext5/QuinticIrreducible.lean
and generated certificate data in
KoalaBear/Ext5/QuinticCertData.lean)
and KoalaBear/Ext6.lean (X^6 + X^3 + 1, the first
composite-degree general modulus, with
Ext6/SexticIrreducible.lean and
Ext6/SexticCertData.lean).
Ext6/GaloisField.lean is a separate
opt-in module identifying Ext6 with Mathlib's abstract GaloisField KoalaBear.fieldSize 6, so
the computable arithmetic here can serve developments phrased over that (ArkLib's KoalaSextic,
for the Proximity Prize parameter point of [ABF26], ePrint 2026/680). GaloisField commits to no
modulus, so the identification follows from card_ext6 alone and is independent of the choice of
Φ₉ — but it is noncanonical, so it pins down nothing about where ext6Gen lands.
Concretely, for P : ExtensionParams F:
| Surface | Declarations |
|---|---|
| Ring / field | CommRing (Ext P), Field (Ext P) (the latter given [Fact (Irreducible P.poly)]) |
| Base field | Ext.ofBase : F → Ext P, Ext.ofBaseRingHom, Algebra F (Ext P) (hence Module F (Ext P) via Algebra.toModule) |
| Adjoined root | Ext.gen, Ext.gen_pow_d : gen ^ d = monomialMod d, Ext.aeval_gen_poly : aeval gen P.poly = 0; for a binomial, Ext.gen_pow_d_binomial : gen ^ d = ofBase W |
| Specification | Ext.toQuot, Ext.ringEquivQuot : Ext P ≃+* AdjoinRoot P.poly |
| Cardinality | Fintype (Ext P), Ext.card_ext : Fintype.card (Ext P) = q ^ d |
| Coefficients | Ext.coeff, Ext.ofFn, Ext.equivFn : Ext P ≃ (Fin d → F) |
With the Algebra instance in place, ordinary Mathlib machinery — aeval, scalar towers,
Subalgebra, Module — applies directly.
Still missing, and the natural next step: tower support. There is no AlgebraTower instance
(CompPoly/Data/RingTheory/AlgebraTower.lean), so F ⊂ Ext F 2 ⊂ Ext F 4 does not compose and
the Mersenne31 CM31/QM31 Circle-STARK stack is out of reach.
Rabin's test says a degree-d polynomial f over F_q is irreducible exactly when
f ∣ X^(q^d) - X and f is coprime to X^(q^(d/l)) - X for every prime l ∣ d.
For a binomial, X^d = W gives X^(q^j) ≡ W^((q^j - 1)/d) * X (mod X^d - W) whenever
d ∣ q^j - 1. Both conditions therefore become conditions on W alone:
X^d - Wis irreducible overF_qiffW^((q^d - 1)/d) = 1andW^((q^(d/l) - 1)/d) ≠ 1for every primel ∣ d.
For d = 4 that is two exponentiations, discharged by reduce_mod_char, which does modular
repeated squaring during elaboration.
Nothing here uses native_decide, per the TCB policy in AGENTS.md.
For a non-binomial modulus nothing collapses, and the Rabin conditions are genuine
F[X] statements: f ∣ X^(q^d) - X needs X^(q^d) mod f, about d · log₂ q modular
squarings. Data/Polynomial/RabinCertificate.lean
handles this with kernel-checked certificates:
- Polynomials are little-endian
ℕ-coefficient lists with schoolbook arithmetic by structural recursion, so checks reduce in the kernel via GMP-acceleratedNatops. - A whole square-and-multiply chain is one list literal verified by a single kernel
reduction of
runChain;runChain_soundlifts it toX^N % f = r % f. - The trace condition is a chain ending at
X; coprimality is a chain plus a Bézout identityu·f + v·w = 1on the reduced residue — no Euclidean gcd chain. irreducible_of_rabin_prime_degreepackages the test whendis prime (one trace, one coprimality check).
Composite degree needs one coprimality check per prime factor, and the prime-degree collapse
is unsound there rather than merely weak. Polynomial.irreducible_of_rabin already quantifies
over d.primeFactors; the packaged forms are:
d |
Wrapper | Checks |
|---|---|---|
| prime | irreducible_of_rabin_prime_degree |
f ∣ X^(q^d) - X, IsCoprime f (X^q - X) |
6 |
irreducible_of_rabin_degree_six |
plus IsCoprime f (X^(q^3) - X) and IsCoprime f (X^(q^2) - X) |
| two prime factors | irreducible_of_rabin_two_prime_factors |
as above, Nat.primeFactors d = {ℓ₁, ℓ₂} supplied by the caller |
Concretely, over KoalaBear (X^3 + X + 4)(X^3 + X - 4) divides X^(p^6) - X and is coprime to
X^p - X, so it satisfies the prime-degree conditions verbatim while being visibly reducible;
only the q^3 check rejects it. Nat.primeFactors 6 = {2, 3} cannot be closed by decide
(Nat.primeFactorsList is well-founded recursive and does not reduce in the kernel), so it is
proved via Nat.primeFactors_mul, mirroring primeFactors_four in Extension/Binomial.lean.
The generator loops over the prime factors too, and the same trap applied to it: before that fix
it reported the product above as irreducible and exited 0. Its --self-test flag now checks it
against known-answer cases including that polynomial.
Certificate data is emitted by the untrusted generator
scripts/gen_rabin_certificate.py
(--lean/--namespace produce a complete data module); the kernel re-checks every step.
The KoalaBear quintic instance costs ~290 generated lines and compiles in about two
seconds — contrast the roughly 2100 lines of per-step BitVec certificates the same test
costs the GHASH polynomial (Fields/Binary/BF128Ghash/XPowTwoPow{Mod,Gcd}Certificate.lean),
which predates this framework.
Since every irreducible f of degree d gives the same field up to isomorphism, the choice is
purely about arithmetic cost, and it is decided by two tables: the reduction table
X^d … X^(2d-2) mod f that Ext.red holds, and the Frobenius matrix. Entries of ±1 cost an
add or a negation; anything else costs a base-field multiplication. Measured over the irreducible
sextics of KoalaBear:
| modulus | red-table nonzeros | needing a multiply | Frobenius nonzeros | needing a multiply |
|---|---|---|---|---|
X^6 + X^3 + 1 (Φ₉) |
8 | 0 | 8 | 0 |
X^6 - X^3 + 1 (Φ₁₈) |
8 | 0 | 8 | 0 |
X^6 - 2X^3 - 2 |
10 | 10 | 11 | 9 |
X^6 + 4X - 3 |
10 | 10 | 31 | 30 |
X^6 + 3X^2 - 3 |
11 | 11 | 16 | 15 |
X^6 + X^4 + 3 |
13 | 9 | 16 | 15 |
So prefer, in order: a cyclotomic Φₙ when one has the right degree; then a sparse trinomial with
±1 coefficients; then anything sparse. Two further points, both visible above:
- A modulus of the form
g(X^k)puts a subfield atF_p(θ^k)with a sparse coordinate description, i.e. it is a tower in disguise.Φ₉ = g(X^3)withg = Y^2 + Y + 1givesF_p ⊂ F_p² ⊂ F_p⁶, so the tower's arithmetic is available without any tower machinery. The mirror orientationh(X^2)withhcubic isX^6 + X^4 + 3— the same idea, measurably worse. - Prefer all-nonnegative coefficients when there is a choice: the certificate encoding then needs
no
p - 1literal, and nocast_p_sub_one-style lemma. ComparesexticL = [1,0,0,1,0,0,1]againstquinticL = [2130706432, 0, 1, 0, 0, 1].
- Pick
W. Ford = 4overq ≡ 1 mod 4, any non-square works; prefer the smallest, so that multiplying byWis cheap. - Write the
BinomialParams, supplyingcard_eq := ZMod.card _. - Prove irreducibility with
irreducible_X_pow_four_sub_C_of_card. The two exponentiation goals need the type presented asZMod <numeral>, becausereduce_mod_charreads the modulus syntactically andfieldSizeis an expression like2 ^ 31 - 2 ^ 24 + 1. Use ashow— see any of the threeExt4.leanfiles. - Register
instance : Fact (Irreducible ...), define theabbrevasExt ...Params.toExtensionParams, and route theFactthroughtoExtensionParams_poly— seeKoalaBear/Ext4.lean.
That is about 60 lines.
- Pick a monic irreducible
f(confirm withscripts/gen_rabin_certificate.py, which exits nonzero iffis reducible). - Generate the certificate module:
python3 scripts/gen_rabin_certificate.py --p <p> --f <coeffs> --lean <path> --namespace <NS>. - Write the irreducibility wrapper:
toPoly p fL = f,natDegree,f ≠ 0, then the chain/Bézoutrflchecks and the assembly throughirreducible_of_rabin_prime_degree(primed, seeKoalaBear/Ext5/QuinticIrreducible.lean) orirreducible_of_rabin_degree_six/irreducible_of_rabin_two_prime_factors(composited, seeKoalaBear/Ext6/SexticIrreducible.lean). At compositedthere is one chain plus Bézout block per prime factor, namedcop<m>Steps/cop<m>Rp/… form = d / ℓ. - Write the
ExtensionParams(lower coefficients off, little-endian) and prove...Params.poly = f; register theFactand define theabbrev— seeKoalaBear/Ext5.lean(supporting cert/proof files underKoalaBear/Ext5/).
That is the generated data plus about 200 hand-written lines.
Ext P is Vector F P.d: dense, little-endian, length exactly d. There is no degree-bound
invariant to maintain — the bound is structural, a consequence of the length, not a proposition
carried alongside the data. As a result this subtree is independent of the CPolynomial
stack: nothing under CompPoly/Fields/Extension/ imports CompPoly/Univariate/.
The one place a degree bound is needed on the polynomial side — showing that the representative
Ext.toQuot picks is the canonical degree-< d one — is proved directly in
Extension/Bridge.lean as degree_repr_lt, from
Polynomial.degree_sum_le and Polynomial.degree_C_mul_X_pow_le. If you want the
CPolynomial-side theory instead (degreeLT, degreeLTEquiv in
Univariate/Linear.lean and
Univariate/ToPoly/Degree.lean), it exists but is
not wired to this framework; connecting them would be new work.
ExtensionParams carries d, the modulus's lower coefficients, and the base-field cardinality
q as a type index, so two different extensions of the same base field are different types
whose instances cannot be confused. q is data rather than Fintype.card F because Fermat
inversion evaluates the exponent at runtime, and Fintype.card (ZMod p) would enumerate all
of Fin p. BinomialParams is the ergonomic front-end for X^d - W, mapped in by
BinomialParams.toExtensionParams (lower coefficients (-W, 0, …, 0)), with toExtensionParams_poly
identifying the two spellings of the defining polynomial.
The instances are assembled field-by-field, not by Function.Injective.commRing /
.field. Those transports take toQuot as data, which forces the resulting instance
noncomputable. That is not merely cosmetic: Monoid.toNatPow then outranks Ext.instPow, and
compiled x ^ n fails to build. This was observed, not hypothesized. If you add structure to
Ext P, keep it computable and keep a #guard in
tests/CompPolyTests/Fields/Extension/Arithmetic.lean
that exercises the operation, since only compiled evaluation catches this class of regression.
The load-bearing correctness lemma is Ext.toQuot_shiftReduce: shiftReduce is "multiply by
X, reduce mod f", and toQuot (shiftReduce e) = rt * toQuot e is the one place the
defining relation rt_relation is consumed. monomialMod k = shiftReduce^[k] 1 is then
X^k mod f by a one-line induction, and toQuot_mul — Ext.mul expands product monomials
through monomialMod — follows with no wrap-around case analysis at all.
The framework is correctness-complete, and its design is ready for fast arithmetic — Ext P
is generic over the base-field carrier precisely so a Montgomery representation can be dropped
in. The current instantiation over ZMod, however, is not fast. Measured with
lake exe CompPolyBench --small on a developer laptop:
| Group | Operation | Average |
|---|---|---|
fields-extension-koalabear-ext4-mul |
mul |
~25 us |
fields-extension-koalabear-ext4-inv |
inv |
~3.5 ms |
fields-extension-koalabear-ext5-mul |
mul |
~41 us |
fields-extension-koalabear-ext5-inv |
inv |
~7.6 ms |
fields-extension-koalabear-ext6-mul |
mul |
~64 us |
fields-extension-koalabear-ext6-inv |
inv |
~15 ms |
For scale, a hand-written Rust degree-4 BabyBear multiply is a few nanoseconds. Do not quote this framework as performance-ready until the items below are done.
Those numbers are with the reduction table in place. The same benchmarks with @[csimp] removed
from mul_eq_mulTbl, i.e. running the specification directly, on the same machine:
| Operation | Spec (mul) |
Table (mulTbl) |
Speedup |
|---|---|---|---|
Ext4 mul |
78.1 us | 25.4 us | 3.1x |
Ext4 inv |
14.0 ms | 3.5 ms | 4.0x |
Ext5 mul |
195.6 us | 40.6 us | 4.8x |
Ext6 mul |
429.8 us | 63.8 us | 6.7x |
Ext6 inv |
119.6 ms | 15.1 ms | 7.9x |
The speedup growing with d is the point: it is the O(d^5) → O(d^3) change becoming visible.
The 78 us spec figure also reproduces the ~73 us recorded before the table existed, which is what
makes this an honest A/B rather than a change of measurement conditions.
The remaining causes, in order of size:
-
Ext.mulallocates, and its asymptotics are still not optimal.Asymptotics.
mul— the specification — expands each product monomial throughmonomialMod (i + j) = shiftReduce^[i+j] 1, recomputed for every(m, i, j). That is what keeps the correctness proof one additive lemma, and what made the compiled code roughly O(d⁵).Ext.rednow holdsX^0 … X^(2d-2) mod f, andExt.mulTblconsults it instead;mul_eq_mulTblis registered@[csimp], so compilation is swapped while every proof still refers toExt.mul. That is O(d³). The remaining step to O(d²) is a schoolbook convolution to length2d - 1folded throughred, rather than the current triple sum, plus hoistingredout ofmulTblso it is computed once perPrather than once per multiplication.Allocation. Because
Pis a runtime parameter nothing monomorphises:Finset.univis rebuilt andFinvalues boxed on every call.@[specialize]recovers only about 6%. The fix is anArray-loop backend, following theMulContextidiom inUnivariate/Context.lean.Keep the
monomialModexpansion as the spec whatever replacesmulTbl: it is whattoQuot_mulis proved against, and reducing everything totoQuot_shiftReduceis why that proof is short. -
The base field is
ZMod p, i.e. boxedNatarithmetic. Instantiating overKoalaBear.Fast.Field(UInt32Montgomery,Montgomery/Native32Field.lean) needs onlyFintypefor that carrier plus irreducibility transported alongMontgomery.Native32.ringEquivwithPolynomial.mapEquiv. No change to the framework. -
Inversion is Fermat (
x ^ (q^d - 2)), aboutd · log qextension multiplications — the ~140x ratio tomulabove, and it is the reason the#guardregressions dominate the test module's build time. A norm-based inverse (Itoh–Tsujii) would be roughly two orders of magnitude faster:N(x) = ∏_j φ^j(x)lands in the base field, sox⁻¹ = (∏_{j≥1} φ^j(x)) · N(x)⁻¹costsd - 1Frobenius applications,d - 1extension multiplications, and one base-field inverse.The cost hinges on Frobenius being sparse, which is exactly what the modulus choice above buys. For a binomial with
d ∣ q - 1it is a coordinate-wise scaling by powers ofW^((q-1)/d); forExt6it isθ ↦ θ^2with all-±1entries, sincep ≡ 2 mod 9. NeitherExt.frobeniusnorExt.normexists yet.
None of these is hidden behind an abstraction that makes replacing it awkward, and each is
guarded by the #guard regressions in
tests/CompPolyTests/Fields/Extension/Arithmetic.lean.
Hachi (2^32 - 99) has no FastField Montgomery path: Mont32Field requires
modulus < 2^31, since radix-2^32 reduction needs x + m * p < 2^64. It also has two-adicity
2, so it admits no radix-2 NTT domain. The extension layer is generic over the base-field
carrier, so a future 64-bit Montgomery layer would be picked up unchanged.