Fewest AND gates for field multiplication

Task

Write multiplication in GF(2^m) as a bilinear algorithm, c = Σ_k (u_k·a)(v_k·b) w_k, and minimize the number of products. Use the modulus P_m specified in the instance file. The T gate problem uses the same moduli.

Submission file

JSON structure:

{"m": 4, "U": ["1000", ...], "V": ["1000", ...], "W": ["100000000", ...]}

This shows the file structure. The verifier bundle contains a valid example.

• U and V have r rows, each a bit string of length m. Character i of U[k] is the coefficient of a_i in the k-th left linear form; V[k] does the same for b.
• W has m rows, each a bit string of length r. W[l][k] specifies whether product k contributes to output coefficient l.
• Use at most m² products.

Validation

The submission is valid if and only if Σ_k U[k][i] V[k][j] W[l][k] = T_ijl (mod 2) for all i, j and l, where T_ijl is the coefficient of x^l in x^i+j mod P_m. The verifier checks all m³ entries.

Scoring

The score is the number of products r. Fewer products rank first. For equal product counts, fewer XOR operations rank first, then the earlier submission. The XOR count is Σ (row weight − 1) over the nonzero rows of U, V and W; it is computed separately for each linear form, without reusing intermediate sums. The demo has no limit on the XOR count.

Baseline and reference scores

Sources: Barbulescu, Detrey, Estibals and Zimmermann (ePrint 2012/110); Ballet et al., survey arXiv:1906.07456, Tables 1 and 2. For m ≤ 6 the minimum product count is proved, so equal product counts are ranked by XOR count. The bilinear rank does not depend on the choice of modulus; the XOR count does.

Application

Each bilinear product can be implemented with a Toffoli gate. These multipliers are used in field inversion and point addition in Shor's algorithm for elliptic curves over binary fields.

Current records

Reference scores come from cited papers or derived constructions. Only accepted submissions can hold a QArena record.