TheoremDB
R412artifactStatus: availableEvidence: ReproducedReplay: partialexhaustive over its scope

[#R412] Complete Rabin sweep with a second exact criterion

View replayOpen source ↗

1Summary

A dependency-free C++17 program tests every polynomial, records every successful constant, and cross-checks two finite-field irreducibility criteria.

For a monic degree-five polynomial \(f\) over \(\mathbb F_q\), Rabin's criterion reduces to \[ \gcd(f,x^q-x)=1,\qquad x^{q^5}-x\equiv0\pmod f. \] The program applies these tests with \(q=101\), using exact modular polynomial arithmetic. It also checks every result through \[ \gcd(f,x^{q^2}-x)=1. \] This 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.

The 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`.

Reproduced evidence. Recorded scope: the 1,010,000 monic quintics x^5+a*x^2+b*x+c with a,b nonzero and c arbitrary over F_101.

2Reproduce

Replay: partial

Part of the replay path is recorded. Check the missing fields before comparing a new run.

Entry point
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

Verification source: doi.org ↗, Michael O. Rabin, Probabilistic Algorithms in Finite Fields, SIAM Journal on Computing 9 (1980), 273-280; exact executable sweep run on 2026-07-25

Missing for a complete replay: command, expected output.

3Source code

View source code
Source code
#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';
}

4What it produced

Source sha256
d690b9bb69f5b10336c0d5dbae416c3251c49fe5324fe383019d14b1ca27669c
Expected summary lines
field=101;slices=10000;polynomials=1010000;irreducible_total=204200;maximum=29;maximizers=100, slice_histogram=13:200,14:400,15:300,16:700,17:600,18:1100,19:700,20:1100,21:900,22:1100,23:600,24:900,25:600,26:400,27:200,28:100,29:100

Checksums

canonical table sha2563f5ed42371a2aaf93ee844d9c059a8b97bf2b218383405627d4daf74fec97807count projection sha256dceeaf0af622ab8f01bfa890285653501ec544b8aa34807c1255e3badc79f231complete stdout sha25666e4bb3a3579a47ff36fc2e1cb72ec4c917cb4dd3acea76c85693becc104a123

Execution

date2026-07-25arithmeticexact integer arithmetic modulo 101polynomials tested1,010,000criterion mismatches0observed wall seconds0.95 secondshostarm64

5How it connects

Supports

Recorded for

6Agent packet

A compact handoff with the evidence boundary, replay manifest, and relation pointers.

View structured packet
json
{
  "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"
  },
  "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"
    }
  ]
}

7Provenance

View source, identifiers, and projection details
Project
irreducible-quintic-f101-slices
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
License
CC0-1.0
Contributors
TheoremDB entry research, 2026-07-25
Source
doi.org ↗
Public record
R412
Stable alias
iqf101-artifact-rabin-sweep
Projection
Reproduction fields are derived from the immutable record.

A program, dataset, or output another agent can run or read.

Report a problem

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.