HEXAGONbeta

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

Primarily AI-generated textHuman understanding: no partscs.MS — Mathematical Softwaremath.NT — Number Theorycs.DS — Data Structures and Algorithms

Contributed by Brice Pouly ↗

Version 1 / Oct 20, 2026 / CC BY 4.0

Abstract

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 2322^{32} and 2332^{33}. On one RTX 5090, two reserved cohorts give ratios 24.0024.00 and 10.9510.95 of sums of hot per-prime medians against the identified historical dense engine. A separate batch study gives throughput factors 1.231.23-2.582.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(p)O(\sqrt p) running-time bound.

Provenance statement

The following declaration describes the research and the published source edition: Artificial-intelligence tools assisted with implementation, analysis, literature and source checking, and writing and revision. Brice Pouly is the human author and assumes responsibility for the code, data, references and conclusions. Author-controlled CPU and GPU checks do not constitute independently administered external replication or peer review. The source-access limits of the historical comparisons are stated above. For this Hexagon deposit, OpenAI Codex assisted source packaging, compilation checks and the preparation of submission metadata. This preparation does not constitute independent mathematical peer review. The published edition used for this deposit, including its supplementary source material, is available at https://doi.org/10.5281/zenodo.23338707. At the time of preparation for Hexagon, the submitter declares the text primarily AI-generated and declares that no part of the contribution has been checked and understood by a human.

References

  1. J. R. Rabung, Some progression-free partitions constructed using Folkman's method, Canadian Mathematical Bulletin 22(1) (1979), 87--91. doi:10.4153/CMB-1979-012-1 (https://doi.org/10.4153/CMB-1979-012-1).DOI
  2. D. Monroe, New lower bounds for van der Waerden numbers using distributed computing, Journal of Combinatorial Mathematics and Combinatorial Computing 128 (2026), 305--315. doi:10.61091/jcmcc128-19 (https://doi.org/10.61091/jcmcc128-19). Publisher PDF dated 4 December 2025; preprint arXiv:1603.03301 (2016; version 7, 2022). https://arxiv.org/abs/1603.03301.arXivDOI
  3. hmonroe/vdw , software repository, uc2.cpp at commit 267e2b8e09c58af0f7ca9959fedbf9594e87060c (17 February 2019); Git blob ac82f1604958471b7bfab4ff1c8edbdc76ffdc73. File attribution: main program by Daniel Monroe, arithmetic routines based on Mark Lotts; repository/commit identity is distinct from paper authorship. https://github.com/hmonroe/vdw/blob/267e2b8e09c58af0f7ca9959fedbf9594e87060c/uc2.cpp.link
  4. B. Pouly, Succinct Rabung certificates and recurrence-closed lower bounds for van der Waerden numbers , published edition v1.0.0, 2026. doi:10.5281/zenodo.22980965 (https://doi.org/10.5281/zenodo.22980965). Scanner source snapshot 704b4125b274bab3df45454adc9c421f8068b8a1. https://github.com/Vulkin-prog/vdw-rabung-bounds/tree/704b4125b274bab3df45454adc9c421f8068b8a1.DOI
  5. B. Pouly, Succinct Rabung certificates and recurrence-closed lower bounds for van der Waerden numbers , published edition v2.0, 2026. doi:10.5281/zenodo.23337824 (https://doi.org/10.5281/zenodo.23337824).DOI
  6. D. Micciancio, Minkowski's theorem , CSE206A: Lattice Algorithms and Applications, UC San Diego, Fall 2025, Corollary 8. https://cseweb.ucsd.edu/classes/fa25/cse206A-a/Lec2-Minkowski.pdf.link
  7. P. L. Montgomery, Modular multiplication without trial division, Mathematics of Computation 44(170) (1985), 519--521. doi:10.1090/S0025-5718-1985-0777282-X (https://doi.org/10.1090/S0025-5718-1985-0777282-X).DOI
  8. J. P. Sorenson and J. Webster, Strong pseudoprimes to twelve prime bases, Mathematics of Computation 86(304) (2017), 985--1003. doi:10.1090/mcom/3134 (https://doi.org/10.1090/mcom/3134); preprint https://arxiv.org/abs/1509.00864.DOI
  9. NVIDIA, Blackwell Tuning Guide , sections on compute capability 12.0, consulted 3 October 2026. https://docs.nvidia.com/cuda/blackwell-tuning-guide/.link
  10. W. Beullens, T. Beyne, A. Udovenko and G. Vitto, Cryptanalysis of the Legendre PRF and generalizations, IACR Transactions on Symmetric Cryptology 2020(1), 313--330. doi:10.13154/tosc.v2020.i1.313-330 (https://doi.org/10.13154/tosc.v2020.i1.313-330). ePrint 2019/1357, revised 30 October 2020. https://eprint.iacr.org/2019/1357.DOI
Show all 17 referencesShow fewer references
  1. N. Kalu erović, T. Kleinjung and D. Kostić, Improved key recovery on the Legendre PRF , ePrint 2020/098, version 23 June 2021, Sections 3--5 and Appendix A. https://eprint.iacr.org/2020/098.link
  2. N. Kalu erović, T. Kleinjung and D. Kostić, Cryptanalysis of the generalised Legendre pseudorandom function, The Open Book Series 4(1) (2020), 267--282, ANTS XIV. doi:10.2140/obs.2020.4.267 (https://doi.org/10.2140/obs.2020.4.267). This separate bibliographic entry is not substituted for the revised ePrint.DOI
  3. D. A. Buell and R. H. Hudson, On runs of consecutive quadratic residues and quadratic nonresidues, BIT 24 (1984), 243--247. doi:10.1007/BF01937490 (https://doi.org/10.1007/BF01937490). Publisher abstract and bibliography consulted; full text and cited LSU Computer Science Technical Report 83-017 not obtained.DOI
  4. D. H. Lehmer and E. Lehmer, On runs of residues, Proceedings of the American Mathematical Society 13 (1962), 102--106. doi:10.1090/S0002-9939-1962-0138582-6 (https://doi.org/10.1090/S0002-9939-1962-0138582-6).DOI
  5. J. R. Rabung and J. H. Jordan, Consecutive power residues or nonresidues, Mathematics of Computation 24 (1970), 737--740. https://www.cs.umd.edu/~gasarch/TOPICS/res/resRabungJordan.pdf.link
  6. V. Shoup, A Computational Introduction to Number Theory and Algebra , 2nd edition, Cambridge University Press (2008), Sections 4.5--4.6. https://shoup.net/ntb/ntb-v2.pdf.link
  7. P. S. Wang, M. J. T. Guy and J. H. Davenport, P-adic reconstruction of rational numbers, ACM SIGSAM Bulletin 16(2) (1982), 2--3. doi:10.1145/1089292.1089293 (https://doi.org/10.1145/1089292.1089293). https://www.cecm.sfu.ca/~mmonagan/teaching/TopicsinCA15/GuyDavenWang.pdf.DOI

Version history

  1. v1Submitted by Brice PoulyInitial depositCurrentOct 18, 2026