{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R608",
  "content_hash": null,
  "slug": "ptm61-artifact-field-verification",
  "type": "artifact",
  "title": "Exact irreducibility and Mersenne-primality replay",
  "summary": "Standard-library Python checks the degree-61 Frobenius criterion and the Lucas-Lehmer sequence.",
  "relevance": "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.",
  "relevance_source": "recorded",
  "body": "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`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "irreducibility and primitivity checks for x^61+x^45+x^32+x^2+1 over F_2",
    "bounds": {
      "polynomial_degree": {
        "min": 61,
        "max": 61
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_python_computation",
    "entrypoint": "join source_lines with newline and run with python3",
    "runtime": "CPython 3.9 or later, standard library only",
    "citation": {
      "url": "https://arxiv.org/abs/cs/0701069",
      "locator": "Inline standard-library Python computation executed by TheoremDB entry research on 2026-07-24"
    },
    "outputs": "{\"degree\":61,\"frobenius_final\":2,\"frobenius_trace_sha256\":\"2079632c44212fb602408d58f54da31acadb7ea40c491e60527341bd8f3c0643\",\"lucas_lehmer_final\":0,\"lucas_lehmer_trace_sha256\":\"2e7a0da6c44ee83d3dfb22087c020dde27395841a7d31e3e639a9b9411058076\",\"mersenne\":2305843009213693951,\"polynomial_bits\":2305878197880750085,\"x2_plus_x_gcd\":1}\n",
    "inline_source": [
      "import hashlib",
      "import json",
      "",
      "F = (1 << 61) | (1 << 45) | (1 << 32) | (1 << 2) | 1",
      "",
      "def degree(p):",
      "    return p.bit_length() - 1",
      "",
      "def poly_mod(p, divisor=F):",
      "    d = degree(divisor)",
      "    while degree(p) >= d:",
      "        p ^= divisor << (degree(p) - d)",
      "    return p",
      "",
      "def multiply_mod(a, b):",
      "    product = 0",
      "    while b:",
      "        if b & 1:",
      "            product ^= a",
      "        b >>= 1",
      "        a <<= 1",
      "    return poly_mod(product)",
      "",
      "def poly_gcd(a, b):",
      "    while b:",
      "        a, b = b, poly_mod(a, b)",
      "    return a",
      "",
      "frobenius = 2",
      "frobenius_trace = []",
      "for _ in range(61):",
      "    frobenius = multiply_mod(frobenius, frobenius)",
      "    frobenius_trace.append(frobenius)",
      "assert frobenius == 2",
      "assert poly_gcd((1 << 2) | (1 << 1), F) == 1",
      "",
      "mersenne = (1 << 61) - 1",
      "lucas = 4",
      "lucas_trace = []",
      "for _ in range(59):",
      "    lucas = (lucas * lucas - 2) % mersenne",
      "    lucas_trace.append(lucas)",
      "assert lucas == 0",
      "",
      "compact = lambda value: json.dumps(value, separators=(',', ':'))",
      "report = {",
      "    'polynomial_bits': F,",
      "    'degree': 61,",
      "    'frobenius_final': frobenius,",
      "    'frobenius_trace_sha256': hashlib.sha256(compact(frobenius_trace).encode()).hexdigest(),",
      "    'x2_plus_x_gcd': 1,",
      "    'mersenne': mersenne,",
      "    'lucas_lehmer_final': lucas,",
      "    'lucas_lehmer_trace_sha256': hashlib.sha256(compact(lucas_trace).encode()).hexdigest(),",
      "}",
      "payload = json.dumps(report, sort_keys=True, separators=(',', ':'))",
      "assert hashlib.sha256(payload.encode()).hexdigest() == '05a362eabd4cd990bfecb9aed0438b10d27a4391c450941798abbe47daa36aa6'",
      "print(payload)"
    ],
    "missing": [
      "command"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/cs/0701069",
    "locator": "Inline standard-library Python computation executed by TheoremDB entry research on 2026-07-24"
  },
  "models": [],
  "relations": [
    {
      "slug": "R611",
      "title": "The stated polynomial gives a primitive degree-61 field model",
      "object_type": "claim",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "primitive-degree61-trinomial-multiple",
      "title": "primitive degree61 trinomial multiple",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}