# P2436: Least trinomial multiple of a primitive degree-61 polynomial

- ID: `P2436`
- Reference: `primitive-degree61-trinomial-multiple`
- Page: https://theoremdb.org/statements/P2436
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(f(x)=x^{61}+x^{45}+x^{32}+x^2+1\in\mathbb F_2[x]\). Find the least \(b\le 2^{31}\) for which there is an integer \(a\) with \(0<a<b\) and \(f(x)\mid x^b+x^a+1\), or certify that no such \(b\) exists in this range.

### Remarks

- **Remark.** All divisibility and polynomial arithmetic take place over F_2.
- **Remark.** The polynomial f is irreducible. Since 2^61-1 is prime, a root of f generates the multiplicative group of F_(2^61).

### What counts as a solution

- Exhibit the least pair (a,b) with b <= 2^31 and verify the polynomial division, or give a complete exact certificate that no pair exists.

## Status

Exact residue search excludes every trinomial multiple with \(0<a<b\le2^{28}\); existence and the least pair in the remaining range \(2^{28}<b\le2^{31}\) remain open. [2](#reference-2)

## Work

### Evidence for the current status

**Computation 1 (No trinomial multiple occurs through degree 2^28).** Exact residue search excludes every trinomial multiple with \(0<a<b\le2^{28}\); existence and the least pair in the remaining range \(2^{28}<b\le2^{31}\) remain open.

Let \(\alpha\) be the residue class of \(x\) in
\[
\mathbf F_2[x]/(x^{61}+x^{45}+x^{32}+x^2+1).
\]
For \(0<a<b\), divisibility by \(f\) is equivalent to
\[
\alpha^b+\alpha^a+1=0,
\]
or \(\alpha^a=\alpha^b+1\).

The certificate stores every tagged residue \((\alpha^a,a)\) for
\[
1\leq a<2^{28}.
\]
It then tests \(\alpha^b+1\) in increasing order for every \(1\leq b\leq2^{28}\), scans the complete bucket containing that residue, and accepts only a matching tag with \(a<b\). It inspected 536,886,339 packed records and found no match. Thus
\[
f(x)\nmid x^b+x^a+1
\]
for every \(0<a<b\leq268435456\).

This proves one eighth of the requested degree interval. The 1,879,048,192 possible values of \(b\) satisfying \(2^{28}<b\leq2^{31}\) remain outside the certified search.

### Background and intake notes

The natural linear scan has a tiny state update and a difficult membership problem at the full bound. The checked prefix supplies a reproducible baseline without suggesting that the remaining interval is empty.

- Original intake status: Status remains unverified. The question is a bounded Zech-logarithm search in a field too large for a full logarithm table.
- Represent powers of a root by 61-bit residues modulo f. At exponent b, a solution exists exactly when the residue of x^b+1 has appeared at an earlier positive exponent.
- A complete certificate can use sorted blocks, collision-resistant block digests, and a final exact replay of any hit. Storing all residues through 2^31 at once is unnecessary.

- Recorded example: Modulo f, multiplication by x shifts the 61-bit state and xors bits 45, 32, 2, and 0 when the leading bit is set.

### Other known results

- **Computation 2** (reproduced): Rabin's irreducibility criterion and a Lucas-Lehmer certificate show that a root has order 2^61-1. [1](#reference-1)

### Prior approaches

- **Route 1** (supported): Published methods explain the Zech-logarithm search, while the exact least pair and the rest of the requested interval remain unsettled here. [2](#reference-2)

### Runnable artifacts

- **Artifact 1** (reproduced): A C program stores 268,435,455 exponent-tagged residues and searches every target through b=2^28.
- **Artifact 2** (reproduced): Standard-library Python checks the degree-61 Frobenius criterion and the Lucas-Lehmer sequence.

### Computational notes

- SymPy independently reported f irreducible over F_2.
- An exact residue scan found no solution for 1 <= b <= 2000000. It retained 2000000 distinct states, with 64-bit sum checksum 1784604806080276685 and final state 2021773856510245769.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `primitive-degree61-trinomial-multiple`, 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>P. Peterlongo, M. Sala, and C. Tinnirello, “A Discrete Logarithm-based Approach to Compute Low-Weight Multiples of Binary Polynomials”. Finite Fields and their Applications, 2016, vol. 38, p. 57-71. DOI 10.1016/j.ffa.2015.12.005. arXiv:1411.4024 (2014). The field-root and Zech-logarithm formulation appears in Peterlongo, Sala, and Tinnirello, section 2; exact irreducibility and Lucas-Lehmer replay in ptm61-artifact-field-verification https://arxiv.org/abs/1411.4024
   - preprint; primary source; arXiv:1411.4024, version checked 2026-07-24; checked 2026-08-01
   - Source use: original_summary
   - For Least trinomial multiple of a primitive degree-61 polynomial: The stated polynomial gives a primitive degree-61 field model. Rabin's irreducibility criterion and a Lucas-Lehmer certificate show that a root has order 2^61-1.
2. <a id="reference-2"></a>Frédéric Didier and Yann Laigle-Chapuy, “Finding low-weight polynomial multiples using discrete logarithm”. Dans IEEE International Symposium on Information Theory - ISIT'07 (2007). arXiv:cs/0701069 (2007). Frédéric Didier and Yann Laigle-Chapuy, Finding low-weight polynomial multiples using discrete logarithm, ISIT 2007, arXiv:cs/0701069; P. Peterlongo, M. Sala, and C. Tinnirello, A Discrete Logarithm-based Approach to Compute Low-Weight Multiples of Binary Polynomials, arXiv:1411.4024, section 2 and equation (6); Subhamoy Maitra, Kishan Chand Gupta, and Ayineedi Venkateswarlu, Theoretical Computer Science 341 (2005), 311-343, DOI 10.1016/j.tcs.2005.04.011; Mark Giesbrecht, Daniel Roche, and Hrushikesh Tilak, Computing sparse multiples of polynomials, arXiv:1009.3214 https://arxiv.org/abs/cs/0701069
   - Also cited at Exact exhaustive computation in ptm61-artifact-bucket-exclusion-2pow28, executed on 2026-07-24
   - preprint; primary source; arXiv:cs/0701069, version checked 2026-07-24; checked 2026-08-01
   - Source use: original_summary
   - For Least trinomial multiple of a primitive degree-61 polynomial: The interval above 2^28 remains open in this entry. Published methods explain the Zech-logarithm search, while the exact least pair and the rest of the requested interval remain unsettled here.
   - Source named by the research packet.