Pith. sign in

REVIEW 2 major objections 1 minor 29 references

Faster enumeration of primes

T0 review · 2 major / 1 minor · reviewed 2026-06-26 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read New algorithms enumerate all primes up to N in N (log log N)^{1+o(1)} bit operations.

desk verdict Harvey claims the first log-power speedup for prime enumeration using polynomial arithmetic over finite fields, but the strongest bound is non-rigorous and the reduction may hide extra factors. read the letter →

arxiv 2606.22851 v1 pith:G3QBDEDJ submitted 2026-06-22 math.NT cs.DScs.SC

David Harvey This is my paper · ORCID
classification math.NTcs.DScs.SC
keywords primeenumerationsieveofEratosthenesfastpolynomialarithmeticfinitefieldserror-correctingcodesbitcomplexitymultitapeTuringmachine
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper presents new algorithms for finding every prime up to a bound N. These achieve the first improvement by a positive power of log N over the classic sieve of Eratosthenes. The fastest version runs in N (log log N)^{1+o(1)} bit operations under the multitape Turing model. The method reduces the sieving task to fast polynomial arithmetic over finite fields and incorporates ideas from error-correcting codes. Rigorous randomized and deterministic variants are given at the cost of additional logarithmic factors.

What carries the argument

Fast polynomial arithmetic over finite fields, used to compute convolutions or products that mark composite numbers during sieving.

What would settle it

A concrete multitape Turing machine analysis or implementation for N around 10^12 that shows the observed bit operations exceed N (log log N)^{1.5} or fail to beat prior sieves by a factor approaching log N.

Watch

Extended reading notes

Core claim

By reducing the problem of sieving for primes up to N to fast polynomial arithmetic over finite fields, the bit complexity of prime enumeration drops to N (log log N)^{1+o(1)}, which improves on the N log log N time of the sieve of Eratosthenes by a positive power of log N.

Load-bearing premise

The reduction of sieving to polynomial arithmetic over finite fields introduces no hidden logarithmic factors that cancel the claimed improvement.

Editorial extensions

If this is right

  • The fastest algorithm improves on Pritchard (1981), Atkin-Bernstein (2004) and Sergeev (2016) by almost a factor of log N.
  • A rigorous randomized Las Vegas variant runs slower by an extra (log log N)^{1+o(1)} factor.
  • A rigorous deterministic variant runs slower by an extra (log N)^{1/2+o(1)} factor.
  • The approach draws on error-correcting codes to support the polynomial arithmetic reductions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same polynomial reduction technique might apply to other sieving tasks such as finding smooth numbers or twin primes.
  • Practical code could test whether the asymptotic gains appear in real-world runtimes for N near 10^15.
  • Connections between finite-field polynomials and combinatorial sieves may extend to related problems in analytic number theory.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 1 minor

Summary. The manuscript presents new algorithms for enumerating primes up to N that rely on fast polynomial arithmetic over finite fields together with techniques from error-correcting codes. The fastest variant is stated to run in N (log log N)^{1+o(1)} bit operations in the multitape Turing model and to improve on Pritchard (1981), Atkin–Bernstein (2004) and Sergeev (2016) by a factor of almost log N; this variant is explicitly described as not fully rigorous. Rigorous Las Vegas and deterministic versions incur extra factors of (log log N)^{1+o(1)} and (log N)^{1/2+o(1)} respectively.

Significance. A fully rigorous proof of the stated complexity would constitute a notable advance, being the first improvement by a positive power of log N over the classical sieve of Eratosthenes and its subsequent refinements. The algebraic approach via polynomial arithmetic is a clear methodological strength.

major comments (2)
  1. [Abstract] Abstract: the primary claim of a positive-power log N speedup is carried exclusively by the non-rigorous variant whose complexity is N (log log N)^{1+o(1)}. The abstract itself states that this version 'is not fully rigorous', while the rigorous variants are slower by additional (log log N)^{1+o(1)} or (log N)^{1/2+o(1)} factors; therefore the claimed improvement over prior work is not yet supported by a complete analysis.
  2. [Abstract] Abstract (paragraph on polynomial arithmetic): the reduction of the sieving problem to fast polynomial arithmetic over finite fields is asserted to incur no hidden logarithmic factors that would cancel the (log log N)^{1+o(1)} gain. No explicit accounting of all multitape Turing-machine operations (field arithmetic overhead, tape management, or error-correcting-code constructions) is supplied, leaving open the possibility that a single extra log log N factor appears and eliminates the asymptotic improvement.
