# P2654: Densest inverse of a weight-five binary cyclic polynomial

- ID: `P2654`
- Reference: `weight-five-cyclic-inverse-127`
- Page: https://theoremdb.org/statements/P2654
- Record maturity: Reviewed problem with recorded work

## Problem

Among all units \(f=1+x^a+x^b+x^c+x^d\) in \(\mathbb F_2[x]/(x^{127}+1)\), with \(1\le a<b<c<d\le126\), determine the maximum Hamming weight of \(f^{-1}\).

### Problem setup

- **Definition.** A unit is a residue class relatively prime to x^127+1.
- **Remark.** Every residue class is represented by a polynomial of degree below 127, and its Hamming weight is its number of nonzero coefficients.

### What counts as a solution

- Give a weight-five unit whose inverse attains the maximum and an exact sweep of all 10009125 normalized supports, with replayable polynomial products.

## Status

An explicit unit gives 85, while a complement argument gives the universal upper bound 101.

## Work

### Evidence for the current status

**Computation 1 (The maximum inverse weight lies between 85 and 101).** An explicit unit gives 85, while a complement argument gives the universal upper bound 101.

Let \(M\) be the requested maximum. The support
\[
\{0,45,49,53,94\}
\]
has the inverse displayed in `wfci127-claim-weight-85-witness`, so \(M\geq85\). The argument in `wfci127-claim-complement-upper-bound` proves \(M\leq101\). Therefore
\[
85\leq M\leq101.
\]
Both endpoints are odd, as every inverse of an odd-weight polynomial evaluates to 1 at \(x=1\). The exact maximum remains open in this fixture. Its complete normalized search space has
\[
\binom{126}{4}=10{,}009{,}125
\]
supports.

### Background and intake notes

Each support is an independent search item and every incumbent has a 127-bit multiplication certificate.

- Original intake status: Status remains unverified. Sparse inverses in binary cyclic rings are studied in coding and cryptographic settings, but this normalized instance may lack a published exhaustive value.
- There are exactly C(126,4)=10009125 normalized supports. Use binary extended gcd for each unit and retain the full support and inverse for every new record.
- Trap: x^127+1 equals x^127-1 in characteristic two. Integer-polynomial signs and ordinary multiplication give wrong unit and inverse tests.

- Recorded example: The support {0,45,49,53,94} has inverse 0x3bf17593bf175d3fb175d3fb377f3fb3 of weight 85.

### Other known results

- **Computation 2** (reproduced): Exact cyclic multiplication verifies the supplied 127-bit inverse. [1](#reference-1)
- **Computation 3** (reproduced): The complement of an inverse must have at least 26 nonzero coefficients.
- **Claim 1** (supported): Coding-based cryptography uses the same binary circulant ring and sparse factors, while the cited papers do not tabulate this length-127 extremum. [1](#reference-1) [2](#reference-2)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python checks both product identities, both weights, and the complement upper-bound arithmetic.
- **Artifact 2** (reproduced): A standard-library program enumerates every support and computes inverses by binary polynomial Euclid, with a streaming result checksum.

### Computational notes

- Exact carryless multiplication of the displayed polynomials reduces to 1 modulo x^127+1, so the current lower bound is 85. Since f(1)=1, every inverse has odd weight. Weight 127 would be the all-one polynomial, whose product with f is again all-one, giving the upper bound 125.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `weight-five-cyclic-inverse-127`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier, and Paulo S. L. M. Barreto, “MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes,” IACR ePrint 2012/409. Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier, and Paulo S. L. M. Barreto, MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes, IACR ePrint 2012/409, sections 2 and 3; Qian Guo, Thomas Johansson, and Paul Stankovski, A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors, ASIACRYPT 2016, IACR ePrint 2016/858, discussion of binary circulant rank and polynomial coprimality; Misoczki et al., sections 2 and 3 https://eprint.iacr.org/2012/409
   - Also cited at Misoczki et al., sections 2 and 3
   - Also cited at wfci127-artifact-exact-witness-verifier, executed 2026-07-25
   - website; reference source; web version checked 2026-07-25; checked 2026-07-25
   - Source use: citation_only
   - For Densest inverse of a weight-five binary cyclic polynomial: The exact normalized extremum was not located in the audited literature. Coding-based cryptography uses the same binary circulant ring and sparse factors, while the cited papers do not tabulate this length-127 extremum.
   - Source named by the research packet.
2. <a id="reference-2"></a>Qian Guo, Thomas Johansson, and Paul Stankovski, “A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors,” IACR ePrint 2016/858; ASIACRYPT 2016. Guo, Johansson, and Stankovski, binary circulant rank and coprimality discussion https://eprint.iacr.org/2016/858
   - website; reference source; web version checked 2026-07-25; checked 2026-07-25
   - Source use: citation_only
   - For Densest inverse of a weight-five binary cyclic polynomial: The exact normalized extremum was not located in the audited literature. Coding-based cryptography uses the same binary circulant ring and sparse factors, while the cited papers do not tabulate this length-127 extremum.