Research · Papers · Adders, counters and the heap law · MF-150
Exact multiplicative complexity of 2×2 unsigned integer multiplier
MC(2×2 unsigned integer multiplier) = 4
Published 2026-09-04
For everyone
Plain summary
Multiplying two 2-bit numbers produces a 4-bit product. In circuit design and cryptography, addition modulo 2 (XOR) is cheap, while non-linear multiplication (AND) is expensive. Multiplicative complexity counts the minimum number of AND gates needed to evaluate a function.
This entry proves that a 2×2 unsigned integer multiplier requires exactly four non-linear multiplications. Three or fewer cannot compute it, and an explicit four-multiplication circuit computes all four output bits.
Small multipliers are common across arithmetic literature, so this decomposition is likely already documented. Check the NIST Circuits repository for prior art before citing this result as novel.
Result
For the 2×2 unsigned integer multiplier mapping four input bits (a0, a1, b0, b1) to four product bits (p0, p1, p2, p3):
MC(2×2 unsigned integer multiplier) = 4
The bound is exact: an analytic lower bound of 4 matches a fully verified four-multiplication circuit.
Setting and definitions
Let a = (a1, a0) and b = (b1, b0) be 2-bit unsigned integers with bits in GF(2), representing integers 2*a1 + a0 and 2*b1 + b0. The product is a 4-bit unsigned integer p = (p3, p2, p1, p0) representing 8*p3 + 4*p2 + 2*p1 + p0. The multiplicative complexity MC(f) is the minimum number of GF(2) multiplication gates required to compute the multi-output Boolean function f over the basis (XOR, NOT, AND).
Method
The lower bound is proved analytically without SAT solvers using Floor A:
- delta = 0.232421875
- -log2(delta)/log2(8/5) = 3.09, which rounds up to a lower bound of 4 multiplications.
The upper bound is given by an explicit four-multiplication straight-line program:
- t1 = a0 b0
- t2 = a1 b1
- t3 = (a0+a1)(b0+b1)
- t4 = t1 t2
The four product bits are linear combinations of these intermediate terms:
- p0 = t1
- p1 = t3+t1+t2
- p2 = t2+t4
- p3 = t4
This circuit was evaluated across all 16 input vectors in GF(2)^4 against the arithmetic specification, producing zero mismatches.
Artifact receipts:
- floors/family_sweep2.py
- out_family2.json (mult_2x2)
- replay_mult2.py
Evidence tiers: P (analytic lower floor) and FR (full replay verification for upper bound).
Discussion
Four multiplications are necessary and sufficient for the standard 2×2 unsigned integer multiplier over GF(2).
Prior art status is PARTIAL. Small integer multipliers are thoroughly documented in computer arithmetic literature, and this four-multiplication decomposition is likely present in existing catalogs. Consult the NIST Circuits repository before claiming novelty.
For everyone — the takeaway
What this means
A 2×2 unsigned integer product cannot run on three or fewer non-linear multiplications. The four-multiplication recipe gives an optimal structure for implementations where reducing non-linear gates is the primary design target.
Attribution and prior art
Prior art: This is a partial result, as small multipliers are well-studied and likely already known. Please check the NIST Circuits repository before external use.
Register references
- Entry: MF-150
- floors/family_sweep2.py
- out_family2.json (mult_2x2)
- replay_mult2.py
- NIST Circuits repository (noted in prior art)
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 3 receipt files bundled (5 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.