{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R607",
  "content_hash": null,
  "slug": "ptm61-artifact-bucket-exclusion-2pow28",
  "type": "artifact",
  "title": "Exact 2^28 bucket exclusion certificate",
  "summary": "A C program stores 268,435,455 exponent-tagged residues and searches every target through b=2^28.",
  "relevance": "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.",
  "relevance_source": "recorded",
  "body": "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.\n\nThe 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.\n\nSHA-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`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "every pair 0 < a < b <= 268435456 tested by exact residues modulo the stated polynomial",
    "bounds": {
      "b": {
        "min": 1,
        "max": 268435456
      },
      "stored_positive_powers": {
        "min": 268435455,
        "max": 268435455
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "complete",
    "kind": "inline_c_computation",
    "command": "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",
    "citation": {
      "url": "https://arxiv.org/abs/cs/0701069",
      "locator": "Inline C11 and OpenSSL computation executed by TheoremDB entry research on 2026-07-24"
    },
    "outputs": "limit=268435456 states=268435455 state_sum_mod_2^64=15183333062782668587 final_a_state=2011766183670121759\nstarts_sha256_le=dd87c5d9889c5dac153dded50f97c3902c6800ec902b55cff2ca0888d615b3e4\nrecords_sha256_le=46f09e159b66fcf43a035c720fcf15e4861a76f71119ec6033328931b0089fe0\ninspected=536886339 found=0 final_b_state=1717654178049428027\n",
    "runtime_seconds": 12,
    "inline_source": [
      "#include <inttypes.h>",
      "#include <openssl/sha.h>",
      "#include <stdint.h>",
      "#include <stdio.h>",
      "#include <stdlib.h>",
      "#include <string.h>",
      "",
      "#define BITS 28",
      "#define LIMIT (UINT64_C(1) << BITS)",
      "#define COUNT (LIMIT - 1)",
      "#define LOW_BITS (61 - BITS)",
      "#define LOW_MASK ((UINT64_C(1) << LOW_BITS) - 1)",
      "",
      "static inline uint64_t advance(uint64_t state) {",
      "    const uint64_t mask = (UINT64_C(1) << 61) - 1;",
      "    const uint64_t feedback = (UINT64_C(1) << 45) | (UINT64_C(1) << 32) |",
      "                              (UINT64_C(1) << 2) | 1;",
      "    uint64_t top = state >> 60;",
      "    state = (state << 1) & mask;",
      "    return state ^ (feedback & (UINT64_C(0) - top));",
      "}",
      "",
      "static void sha256_hex(const void *data, size_t bytes, char out[65]) {",
      "    unsigned char digest[SHA256_DIGEST_LENGTH];",
      "    SHA256(data, bytes, digest);",
      "    for (size_t i = 0; i < sizeof digest; ++i)",
      "        sprintf(out + 2 * i, \"%02x\", digest[i]);",
      "    out[64] = '\\0';",
      "}",
      "",
      "int main(void) {",
      "    uint16_t endian = 1;",
      "    if (*(unsigned char *)&endian != 1) return 2;",
      "    uint32_t *starts = calloc((size_t)LIMIT, sizeof *starts);",
      "    uint64_t *records = malloc((size_t)COUNT * sizeof *records);",
      "    if (!starts || !records) return 3;",
      "",
      "    uint64_t state = 1, state_sum = 0;",
      "    for (uint64_t a = 1; a < LIMIT; ++a) {",
      "        state = advance(state);",
      "        ++starts[state >> LOW_BITS];",
      "        state_sum += state;",
      "    }",
      "    if (state_sum != UINT64_C(15183333062782668587) ||",
      "        state != UINT64_C(2011766183670121759)) return 4;",
      "",
      "    uint64_t total = 0;",
      "    for (uint64_t bucket = 0; bucket < LIMIT; ++bucket) {",
      "        total += starts[bucket];",
      "        starts[bucket] = (uint32_t)total;",
      "    }",
      "    if (total != COUNT) return 5;",
      "",
      "    state = 1;",
      "    for (uint64_t a = 1; a < LIMIT; ++a) {",
      "        state = advance(state);",
      "        uint64_t bucket = state >> LOW_BITS;",
      "        uint64_t position = --starts[bucket];",
      "        records[position] = (a << LOW_BITS) | (state & LOW_MASK);",
      "    }",
      "",
      "    char starts_sha[65], records_sha[65];",
      "    sha256_hex(starts, (size_t)LIMIT * sizeof *starts, starts_sha);",
      "    sha256_hex(records, (size_t)COUNT * sizeof *records, records_sha);",
      "    if (strcmp(starts_sha,",
      "        \"dd87c5d9889c5dac153dded50f97c3902c6800ec902b55cff2ca0888d615b3e4\") ||",
      "        strcmp(records_sha,",
      "        \"46f09e159b66fcf43a035c720fcf15e4861a76f71119ec6033328931b0089fe0\"))",
      "        return 6;",
      "",
      "    uint64_t inspected = 0, found_a = 0, found_b = 0;",
      "    state = 1;",
      "    for (uint64_t b = 1; b <= LIMIT; ++b) {",
      "        state = advance(state);",
      "        uint64_t target = state ^ 1;",
      "        uint64_t bucket = target >> LOW_BITS;",
      "        uint64_t begin = starts[bucket];",
      "        uint64_t end = bucket + 1 < LIMIT ? starts[bucket + 1] : COUNT;",
      "        for (uint64_t position = begin; position < end; ++position) {",
      "            ++inspected;",
      "            uint64_t record = records[position];",
      "            if ((record & LOW_MASK) == (target & LOW_MASK)) {",
      "                uint64_t a = record >> LOW_BITS;",
      "                if (a < b) {",
      "                    found_a = a; found_b = b;",
      "                    goto done;",
      "                }",
      "            }",
      "        }",
      "    }",
      "done:",
      "    if (inspected != UINT64_C(536886339) || found_a || found_b ||",
      "        state != UINT64_C(1717654178049428027)) return 7;",
      "    printf(\"limit=%\" PRIu64 \" states=%\" PRIu64",
      "           \" state_sum_mod_2^64=%\" PRIu64 \" final_a_state=%\" PRIu64 \"\\n\",",
      "           LIMIT, COUNT, state_sum, UINT64_C(2011766183670121759));",
      "    printf(\"starts_sha256_le=%s\\nrecords_sha256_le=%s\\n\",",
      "           starts_sha, records_sha);",
      "    printf(\"inspected=%\" PRIu64 \" found=0 final_b_state=%\" PRIu64 \"\\n\",",
      "           inspected, state);",
      "    free(records);",
      "    free(starts);",
      "    return 0;",
      "}"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/cs/0701069",
    "locator": "Inline C11 and OpenSSL computation executed by TheoremDB entry research on 2026-07-24"
  },
  "models": [],
  "relations": [
    {
      "slug": "R610",
      "title": "No trinomial multiple occurs through degree 2^28",
      "object_type": "claim",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "R609",
      "title": "The interval above 2^28 remains open in this entry",
      "object_type": "attempt",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "primitive-degree61-trinomial-multiple",
      "title": "primitive degree61 trinomial multiple",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}