Research · Papers · Direct sums, wedges and the p14 frontier · MF-148
Exact unrestricted multiplicative complexity of 3-term binary polynomial multiplication
MC(polymul_3 over F2) = 6 in the unrestricted model
Published 2026-09-04
For everyone
Plain summary
Binary polynomial multiplication multiplies two polynomials whose coefficients are 0 or 1 without modular reduction. In hardware circuits, additions (XOR gates) cost very little area and power, while multiplications (AND gates) are expensive. Multiplicative complexity counts the minimum number of multiplications needed when additions are free.
Multiplying two 3-term binary polynomials takes 6 inputs and produces 5 outputs. The classical Karatsuba algorithm does this using 6 multiplications, but whether a 5-multiplication circuit existed under unrestricted circuit wiring remained an open question. Three independent mathematical proofs confirm that 5 multiplications are impossible, establishing that 6 multiplications is strictly optimal.
Result
Let polymul_3: GF(2)^3 × GF(2)^3 → GF(2)^5 be the 3-term binary polynomial multiplication operator mapping (a0 + a1*x + a2*x^2, b0 + b1*x + b2*x^2) to their product over GF(2). In the unrestricted XOR-free multiplicative complexity model:
MC(polymul_3 over F2) = 6.
Setting and definitions
The operator polymul_3 (or clmul_3) computes the degree-4 binary polynomial product from 6 inputs to 5 coordinate functions:
- c0 = a0*b0
- c1 = a0*b1 + a1*b0
- c2 = a0*b2 + a1*b1 + a2*b0
- c3 = a1*b2 + a2*b1
- c4 = a2*b2
The metric MC(f) is the unrestricted multiplicative complexity over GF(2), defined as the minimum number of two-input AND gates in a GF(2) XOR-and-inverter graph (XAG) computing f, with XOR and NOT gates available at zero cost.
The analysis evaluates a 3-dimensional component subspace V' in the output selection space, using the second-order rank sum invariant m_2(V') and component complexities mc(v) for nonzero v ∈ V'.
Method
The upper bound MC(polymul_3 over F2) ≤ 6 is realized by the classical 6-product Karatsuba/Toom decomposition:
- P0 = a0 * b0
- P1 = a1 * b1
- P2 = a2 * b2
- P01 = (a0 + a1) * (b0 + b1)
- P02 = (a0 + a2) * (b0 + b2)
- P12 = (a1 + a2) * (b1 + b2)
Outputs are reconstructed linearly:
- c0 = P0
- c1 = P01 + P0 + P1
- c2 = P02 + P0 + P2 + P1
- c3 = P12 + P1 + P2
- c4 = P2
This 6-AND circuit was verified over all 64 input assignments in GF(2)^6 by three independent execution seats, logged in polymul3_upper_replay.json.
The lower bound MC(polymul_3 over F2) ≥ 6 is established by three independent routes:
- Subspace rank geometry: Evaluating Theorem A′ at j = 1 on the 3-dimensional subspace V'. All seven nonzero linear classes in V' have mc = 3. Every 2-dimensional plane in V' sums to 9, yielding m_2(V') ≥ 5. Theorem A′ then forces MC ≥ 6. Validated in
geometry/replay_polymul3.py(SHA-256047ea83d…0ce907). - Floor analysis: Floor A (MF-135) gives spectral discrepancy delta = 0.0859375, producing the bound ceil(5.22) = 6. Verified in
floors/replay_clmul3.py,out_family2.json, andfullscan_floors.json. - Field embedding: The subspace V' is a linear image of the GF(8) class space. The lower bound of 6 follows from the multiplicative complexity of multiplication in GF(8) (MF-128) reduced modulo x^3 + x + 1. Component bounds via MF-137 reach only 5; the higher-order structure of V' lifts the bound to 6. Certified in
wave1-gf16/verify_finisher.jsonV3.
Discussion
Standard Karatsuba formulas and NIST benchmark suites use 6 multiplications for 3-term binary polynomial multiplication, but prior work did not establish whether unrestricted linear feedback or arbitrary output mixing could reach 5.
Single-component bounds (such as MF-137) stop at 5. Closing the gap requires the higher-dimensional subspace geometry of V' or Floor A discrepancy analysis. The convergence of all three methods (Theorem A′ on V', Floor A discrepancy, and the GF(8) embedding reduction from MF-128) proves that 6 multiplications is the exact lower bound in the unrestricted model.
For everyone — the takeaway
What this means
This settles the exact multiplication cost for 3-term binary polynomial multiplication. Cryptographic and hardware designs commonly rely on 6-multiplication formulas for degree-2 binary polynomials. This result proves that no circuit can reduce the multiplication count to 5, even with free additions and arbitrary wiring. Designers can focus on optimizing additions, routing, and latency around the standard 6-multiplication core without searching for smaller multiplier counts.
Attribution and prior art
Prior art: This is a known value obtained using classical Karatsuba multiplication for the NIST binary-polynomial category. It remains only a partial result regarding exactness in an unrestricted model.
Register references
- Register entry: MF-148
- Prior art: Classical Karatsuba; NIST binary-polynomial category
- Connected register entries: MF-128, MF-135, MF-137
- Receipt artifacts:
geometry/replay_polymul3.py(SHA-256047ea83d…0ce907)polymul3_upper_replay.jsonfloors/replay_clmul3.pyout_family2.jsonwave1-gf16/verify_finisher.json(V3)fullscan_floors.json
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 6 of 6 receipt files bundled (6 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.