Unconditional fast enumeration of primes by cyclic column shifts
We give a Las Vegas algorithm that enumerates all primes less than n in expectedn(log log n)1+o(1) bit operations on a multitape Turing machine. In Harvey’s algorithm thesize of a compression row is limited by the possibility of unusually many odd square-primes in ashort interval. We randomly shift columns on a product of two cyclic index sets before compression,with limited independence. The global square-prime count then bounds the mean weight of everyshifted row. The shifts are realized at the field-evaluation layer of Harvey’s binary polynomialtransform. A separate truncated last product block makes this realization exact on the paddedinput domain, and an exact square-prime tally certifies successful decoding. The resulting boundmatches the exponent in Harvey’s conjecture-dependent algorithm.
Authors
- Sean O Brady
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-20
- DOI
- https://doi.org/10.5281/zenodo.24383310
- Primary Topic
- Analytic Number Theory Research
- Type
- preprint