{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R412",
  "content_hash": null,
  "slug": "iqf101-artifact-rabin-sweep",
  "type": "artifact",
  "title": "Complete Rabin sweep with a second exact criterion",
  "summary": "A dependency-free C++17 program tests every polynomial, records every successful constant, and cross-checks two finite-field irreducibility criteria.",
  "relevance": "For Most irreducible constant slices of a sparse quintic over F_101, record iqf101-artifact-rabin-sweep (“Complete Rabin sweep with a second exact criterion”) supplies evidence or a replay used to check the packet. The record states: A dependency-free C++17 program tests every polynomial, records every successful constant, and cross-checks two finite-field irreducibility criteria.",
  "relevance_source": "recorded",
  "body": "For a monic degree-five polynomial \\(f\\) over \\(\\mathbb F_q\\), Rabin's criterion reduces to\n\\[\n\\gcd(f,x^q-x)=1,\\qquad x^{q^5}-x\\equiv0\\pmod f.\n\\]\nThe program applies these tests with \\(q=101\\), using exact modular polynomial arithmetic. It also checks every result through\n\\[\n\\gcd(f,x^{q^2}-x)=1.\n\\]\nThis second condition is equivalent here because every reducible quintic has an irreducible factor of degree one or two, and \\(x^{q^2}-x\\) contains every monic irreducible whose degree divides two. The program exits if the two decisions differ. They agree on all 1,010,000 inputs.\n\nThe output begins with three summary lines. It then writes one canonical row for every pair in lexicographic order, formatted as `a<TAB>b<TAB>N<TAB>c_1,c_2,...<LF>`. The 10,000-row table has SHA-256 digest `3f5ed42371a2aaf93ee844d9c059a8b97bf2b218383405627d4daf74fec97807`. Its three-column count projection has digest `dceeaf0af622ab8f01bfa890285653501ec544b8aa34807c1255e3badc79f231`. The complete output, including summary lines, has digest `66e4bb3a3579a47ff36fc2e1cb72ec4c917cb4dd3acea76c85693becc104a123`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "the 1,010,000 monic quintics x^5+a*x^2+b*x+c with a,b nonzero and c arbitrary over F_101",
    "bounds": {
      "field_order": {
        "min": 101,
        "max": 101
      },
      "a_values": {
        "min": 100,
        "max": 100
      },
      "b_values": {
        "min": 100,
        "max": 100
      },
      "c_values": {
        "min": 101,
        "max": 101
      },
      "tests": {
        "min": 1010000,
        "max": 1010000
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_cpp_computation",
    "entrypoint": "Join source_lines with newline and append a final newline. Compile with c++ -O3 -std=c++17, run into sweep.tsv, inspect the first three lines, and hash the whole output. Hash tail -n +4 for the canonical table. Hash tail -n +4 piped through cut -f1-3 for the count projection.",
    "runtime": "C++17 compiler and standard POSIX text tools",
    "citation": {
      "url": "https://doi.org/10.1137/0209024",
      "locator": "Michael O. Rabin, Probabilistic Algorithms in Finite Fields, SIAM Journal on Computing 9 (1980), 273-280; exact executable sweep run on 2026-07-25"
    },
    "inline_source": [
      "#include <algorithm>",
      "#include <array>",
      "#include <cstdint>",
      "#include <cstdlib>",
      "#include <iostream>",
      "#include <map>",
      "#include <sstream>",
      "#include <string>",
      "#include <vector>",
      "using namespace std;",
      "",
      "constexpr int P = 101;",
      "using R = array<int, 5>;",
      "",
      "static R mul_mod(const R& u, const R& v, int a, int b, int c) {",
      "  int64_t t[9] = {};",
      "  for (int i = 0; i < 5; ++i)",
      "    for (int j = 0; j < 5; ++j)",
      "      t[i+j] += int64_t(u[i]) * v[j];",
      "  for (int d = 8; d >= 5; --d) {",
      "    int z = int(t[d] % P);",
      "    t[d-3] -= int64_t(a) * z;",
      "    t[d-4] -= int64_t(b) * z;",
      "    t[d-5] -= int64_t(c) * z;",
      "  }",
      "  R out{};",
      "  for (int i = 0; i < 5; ++i) {",
      "    out[i] = int(t[i] % P);",
      "    if (out[i] < 0) out[i] += P;",
      "  }",
      "  return out;",
      "}",
      "",
      "static R power_mod(R base, uint64_t exponent, int a, int b, int c) {",
      "  R out{1, 0, 0, 0, 0};",
      "  while (exponent) {",
      "    if (exponent & 1) out = mul_mod(out, base, a, b, c);",
      "    exponent >>= 1;",
      "    if (exponent) base = mul_mod(base, base, a, b, c);",
      "  }",
      "  return out;",
      "}",
      "",
      "static int inv_mod(int x) {",
      "  int a = x, b = P, u = 1, v = 0;",
      "  while (b) {",
      "    int q = a / b;",
      "    int tmp = a - q*b; a = b; b = tmp;",
      "    tmp = u - q*v; u = v; v = tmp;",
      "  }",
      "  u %= P;",
      "  return u < 0 ? u + P : u;",
      "}",
      "",
      "using Poly = array<int, 6>;",
      "static int degree(const Poly& f) {",
      "  for (int i = 5; i >= 0; --i) if (f[i]) return i;",
      "  return -1;",
      "}",
      "static Poly remainder(Poly u, const Poly& v) {",
      "  int dv = degree(v);",
      "  int inv = inv_mod(v[dv]);",
      "  while (degree(u) >= dv) {",
      "    int du = degree(u), shift = du-dv;",
      "    int factor = u[du] * inv % P;",
      "    for (int i = 0; i <= dv; ++i) {",
      "      u[i+shift] = (u[i+shift] - factor*v[i]) % P;",
      "      if (u[i+shift] < 0) u[i+shift] += P;",
      "    }",
      "  }",
      "  return u;",
      "}",
      "static int gcd_degree(Poly u, Poly v) {",
      "  while (degree(v) >= 0) {",
      "    Poly r = remainder(u, v);",
      "    u = v;",
      "    v = r;",
      "  }",
      "  return degree(u);",
      "}",
      "",
      "static bool irreducible(int a, int b, int c) {",
      "  const R x{0, 1, 0, 0, 0};",
      "  R xq = power_mod(x, P, a, b, c);",
      "  Poly f{c, b, a, 0, 0, 1};",
      "  Poly h1{};",
      "  for (int i = 0; i < 5; ++i) h1[i] = xq[i];",
      "  h1[1] = (h1[1] + P - 1) % P;",
      "  bool no_linear_factor = gcd_degree(f, h1) == 0;",
      "  R r = xq;",
      "  for (int i = 1; i < 5; ++i) r = power_mod(r, P, a, b, c);",
      "  bool rabin = no_linear_factor && r == x;",
      "",
      "  R xq2 = power_mod(xq, P, a, b, c);",
      "  Poly h2{};",
      "  for (int i = 0; i < 5; ++i) h2[i] = xq2[i];",
      "  h2[1] = (h2[1] + P - 1) % P;",
      "  bool no_degree_one_or_two_factor = gcd_degree(f, h2) == 0;",
      "  if (rabin != no_degree_one_or_two_factor) {",
      "    cerr << \"criterion mismatch at \" << a << ',' << b << ',' << c << '\\n';",
      "    exit(2);",
      "  }",
      "  return rabin;",
      "}",
      "",
      "int main() {",
      "  map<int,int> slice_hist;",
      "  int best = -1;",
      "  vector<pair<int,int>> maximizers;",
      "  vector<string> lines;",
      "  uint64_t irreducible_total = 0;",
      "  for (int a = 1; a < P; ++a) {",
      "    for (int b = 1; b < P; ++b) {",
      "      vector<int> constants;",
      "      for (int c = 0; c < P; ++c) {",
      "        if (irreducible(a,b,c)) constants.push_back(c);",
      "      }",
      "      int n = int(constants.size());",
      "      irreducible_total += n;",
      "      slice_hist[n]++;",
      "      if (n > best) {",
      "        best = n;",
      "        maximizers.clear();",
      "      }",
      "      if (n == best) maximizers.emplace_back(a,b);",
      "      ostringstream s;",
      "      s << a << '\\t' << b << '\\t' << n << '\\t';",
      "      for (size_t i = 0; i < constants.size(); ++i) {",
      "        if (i) s << ',';",
      "        s << constants[i];",
      "      }",
      "      lines.push_back(s.str());",
      "    }",
      "  }",
      "  cout << \"field=101;slices=10000;polynomials=1010000;irreducible_total=\"",
      "       << irreducible_total << \";maximum=\" << best",
      "       << \";maximizers=\" << maximizers.size() << '\\n';",
      "  cout << \"slice_histogram=\";",
      "  bool first = true;",
      "  for (auto [n,count] : slice_hist) {",
      "    if (!first) cout << ',';",
      "    first = false;",
      "    cout << n << ':' << count;",
      "  }",
      "  cout << '\\n';",
      "  cout << \"maximizer_pairs=\";",
      "  for (size_t i = 0; i < maximizers.size(); ++i) {",
      "    if (i) cout << ',';",
      "    cout << maximizers[i].first << ':' << maximizers[i].second;",
      "  }",
      "  cout << '\\n';",
      "  for (const auto& line : lines) cout << line << '\\n';",
      "}"
    ],
    "missing": [
      "command",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1137/0209024",
    "locator": "Michael O. Rabin, Probabilistic Algorithms in Finite Fields, SIAM Journal on Computing 9 (1980), 273-280; exact executable sweep run on 2026-07-25"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R414",
      "title": "The exact maximum slice count is 29",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "irreducible-quintic-f101-slices",
      "title": "irreducible quintic f101 slices",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}