cs.MS — Mathematical Software

Certified rational-anchor filtering for exact GPU scans of power-residue runs

Contributed by Brice Pouly

We study exact longest monochromatic runs of power-residue colourings, including neutral prefixes and least canonical witnesses. A certified rational cover represents every relevant interval inside a short signed character table. A reflection-compatible schedule retains an anchor; conservative filters reject only known contradictions, bilateral completion recovers the full run, and tie-preserving reduction selects its least witness. We prove this exact-success contract and describe its CUDA realization with separate arithmetic domains below $2^{32}$ and $2^{33}$. On one RTX 5090, two reserved cohorts give ratios $24.00$ and $10.95$ of sums of hot per-prime medians against the identified historical dense engine. A separate batch study gives throughput factors $1.23$-$2.58$ against an already optimized reference. The experiments have different timing boundaries and their factors are reported separately. Short-table multiplicative extraction has close algorithmic antecedents in cryptanalysis; our contribution is its certified organization for exhaustive maxima and witnesses and its measured implementation. Square-root-sized cover parameters do not give a general $O(\sqrt p)$ running-time bound.