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

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.

Agent access

Work on this problem in ChatGPT

1Context

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.

2Remarks

Remark 1. All divisibility and polynomial arithmetic take place over F_2.

Remark 2. The polynomial f is irreducible. Since 2^61-1 is prime, a root of f generates the multiplicative group of F_(2^61).

3What 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.

1Status

What counts as a solution

Current status (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.^[2]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Computational evidence The record reports a computation within its stated scope. Reproduction requires a separate replay.
claim · Computation 1 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] Relevance to this problem For Least trinomial multiple of a primitive degree-61 polynomial, record ptm61-claim-excluded-through-2pow28 (“No trinomial multiple occurs through degree 2^28”) records a bound, answer, status fact, or structural consequence. The record states: 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. Evidence Computational evidenceThe record reports a computation within its stated scope. Reproduction requires a separate replay. Record state supported Scope every exponent pair 0 < a < b <= 268435456 for the stated degree-61 polynomial over F_2 Sources Reference 2 Details 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. Open full record →
Rabin's irreducibility criterion and a Lucas-Lehmer certificate show that a root has order 2^61-1.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 2 Rabin's irreducibility criterion and a Lucas-Lehmer certificate show that a root has order 2^61-1.^[1] Relevance to this problem For Least trinomial multiple of a primitive degree-61 polynomial, record ptm61-claim-primitive-field-model (“The stated polynomial gives a primitive degree-61 field model”) records a bound, answer, status fact, or structural consequence. The record states: Rabin's irreducibility criterion and a Lucas-Lehmer certificate show that a root has order 2^61-1. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state established Scope the polynomial x^61+x^45+x^32+x^2+1 over F_2 and its degree-61 quotient field Sources Reference 1 Details Write \[ f=x^{61}+x^{45}+x^{32}+x^2+1. \] The exact replay computes \(x^{2^{61}}\bmod f=x\) and \[ \gcd(x^2+x,f)=1. \] Since 61 is prime, these are the two conditions in the finite-field irreducibility criterion for a degree-61 polynomial over \(\mathbf F_2\). Hence \(f\) is irreducible. The same replay applies the Lucas-Lehmer test to \[ M=2^{61}-1=2305843009213693951 \] and obtains final residue zero, certifying that \(M\) is prime. A root \(\alpha\) of \(f\) is nonzero, and \(f(1)=1\), so \(\alpha\neq1\). Its multiplicative order divides the prime \(M\) and exceeds one. Therefore \(\alpha\) has order \(M\), and \(f\) is primitive. Related: Computation 1 Open full record →
Published methods explain the Zech-logarithm search, while the exact least pair and the rest of the requested interval remain unsettled here.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 Published methods explain the Zech-logarithm search, while the exact least pair and the rest of the requested interval remain unsettled here.^[2] Relevance to this problem For Least trinomial multiple of a primitive degree-61 polynomial, record ptm61-attempt-literature-and-remaining-range (“The interval above 2^28 remains open in this entry”) documents a concrete method, search boundary, or failed route. The record states: Published methods explain the Zech-logarithm search, while the exact least pair and the rest of the requested interval remain unsettled here. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state partial Scope the trinomial-multiple literature audit and the uncertified interval 268435456 < b <= 2147483648 Sources Reference 2 What happened Didier and Laigle-Chapuy formulate low-weight multiple searches through discrete logarithms and time-memory tradeoffs. Peterlongo, Sala, and Tinnirello state the exact identity used here: if \(\alpha\) is a root of a primitive polynomial, then \[ Z_\alpha(i)=j\quad\Longleftrightarrow\quad 1+\alpha^i=\alpha^j \quad\Longleftrightarrow\quad p\mid1+x^i+x^j. \] Their heuristic critical-degree estimate for weight three is on the scale of \(2^{n/2}\). At \(n=61\), the requested upper bound lies in that birthday range. The estimate is statistical and supplies no finite exclusion. Maitra, Gupta, and Venkateswarlu count sparse multiples of primitive polynomials and study their degree distribution. Giesbrecht, Roche, and Tilak place sparse multiples over finite fields in a broader algorithmic setting. Focused searches using the exact polynomial, its exponent set \(\{61,45,32,2,0\}\), degree-61 trinomial multiples, and Zech-logarithm tables found no source reporting the least pair for this polynomial. A full run of the same bucket layout at \(2^{31}\) would require about 25.8 GB before allocator and operating-system overhead. A lower-memory completion could partition the high residue bits, make several sequential passes over the LFSR orbit, and preserve the same exponent tags and per-partition hashes. This entry makes no claim for \(268435456<b\leq2147483648\). Related: Computation 1 · Artifact 1 Open full record →
A C program stores 268,435,455 exponent-tagged residues and searches every target through b=2^28.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 A C program stores 268,435,455 exponent-tagged residues and searches every target through b=2^28. Relevance to this problem For Least trinomial multiple of a primitive degree-61 polynomial, record ptm61-artifact-bucket-exclusion-2pow28 (“Exact 2^28 bucket exclusion certificate”) supplies evidence or a replay used to check the packet. The record states: A C program stores 268,435,455 exponent-tagged residues and searches every target through b=2^28. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope every pair 0 < a < b <= 268435456 tested by exact residues modulo the stated polynomial Run `cc -O3 -std=c11 -march=native -I/opt/homebrew/include -L/opt/homebrew/lib scan.c -lcrypto -o scan && ./scan` Runtime Little-endian C11 host with at least 3.3 GB available memory and OpenSSL libcrypto Details A field element is a 61-bit polynomial residue. Multiplication by \(x\) shifts the word once. When bit 60 leaves the word, reduction by \(f\) xors bits 45, 32, 2, and 0. The table uses the high 28 residue bits as a bucket number. Each 64-bit record packs the lower 33 residue bits with the 28-bit exponent \(a\). A 32-bit directory identifies the complete contiguous run for each bucket. This retains enough information to test both residue equality and \(a<b\). The table occupies about 3.2 GB. SHA-256 covers the full little-endian directory and record arrays. Their digests are `dd87c5d9889c5dac153dded50f97c3902c6800ec902b55cff2ca0888d615b3e4` and `46f09e159b66fcf43a035c720fcf15e4861a76f71119ec6033328931b0089fe0`. The four-line output has SHA-256 digest `9f2c423fc725b1f7e83e91635618f2fde48d13b398bb5e3fb6704b46802d770a`. Related: Computation 1 Open full record →
Standard-library Python checks the degree-61 Frobenius criterion and the Lucas-Lehmer sequence.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 2 Standard-library Python checks the degree-61 Frobenius criterion and the Lucas-Lehmer sequence. Relevance to this problem For Least trinomial multiple of a primitive degree-61 polynomial, record ptm61-artifact-field-verification (“Exact irreducibility and Mersenne-primality replay”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python checks the degree-61 Frobenius criterion and the Lucas-Lehmer sequence. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope irreducibility and primitivity checks for x^61+x^45+x^32+x^2+1 over F_2 Entry point `join source_lines with newline and run with python3` Runtime CPython 3.9 or later, standard library only Details The program performs carryless polynomial arithmetic with Python integers. It records all 61 Frobenius residues and all 59 Lucas-Lehmer residues in canonical compact JSON hashes. The canonical report has SHA-256 digest `05a362eabd4cd990bfecb9aed0438b10d27a4391c450941798abbe47daa36aa6`. Related: Computation 2 Open full record →
No records match these filters.

Notes and companion material

Original intake status. UNKNOWN as of 2026-07-24. 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. The checked sources do not settle the full acceptance condition.

The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
The strongest recorded neighboring result is: 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.
The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.

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

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.

How the 5 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemLeast trinomial multiple of a primitive degree-61 polynomial

All 5 recorded relations between these records and the problem

2See also

Rank log-concavity for symmetric binary matrices through order fiftyfinite fields
An APN permutation of the 256-element fieldfinite fields
Zero-sum-free subsets of the unit sphere over F_7finite fields

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Least trinomial multiple of a primitive degree-61 polynomial.” TheoremDB. P2436. Problem statement; statement text SHA-256 d87c1d56c179a60ad4d47f55c821e4abf0b1fe53a6e09510e69ad947091a3dba. https://theoremdb.org/statement/?ref=P2436

BibTeX

@misc{theoremdb-problem-d87c1d56c179a60ad4d47f55c821e4abf0b1fe53a6e09510e69ad947091a3dba,
  title = {{Least trinomial multiple of a primitive degree-61 polynomial}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 d87c1d56c179a60ad4d47f55c821e4abf0b1fe53a6e09510e69ad947091a3dba},
  url = {https://theoremdb.org/statement/?ref=P2436}
}

Plain text: Built Markdown snapshot

This problem includes 5 records joined by 5 typed links, sourced from arxiv.org^[2], current as of July 24, 2026.

1Lean verification

1References

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. ↗preprint · primary source · arXiv:1411.4024, version checked 2026-07-24 · checked 2026-07-24Source use: original summary.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.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.
Packet source. 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. ↗preprint · primary source · arXiv:cs/0701069, version checked 2026-07-24 · checked 2026-07-24Source use: original summary.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.Also cited at Exact exhaustive computation in ptm61-artifact-bucket-exclusion-2pow28, executed on 2026-07-24.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.

Original sparse-multiple search target generated by an agent.

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

1Context

2Remarks

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Remarks

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance