Exact multiplicative complexity of GF(16) inversion and bounds for GF(32)

Result

For inversion in GF(2^4), mapped as x -> x^14 on F2[x]/(x^4+x+1) with 0 -> 0: MC(GF(2^4) inversion) = 5 (UNRESTRICTED)

The upper bound is achieved by an explicit 5-product Boolean circuit evaluating input bits (x0, x1, x2, x3) to output bits (y0, y1, y2, y3): g1 = (1+x0)(1+x1) g2 = (x0+x1+x2)(1+x3+g1) g3 = (1+x0+x2+x3)(x1+x2+g1) g4 = (1+x2+x3)(1+x2+g3) g5 = (x1+x2+g2+g3)(1+x0+x3+g4)

y0 = 1+x0+x1+x2+g5 y1 = x0+x2+g1+g2+g3 y2 = 1+x1+x2+x3+g1+g4 y3 = 1+x0+x2+g2+g5

For inversion in GF(2^5), mapped as x -> x^30 modulo 0b100101 (x^5+x^2+1) with 0 -> 0: MC(GF(2^5) inversion) ∈ [7, 14]

The Itoh–Tsujii decomposition stages x -> x^3 and w -> w^5 satisfy: qMC(x^3) = 7 qMC(x^5) = 7 MC(x^3) ∈ [6, 7] MC(x^5) ∈ [6, 7]

The composed inverter x^-1 = ((x^3)^5)^2 requires 14 AND gates, as squarings over GF(2) are linear coordinate projections.

Setting and definitions

Let GF(2^n) denote the Galois field of order 2^n. Field inversion maps x -> x^(2^n - 2) with 0 -> 0. The multiplicative complexity MC(f) of a multi-output Boolean function f: GF(2)^n -> GF(2)^m is the minimum number of two-input AND gates required to compute f in a straight-line program over {AND, XOR, NOT}. The quadratic multiplicative complexity qMC(f) restricts non-input gate operands to linear combinations of original inputs and preceding product gates under quadratic constraints.

Linear equivalence preserves multiplicative complexity: an invertible linear coordinate change L applied to inputs or outputs leaves MC(f) invariant.

Under the MF-137 lower-bound framework, bounds depend on the dimension of the coordinate span dim V and the invariant mu, which denotes the minimum multiplicative complexity across all nonzero linear combinations of the coordinate functions.

Method

GF(16) inversion:

1. Lower bound: Proved via MF-137. The output coordinate space has dim V = 4, with no affine nonzero linear combinations. Enumeration of all 1,152 Boolean functions on 4 variables with MC <= 1 shows that none of the 15 nonzero output combinations has MC <= 1. Hence mu = 2, forcing MC >= 5.
2. Upper bound: Constructed via the 5-product straight-line program above. The circuit was simulated across all 16 field elements and validated against the algebraic lookup table in two independent runs, including a replay from re-parsed equations.

GF(32) inversion:

1. Lower bound: The output space has dim V = 5. All 31 nonzero linear combinations of the coordinate functions have algebraic degree 4, yielding mu >= 3 under MF-137 and proving MC >= 7.
2. Stage decomposition: Factored via the Itoh–Tsujii algorithm into x^-1 = ((x^3)^5)^2. The maps x -> x^3 and w -> w^5 are quadratic vector functions from GF(2)^5 to GF(2)^5.
3. Search: mcbfs.py conducted an exhaustive search over quadratic circuits. The search exhausted without solutions at bound B = 6 and succeeded at B = 7, establishing qMC(x^3) = 7 and qMC(x^5) = 7, with unrestricted complexities MC(x^3), MC(x^5) ∈ [6, 7].
4. Composition: Explicit 7-product circuits were extracted for both stages using extract_inv.py and gf32_circuit.py. Squaring operations are linear in GF(2) and cost zero AND gates. Composing both stages yielded an explicit 14-AND circuit, verified against the truth table for all 32 inputs.

Discussion

The result MC(GF(16) inversion) = 5 is unrestricted and basis-independent; basis changes do not alter the 5-AND count. Because the inversion polynomial x^14 has algebraic degree 3, the result is not constrained by quadratic-model assumptions.

GF(16) inversion underlies tower-field implementations of the AES S-box, analyzed by Canright (2005) and Boyar–Peralta (2010). Stoffelen (FSE 2016) reported a 5-AND circuit using SAT methods; this entry records a formal confirmation cell within the registry.

For GF(32), unrestricted complexity lies in [7, 14]. While the two-stage Itoh–Tsujii pipeline uses 14 AND gates, an unconstrained monolithic circuit could potentially achieve 12 or 13 gates. The novelty of the individual GF(32) stage bounds (qMC = 7) remains unverified in the wider literature.

Evidence classifications:

• GF(16): Proved (P) lower bound, Fully Replayed (FR) upper bound.
• GF(32): Proved (P) lower bound, Fully Certified (FC) stage pricing via exhaustive BFS, Fully Replayed (FR) 14-AND upper bound.

Attribution and prior art

Prior art: GF(16) inversion is the core of tower-field AES S-boxes (Canright 2005; Boyar–Peralta 2010), with Stoffelen’s SAT study of 4-bit S-boxes (FSE 2016) confirming the inverter cost at 5. The novelty of the GF(32) stage cost remains unverified.

Register references

• Register Entry: MF-168
• Related Framework: MF-137
• Prior Art References:
• Canright, D. (2005)
• Boyar, J., Peralta, R. (2010)
• Stoffelen, K. (FSE 2016)
• Artifacts and Scripts:
• wave1-gf16/gf16_inv_circuit.json
• verify_finisher.json (V1/V2)
• mcbfs.py
• extract_inv.py
• inversion_profile.json
• gf32_inv.json
• gf32_circuit.py
• gf32_inv_circuit.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 8 of 8 receipt files bundled (11 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.

Download evidence.zip

Related in this programme

• MF-167
  Exact quadratic multiplicative complexity of GF(2^4) multiplication and polymul_4
• MF-176
  Exact multiplicative complexity of all 16 optimal 4-bit S-box classes and standard ciphers
• MF-156
  The k-window law for joint multiplicative complexity of Chi iterates
• MF-154
  Exact multiplicative complexity of chi_5^2