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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Unconditional fast enumeration of primes by cyclic column shifts

Sean O Brady
Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
preprint

Unconditional fast enumeration of primes by cyclic column shifts

Sean O Brady
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon