Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-167
Exact quadratic multiplicative complexity of GF(2^4) multiplication and polymul_4
qMC(GF(2^4) mult) = 9, qMC(polymul_4) = 9, unrestricted MC(GF(16) mult) ∈ [8,9], MC(polymul_4) ∈ [8,9]
Published 2026-09-04
For everyone
Plain summary
Multiplying 4-bit numbers in the 16-element finite field GF(16) and multiplying 4-term binary polynomials are core operations in cryptography and error-correcting codes. Standard bilinear algorithms, such as Karatsuba and Winograd multiplication, take 9 multiplications where each multiplication gate takes one input from the first operand and one from the second.
We analyze the broader quadratic model, where multiplication gates can multiply any two linear combinations of all input bits. We prove that both GF(16) multiplication and 4-term polynomial multiplication require at least 9 multiplications in this model: qMC(GF(2^4) mult) = 9 and qMC(polymul_4) = 9. When gate inputs can be nonlinear, the exact complexity sits between 8 and 9 multiplications. The bilinear bound of 9 is standard prior art, but whether the stronger quadratic lower bound appeared previously remains unverified in the register.
Result
For the field multiplication map GF(2^4) x GF(2^4) -> GF(2^4) and the degree-3 polynomial multiplication map polymul_4 over GF(2):
- qMC(GF(2^4) mult) = 9
- qMC(polymul_4) = 9
For unrestricted multiplicative complexity:
- MC(GF(16) mult) ∈ [8, 9]
- MC(polymul_4) ∈ [8, 9]
As a corollary, any 8-AND Boolean circuit computing GF(16) multiplication must contain at least one AND gate with a non-affine input.
Setting and definitions
Let V = V(GF(16) mult) be the 4-dimensional subspace of quadratic forms on GF(2)^8 representing the coordinate functions of field multiplication. The input dimension is n = 8, dim V = 4, and all 15 nonzero forms in V have polar rank 8.
The quadratic multiplicative complexity qMC(V) is the minimum r such that V ⊆ span(p_1, ..., p_r) for rank-2 quadratic forms p_1, ..., p_r. The unrestricted complexity MC(V) allows products of arbitrary Boolean functions.
The quantity m_3(V) is the minimum number of rank-2 products needed to cover any 3-dimensional subspace W ⊂ V.
The target polymul_4 maps two 4-term polynomials over GF(2) (8 inputs) to their 7-term product (7 outputs, dim V(polymul_4) = 7).
Method
The bound is established through Theorem I (Fano rigidity), geometric enumeration, and subspace transfer.
Theorem I establishes that if a 3-dimensional subspace W ⊂ V with seven nonzero classes of polar rank 8 is contained in span(p_1, ..., p_7) for rank-2 products p_i, the products index over nonzero vectors v ∈ F2^3 with rank(p_v) = 2. The quadratic forms satisfy q_u = sum_{<u,v>=1} p_v for u ∈ F2^3 \ {0}. Grouping by linear functional and inverting the 7 x 7 Fano incidence matrix over Q forces the rank vector of (p_1, ..., p_7) to be (2, 2, 2, 2, 2, 2, 2).
This rigidity restricts the search space of 7-product covers to a finite set. The set S(q) of compatible product systems contains 91,392 elements, matching the symplectic orbit count 255·128·63·32 / (15·8·3·2) and verifying completeness and injectivity of the Lemma G enumeration.
Exhaustive search across all 15 hyperplanes (a single orbit under the 15 field multiplications) and 12 basis permutations shows that no 3-dimensional subspace of V is covered by 7 products. Thus m_3(V) >= 8.
If 8 products covered V (dim V = 4), some 7-product subset would cover a subspace of dimension at least 4 + 7 - 8 = 3, contradicting m_3(V) >= 8. Therefore, qMC(V) >= 9. Two-level Karatsuba multiplication provides the matching upper bound qMC(V) <= 9, verified across all 256/256 inputs.
For polymul_4, the embedding V(GF(16) mult) ⊂ V(polymul_4) holds modulo affine terms, giving qMC(polymul_4) >= 9 by monotonicity. Two-level Karatsuba decomposition matches this at 9 multiplications.
The lower bound MC >= 8 for unrestricted circuits comes from Theorem A' at j = 1 (MF-147).
Artifact verification:
- Subspace sweep and search: wave1-gf16/m3_sweep_result.json, m3_filteroff_result.json, m3_gf16_hp0_result.json
- Recall controls: m3_control_s1..s7.json (7/7 planted 7-product recall controls recovered)
- Group symmetries: symmetry.py
- Polynomial closure and floors: polymul4_close.json, fullscan_floors.json
- Finisher verification: verify_finisher.json V4/V5/V7/V8 and REPORT.md §2.
Discussion
The result fixes the quadratic complexity at 9 AND gates under linear input combinations. The bilinear complexity of 9 is known from Karatsuba and Winograd; the register notes that novelty remains unverified for the stronger quadratic-model lower bound where operand mixing is permitted.
Unrestricted multiplicative complexity for GF(16) multiplication and polymul_4 remains open in [8, 9]. Closing this gap depends on the 3-form transfer conjecture (ML-076), which would imply unrestricted MC(GF(16) mult) = 9.
For everyone — the takeaway
What this means
Both GF(16) multiplication and 4-term binary polynomial multiplication need exactly 9 multiplication gates when gate inputs are linear combinations of the input bits. Mixing bits across operands cannot reduce the count below 9. Any circuit that computes these maps with only 8 multiplication gates must feed a nonlinear signal into at least one multiplication gate.
Attribution and prior art
Prior art: The value 9 is already known from Karatsuba and Winograd's bilinear theory. However, whether this bound is new under the stronger quadratic model, which allows multiplications to mix operands, has not been verified.
Register references
- Entry: MF-167
- Context and bounds: MF-147, ML-076
- Receipts: wave1-gf16/m3_sweep_result.json, m3_filteroff_result.json, m3_gf16_hp0_result.json, m3_control_s1..s7.json, symmetry.py, polymul4_close.json, fullscan_floors.json, verify_finisher.json (V4/V5/V7/V8), REPORT.md §2
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 8 of 9 receipt files bundled (15 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-09-04Published on this site.