minor comments (1)
  1. [Abstract] The abstract would be clearer if it briefly indicated which specific ideas from error-correcting codes are invoked and in which algorithmic step.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the primary claim of a positive-power log N speedup is carried exclusively by the non-rigorous variant whose complexity is N (log log N)^{1+o(1)}. The abstract itself states that this version 'is not fully rigorous', while the rigorous variants are slower by additional (log log N)^{1+o(1)} or (log N)^{1/2+o(1)} factors; therefore the claimed improvement over prior work is not yet supported by a complete analysis.

    Authors: We agree that the strongest claimed improvement appears in the non-rigorous variant. The abstract already qualifies the status of this variant. To address the concern about clarity, we will revise the abstract to state the complexities of the rigorous variants more explicitly and to note that the full improvement over prior work is shown only for the non-rigorous case pending further analysis. revision: yes

  2. Referee: [Abstract] Abstract (paragraph on polynomial arithmetic): the reduction of the sieving problem to fast polynomial arithmetic over finite fields is asserted to incur no hidden logarithmic factors that would cancel the (log log N)^{1+o(1)} gain. No explicit accounting of all multitape Turing-machine operations (field arithmetic overhead, tape management, or error-correcting-code constructions) is supplied, leaving open the possibility that a single extra log log N factor appears and eliminates the asymptotic improvement.

    Authors: We acknowledge that the current manuscript does not provide an exhaustive enumeration of every multitape Turing-machine operation in the reduction. The analysis relies on standard complexity bounds for the underlying primitives. We will add an expanded discussion or appendix that explicitly bounds the overheads from field arithmetic, tape management, and code constructions to confirm that no additional (log log N) factor arises. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: derivation relies on external polynomial arithmetic techniques

full rationale

The paper introduces new prime-sieving algorithms that reduce the problem to fast polynomial multiplication over finite fields and error-correcting code constructions. These reductions are presented as independent algorithmic steps whose complexity is analyzed in the multitape Turing model; no equation or claim is shown to be definitionally equivalent to its own inputs, no fitted parameters are relabeled as predictions, and no load-bearing premise rests on a self-citation chain. The explicit caveats about rigor levels further separate the claimed bounds from any self-referential construction.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

With only the abstract available, the ledger is necessarily incomplete. The work appears to rest on standard results in fast polynomial multiplication over finite fields and basic properties of error-correcting codes; no free parameters or invented entities are mentioned.

assumptions (2)
  • standard math Fast polynomial arithmetic over finite fields can be performed in the stated time bounds using existing algorithms.
    Invoked implicitly when the abstract credits the speedup to fast polynomial arithmetic.
  • domain assumption The multitape Turing machine model accurately captures the bit complexity of the described operations.
    The complexity statements are given explicitly in this model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster enumeration of primes." pith.science (2026). https://pith.science/paper/G3QBDEDJ

@misc{pith2026260622851,
  author       = {Pith},
  title        = {Pith review of: Faster enumeration of primes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G3QBDEDJ}},
  note         = {Machine review of arXiv:2606.22851}
}
abstract

We describe several new algorithms for finding all prime numbers up to a given bound $N$, achieving the first ever speedup by a positive power of $\log N$ over the ancient sieve of Eratosthenes. The fastest version, which is not fully rigorous, runs in \[ N (\log \log N)^{1+o(1)} \] bit operations when analysed in the multitape Turing model. This improves on the best existing algorithms due to Pritchard (1981), Atkin--Bernstein (2004) and Sergeev (2016) by a factor of almost $\log N$. We also present a rigorous randomised (Las Vegas) variant that is slower by a factor of $(\log \log N)^{1+o(1)}$, and a rigorous deterministic variant that is slower by a factor of $(\log N)^{1/2+o(1)}$. The new algorithms make heavy use of fast polynomial arithmetic over finite fields, and also involve ideas from the theory of error-correcting codes.

Figures

Figures reproduced from arXiv: 2606.22851 by the authors.

