Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-120
Model dependence of finite-field multiplication complexity over GF(4) and GF(8)
Over GF(4), unrestricted/rational MC=3, geom MC=2; over GF(8), rational XAG in [4,5], geom XAG=3, bilinear ladder 6,5,3
Published 2026-09-04
For everyone
Plain summary
Multiplying numbers in small finite fields like GF(4) and GF(8) requires nonlinear operations such as logical AND gates. Multiplicative complexity measures the minimum number of these multiplication gates needed in a circuit. This work shows that this cost shifts depending on the circuit rules allowed, such as whether gates can evaluate rational expressions, geometric projections, bilinear products, or general unrestricted logic.
For GF(4), the exact cost is 3 in unrestricted logic and rational models, but drops to 2 in geometric models. For GF(8), the cost spans a ladder depending on whether the circuit is geometric (3), rational (4 or 5), or bilinear (ladder 6, 5, 3). Two caveats apply: the exact cost of 3 for GF(4) was already known in prior literature, and the unrestricted GF(8) bracket of [4, 6] established here has since been resolved to an exact cost of 6 in entry MF-128.
Result
Multiplication complexity over small binary fields depends strictly on the computational model:
- Over GF(4):
- Unrestricted multiplicative complexity: MC = 3
- Rational exact complexity: 3
- Rational border complexity: 3
- Geometric exact complexity: 2
- Geometric border complexity: 2
- Over GF(8):
- Unrestricted XAG complexity in MF-120: bracketed in [4, 6] (superseded by exact MC = 6 in MF-128)
- Rational XAG complexity: bracketed in [4, 5]
- Geometric XAG complexity: 3
- Bilinear / depth-one exact ladder: 6, 5, 3
No unrestricted exact-six claim is established within MF-120 itself.
Setting and definitions
Let GF(2^k) denote the finite field of order 2^k. Field multiplication is a bilinear mapping from GF(2)^k x GF(2)^k to GF(2)^k.
- Unrestricted multiplicative complexity MC(f): the minimum number of binary AND gates required to compute f over the basis {AND, XOR, NOT}.
- Rational model / Rational XAG: circuits where intermediate multiplication terms are restricted to rational linear combinations of inputs or prior products.
- Geometric model / Geometric XAG: complexity under geometric/projective decompositions and lower-dimensional algebraic projections.
- Border complexity: the minimum complexity under approximating families of circuits.
- Bilinear / depth-one complexity: tensor rank and bilinear circuits evaluating products of linear forms without cascading intermediate nonlinear products.
Method
Evidence tier: P + FR. Complexity bounds across models were verified using SAT encodings and finite-field structural checks:
- CaDiCaL solved bounded XAG and bilinear circuit encodings; execution logs are stored in cadical-receipt.json.
- Exhaustive algebraic checks for finite-field multiplication ladders were verified in finite-checks-receipt.json.
- Full verification and cross-check records are compiled in VERIFY-STRASSEN.md, COUNCIL-STRASSEN.md, and STATE-OF-PROGRAM-V2.md.
Discussion
MF-120 isolates the divergence in multiplication complexity across unrestricted, rational, geometric, and bilinear models over GF(4) and GF(8).
Scope boundaries and register corrections:
- Prior art on GF(4): The exact unrestricted 3-AND multiplicative complexity for GF(4) multiplication is prior art. The upper bound of 3 is given by the classical bilinear construction. The lower bound of 3 transfers from the quadratic lower bound to unrestricted XAG multiplicative complexity via the Mirwald–Schnorr normalization for quadratic Boolean maps with at most two outputs (Mirwald and Schnorr 1992, Find and Boyar 2014, Ballet et al. 2011).
- Supersession of unrestricted GF(8): MF-120 bracketed unrestricted binary GF(8) multiplication complexity within [4, 6]. This bracket was superseded by MF-128, which established the exact unrestricted value MC = 6 using a solver-independent two-output-prefix lower chain and a complete-domain six-product replay (documented in FREE-VERIFY.md and FREE-05.md).
- The remaining rational, geometric, border, and bilinear depth-one bounds established in MF-120 remain confirmed.
For everyone — the takeaway
What this means
Circuit complexity is not a single universal number. It depends on the specific operations and intermediate forms allowed in the hardware or software model. Field multiplication in GF(4) and GF(8) can look cheaper in geometric or rational formulations than in unrestricted digital logic. Tracking these model gaps prevents invalid comparisons across cryptographic designs and theoretical lower bounds.
Attribution and prior art
Prior art: The 3-AND complexity for GF(4) was previously established by Mirwald–Schnorr (1992), Find–Boyar (2014), and Ballet et al. (2011). Sources: arXiv:1407.6169 · arXiv:1107.1184 · doi:10.1016/0304-3975(92)90235-8
Register references
- Entry: MF-120
- Reports:
- zkgolf-decomp/reports/VERIFY-STRASSEN.md
- zkgolf-decomp/reports/COUNCIL-STRASSEN.md
- zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md
- zkgolf-decomp/reports/PRIOR-ART-S5.md
- zkgolf-decomp/FREE-VERIFY.md
- zkgolf-decomp/FREE-05.md
- Receipts:
- zkgolf-decomp/verify-strassen-scratch/finite-checks-receipt.json (SHA-256 d5038c528fa125b3ee78e3a614db72d8d8f1582ea614ddf0941011059a00bc5c)
- zkgolf-decomp/verify-strassen-scratch/cadical-receipt.json (SHA-256 5921cec7ad1f7e531882c568b4f45aea8ad81517f2295780204b32ba4c56fe6e)
- Prior-art literature:
- C. P. Mirwald and C. P. Schnorr, "The multiplicative complexity of quadratic Boolean forms," Theoretical Computer Science 102(2) (1992), 307–328, doi:10.1016/0304-3975(92)90235-8
- M. Gausdal Find and J. Boyar, "Multiplicative Complexity of Vector Valued Boolean Functions," arXiv:1407.6169
- S. Ballet et al., "On the Tensor Rank of Multiplication in Finite Fields," arXiv:1107.1184
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 3 of 8 receipt files bundled (32 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-08-30Correction (2026-08-30): The exact unrestricted three-AND value for GF(4) multiplication stands unchanged, but is prior art. Credit belongs to C.
- 2026-08-31On 2026-08-31, the unrestricted binary GF(8) interval in MF-120 was superseded by MF-128's exact value of six, confirmed by an independent proof and replay check. All GF(4) values and model labels in MF-120 remain valid.
- 2026-09-04Published on this site.