Figure 1.1
Figure 1.1. Main dependencies between sections. Dashed arrows indicate dependence on minor auxiliary results. means that f(x)/g(x) → 0 as x → ∞. In particular, o(1) stands for a function that approaches zero as x → ∞. We write log x for the natural logarithm and log2 x for the base two logarithm. We define lg x := max(1, ⌈log2 x⌉), so that lg x takes positive integer values for all x > 0. We write log∗ x for the iterated logari… view at source ↗
Figure 2.1
Figure 2.1. The restricted product f g. The shaded region shows pairs (i, j) such that i ⩾ 2j ⩾ 0. The stars indicate products figj contributing to the coefficient of x 3 in f g, i.e., pairs for which i − j = 3 [PITH_FULL_IMAGE:figures/full_fig_p016_2_1.png] view at source ↗
Figure 4.1
Figure 4.1. Decomposition of Lemma 4.25 for m = 4. Proof of Lemma 4.25. The result follows more or less directly from [PITH_FULL_IMAGE:figures/full_fig_p032_4_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 24 canonical work pages

  1. [1]

    Prime sieves using binary qua- dratic forms

    [AB04] A. O. L. Atkin and D. J. Bernstein. “Prime sieves using binary qua- dratic forms”. In:Math. Comp.73.246 (2004), pp. 1023–1030.issn: 0025-5718,1088-6842.doi:10.1090/S0025-5718-03-01501-1. [AHU75] A. V. Aho, J. E. Hopcroft, and J. D. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley Series in Computer Science and Information Proce...

    work page doi:10.1090/s0025-5718-03-01501-1 2004

  2. [2]

    Amin Shokrollahi.Algebraic Complexity Theory, volume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]

    Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. With the collabo- ration of Thomas Lickteig. Springer-Verlag, Berlin, 1997, pp. xxiv+618. isbn: 3-540-60582-7.doi:10.1007/978-3-662-03338-8. [Ben+16] M. A. Bender et al. “The I/O complexity of computing prime tables”. In:LATIN 2016: Theoretical Informatics. Vol

    work page doi:10.1007/978-3-662-03338-8 1997

  3. [3]

    An incremental primal sieve

    Lecture Notes in Comput. Sci. Springer, Berlin, 2016, pp. 192–206.isbn: 978-3-662- 49529-2; 978-3-662-49528-5.doi:10.1007/978-3-662-49529-2_15. [Ben86] S. A. Bengelloun. “An incremental primal sieve”. In:Acta Inform. 23.2 (1986), pp. 119–125.issn: 0001-5903,1432-0525.doi:10.1007/ BF00289493. 116 REFERENCES [Ber08] D. J. Bernstein. “Fast multiplication and...

    work page doi:10.1007/978-3-662-49529-2_15 2016

  4. [4]

    Factoring polynomials over large finite fields

    Math. Sci. Res. Inst. Publ. Cambridge: Cambridge Univ. Press, 2008, pp. 325–384.doi:10.1017/9781139049801.011. [Ber70] E. R. Berlekamp. “Factoring polynomials over large finite fields”. In: Math. Comp.24 (1970), pp. 713–735.issn: 0025-5718,1088-6842.doi: 10.2307/2004849. [BGS07] A. Bostan, P. Gaudry, and ´E. Schost. “Linear recurrences with polyno- mial c...

    work page doi:10.1017/9781139049801.011 2008

  5. [5]

    Cambridge University Press, Cambridge, 2011, pp

    Cambridge Monographs on Applied and Computational Mathemat- ics. Cambridge University Press, Cambridge, 2011, pp. xvi+221.isbn: 978-0-521-19469-3.doi:10.1017/CBO9780511921698. [CM06] A. C. Cojocaru and M. R. Murty.An Introduction to Sieve Methods and Their Applications. Vol

    work page doi:10.1017/cbo9780511921698 2011

  6. [6]

    On the order of magnitude of the difference between consecutive prime numbers

    London Mathematical Society Stu- dent Texts. Cambridge University Press, Cambridge, 2006, pp. xii+224. isbn: 978-0-521-64275-3; 0-521-61275-6.doi:10.1017/CBO9780511615993. [Coh+06] H. Cohen et al., eds.Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete Mathematics and its Applications (Boca Ra- ton). Chapman & Hall/CRC, Boca Raton, FL, 20...

    work page doi:10.1017/cbo9780511615993 2006

  7. [7]

    A space-efficient fast prime number sieve

    [DJS96] B. Dunten, J. Jones, and J. Sorenson. “A space-efficient fast prime number sieve”. In:Inform. Process. Lett.59.2 (1996), pp. 79–84.issn: 0020-0190,1872-6119.doi:10.1016/0020-0190(96)00099-3. [DLMF]NIST Digital Library of Mathematical Functions.https : / / dlmf . nist.gov/, Release 1.2.6 of 2026-03-15. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Loz...

    work page doi:10.1016/0020-0190(96)00099-3 1996

  8. [8]

    Prime chains and Pratt trees

    American Mathematical Society Colloquium Publications. American Mathemat- ical Society, Providence, RI, 2010, pp. xx+527.isbn: 978-0-8218-4970- 5.doi:10.1090/coll/057. [FKL10] K. Ford, S. V. Konyagin, and F. Luca. “Prime chains and Pratt trees”. In:Geom. Funct. Anal.20.5 (2010), pp. 1231–1258.issn: 1016- 443X,1420-8970.doi:10.1007/s00039-010-0089-0. [FR13...

    work page doi:10.1090/coll/057 2010

Show all 29 references
  1. [9]

    Lecture Notes in Comput. Sci. Springer, Heidelberg, 2015, pp. 677–688.isbn: 978-3-662-48971-0; 978-3-662-48970-3.doi:10 . 1007 / 978 - 3 - 662 - 48971-0_57. [FT93] A. Fr¨ ohlich and M. J. Taylor.Algebraic Number Theory. Vol

    2015

  2. [10]

    Dissecting a sieve to cut its need for space

    Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1993, pp. xiv+355.isbn: 0-521-43834-9. [Gal00] W. F. Galway. “Dissecting a sieve to cut its need for space”. In:Al- gorithmic Number Theory (Leiden, 2000). Vol

    1993

  3. [11]

    Primes in short intervals: heuristics and calculations

    Lecture Notes in Comput. Sci. Springer, Berlin, 2000, pp. 297–312.isbn: 3-540-67695-3. doi:10.1007/10722028_17. [Gal04] W. F. Galway.Analytic computation of the prime-counting function. Thesis (Ph.D.)–University of Illinois at Urbana-Champaign. ProQuest LLC, Ann Arbor, MI, 200...

    2023 doi

  4. [12]

    An improved sieve of Eratosthenes

    Ergebnisse der Mathe- matik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 2001, pp. xii+304.isbn: 3-540- 41647-1.doi:10.1007/978-3-662-04658-6. [Hel20] H. A. Helfgott. “An improved sieve of Eratosthenes”. In:Math. Comp. 89....

    2001 doi

  5. [13]

    Reducing the space used by the sieve of Eratosthenes when factoring

    London Mathematical Society Monographs. Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1974, xiv+364 pp. (loose errata). [HS25] S. Hartman and J. P. Sorenson. “Reducing the space used by the sieve of Eratosthenes when factoring”. In:Inform. Process. L...

    1974 doi

  6. [14]

    Even faster integer multiplication

    issn: 0004-5411,1557-735X.doi:10.1145/3505584. [HvdHL16] D. Harvey, J. van der Hoeven, and G. Lecerf. “Even faster integer multiplication”. In:J. Complexity36 (2016), pp. 1–30.issn: 0885- 064X.doi:10.1016/j.jco.2016.03.001. [HvdHL17] D. Harvey, J. van der Hoeven, and G. Lecerf...

    2016 doi

  7. [15]

    [IK04] H

    issn: 0004-5411,1557-735X.doi:10.1145/3005344. [IK04] H. Iwaniec and E. Kowalski.Analytic Number Theory. Vol

    doi

  8. [16]

    Providence, RI: American Mathematical Society, 2004, pp

    Amer- ican Mathematical Society Colloquium Publications. Providence, RI: American Mathematical Society, 2004, pp. xii+615.isbn: 0-8218-3633- 1.doi:10.1090/coll/053. [Kat10] UNSW Sydney PVC (Research Infrastructure). “Katana”. In: (2010). doi:10.26190/669X- A286.url:https://res...

    2004 doi

  9. [17]

    Addison-Wesley, Reading, MA, 1998, pp

    Seminu- merical algorithms, Third edition [of MR0286318]. Addison-Wesley, Reading, MA, 1998, pp. xiv+762.isbn: 0-201-89684-2. [Knu98b] D. E. Knuth.The Art of Computer Programming. Vol

    1998

  10. [18]

    Addison-Wesley, Reading, MA, 1998, pp

    Sorting and searching, Second edition [of MR0445948]. Addison-Wesley, Reading, MA, 1998, pp. xiv+780.isbn: 0-201-89685-0. [Kou19] D. Koukoulopoulos.The Distribution of Prime Numbers. Vol

    1998

  11. [19]

    Algorithms in algebraic number theory

    Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2019, pp. xii + 356.isbn: 978-1-4704-4754-0; 978-1- 4704-6285-7.doi:10.1090/gsm/203. [Len92] H. W. Lenstra Jr. “Algorithms in algebraic number theory”. In:Bull. Amer. Math. Soc. (N.S.)26.2 (1992), ...

    2019 doi

  12. [20]

    Cambridge University Press, Cambridge, 2007, pp

    Cambridge Studies in Advanced Math- ematics. Cambridge University Press, Cambridge, 2007, pp. xviii+552. isbn: 978-0-521-84903-6; 0-521-84903-9.doi:10.1017/CBO9780511618314. [OEIS] OEIS Foundation Inc.Online Encyclopedia of Integer Sequences.https: //oeis.org/, accessed 9th June

    2007 doi

  13. [21]

    Sorting and element distinctness on one-way Turing ma- chines

    [Pap94] C. H. Papadimitriou.Computational Complexity. Reading, MA: Addison- Wesley Publishing Company, 1994, pp. xvi+523.isbn: 0-201-53082-1. [Pet08] H. Petersen. “Sorting and element distinctness on one-way Turing ma- chines”. In:Language and Automata Theory and Applications. Vol

    1994

  14. [22]

    Lecture Notes in Comput. Sci. Springer, Berlin, 2008, pp. 433–439. isbn: 978-3-540-88281-7; 3-540-88281-2.doi:10.1007/978- 3- 540- 88282-4_39. [Pra77] V. Pratt.CGOL - an Algebraic Notation For MACLISP users. Tech. rep.https://people.eecs.berkeley.edu/ ~fateman/cgol/cgol. 1/pra...

    2008 doi

  15. [23]

    A sublinear additive sieve for finding prime numbers

    120 REFERENCES [Pri81] P. Pritchard. “A sublinear additive sieve for finding prime numbers”. In:Comm. ACM24.1 (1981), pp. 18–23.issn: 0001-0782.doi:10. 1145/358527.358540. [Pri82] P. Pritchard. “Explaining the wheel sieve”. In:Acta Inform.17.4 (1982), pp. 477–485.issn: 0001-59...

    1981 doi

  16. [24]

    Polynomial codes over certain finite fields

    Lecture Notes in Comput. Sci. Springer, Berlin, 1994, pp. 280–288.isbn: 3-540-58691-1. doi:10.1007/3-540-58691-1_67. [Rei90] K. R. Reischuk.Einf¨ uhrung in die Komplexit¨ atstheorie. Leitf¨ aden und Monographien der Informatik. [Guides and Monographs in Informa- tion Science]....

    1994 doi

  17. [25]

    Schnelle Multiplikation von Polynomen ¨ uber K¨ orpern der Charakteristik 2

    [Sch77] A. Sch¨ onhage. “Schnelle Multiplikation von Polynomen ¨ uber K¨ orpern der Charakteristik 2”. In:Acta Informat.7.4 (1977), pp. 395–398.doi: 10.1007/BF00289470. [Sel43] A. Selberg. “On the normal density of primes in small intervals, and the difference between consecut...

    1977 doi arXiv

  18. [26]

    On the complexity of computing prime tables on the Turing machine

    [Ser16b] I. S. Sergeev. “On the complexity of computing prime tables on the Turing machine”. Russian. In:Prikladnaya Diskretnaya Matematika 1 (2016), pp. 86–91. [SGV94] A. Sch¨ onhage, A. F. W. Grotefeld, and E. Vetter.Fast algorithms. A multitape Turing machine implementation...

    2016 doi

  19. [27]

    Two compact incremental prime sieves

    Lecture Notes in Comput. Sci. Springer, Berlin, 2006, pp. 193–207.isbn: 978-3-540-36075-9; 3-540-36075-1. doi:10.1007/11792086_15. [Sor15] J. P. Sorenson. “Two compact incremental prime sieves”. In:LMS J. Comput. Math.18.1 (2015), pp. 675–683.issn: 1461-1570.doi:10. 1112/S1461...

    2006 doi

  20. [28]

    Two fast parallel prime number sieves

    Lecture Notes in Comput. Sci. Springer, Berlin, 1998, pp. 179–195.isbn: 3- 540-64657-4.doi:10.1007/BFb0054861. [SP94] J. Sorenson and I. Parberry. “Two fast parallel prime number sieves”. In:Inform. and Comput.114.1 (1994), pp. 115–130.issn: 0890-5401,1090- 2651.doi:10.1006/in...

    1998 doi

  21. [29]

    Faster relaxed multiplication

    Graduate Studies in Mathematics. Ameri- can Mathematical Society, Providence, RI, 2015, pp. xxiv+629.isbn: 978-0-8218-9854-3.doi:10.1090/gsm/163. [Tit86] E. C. Titchmarsh.The Theory of the Riemann Zeta-function. Second. Edited and with a preface by D. R. Heath-Brown. The Clare...

    2015 doi

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.