Explicit bounds for primality testing and related problems
Open accessThe DOI matches its Crossref record; 62 of the 66 references it cites were found in a registry or an index, and 4 are not checked yet; none of the 15 sources its claims cite is checked for support yet.
Abstract
Many number-theoretic algorithms rely on a result of Ankeny, which states that if the Extended Riemann Hypothesis (ERH) is true, any nontrivial multiplicative subgroup of the integers modulo m omits a number that is O ( log 2 m ) . This has been generalized by Lagarias, Montgomery, and Odlyzko to give a similar bound for the least prime ideal that does not split completely in an abelian extension of number fields. This paper gives a different proof of this theorem, in which explicit constants are supplied. The bounds imply that if the ERH holds, a composite number m has a witness for its compositeness (in the sense of Miller or Solovay-Strassen) that is at most 2 log 2 m .
Checked 2026-11-22 · 4 references not checked yet
Overview
CoChat Summary
TL;DR
Bach gives a new proof of the Ankeny and Lagarias–Montgomery–Odlyzko bounds for least nonresidues and least prime ideals outside subgroups, supplying explicit constants under the Extended Riemann Hypothesis. The bounds imply that, under ERH, a composite \(m\) has a Miller or Solovay–Strassen compositeness witness at most \(2(\log m)^2\).
Key findings
- Under ERH, if \(G\) is a nontrivial subgroup of \(\mathbb Z/(m)^*\) and \(n\in G\) for all positive \(n<x\), then \(x<2(\log m)^2\) (Theorem 2); if the condition holds only for \(n\) relatively prime to \(m\), then \(x<3(\log m)^2\) (Theorem 3).
- For a number field \(K\) of degree \(>1\), absolute discriminant \(A\), and nonprincipal character modulo \(\mathfrak f\), Theorem 4 gives: \(\chi(\mathfrak p)\ne 1\) for \(N\mathfrak p<3\log^2(A^2N\mathfrak f)\); \(\chi(\mathfrak p)\ne 0,1\) for \(N\mathfrak p<12\log^2(A^2N\mathfrak f)\); and \(\chi(\mathfrak p)\ne 0,1\) with \(\deg(\mathfrak p)=1\) for \(N\mathfrak p<18\log^2(A^2N\mathfrak f)\).
- The asymptotic Theorem 1 states \(N\mathfrak p_i<(1+o(1))\log^2(A_i^2N\mathfrak f_i)\) under ERH.
- Computations show that in Theorem 2 the constant “2” can be replaced by \(2/\log 3=1.657071\ldots\), which is best possible; Theorem 4 also implies the class group of a field of discriminant \(A\) is generated by prime ideals of norm at most \(12\log^2 A\), improved to \(<6\log^2 A\) in the quadratic case.
Methods
- Analytic number theory proof using an explicit formula for sums over prime ideals, Hecke \(L\)-functions, Stark’s formula, and a parameter \(a\) chosen to optimize constants under ERH.
- The rational case is treated separately via Dirichlet characters; the algebraic case uses general number fields and characters on ideals.
- Computations include programs to verify Theorem 3 for all \(m<10^6\), generate tables of constants \(C_1,C_2\), and use binary search/minimization to find good \(a\) values.
Limitations
- The results are conditional on ERH, which is unproved; the paper notes that a weaker zero-free strip would suffice for polynomial bounds, but even that is not known, and a Siegel zero would improve the ultimate bound.
- Even assuming ERH, the paper states it is open whether the estimates are of the right order of magnitude; numerical evidence suggests the least quadratic nonresidue grows no faster than a small constant times \(\log p\), and prime-testing evidence suggests perhaps \(O(\log n)\) for the least witness, while lower bounds are \(\Omega(\log p\log\log\log p)\) (Graham–Ringrose) and \(\Omega(\log p\log\log p)\) under ERH (Montgomery).
- The paper says no attempt was made to verify whether the best possible constant for Theorem 3 is also \(2/\log 3\); it also notes the algebraic-case bounds are less sharp because less is known about the relevant zeta and \(L\)-functions.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
0 Valid · 0 Not valid · 15 Not checked · 22 Own results and interpretations
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“X(p) t¿0, 1 occurs for Np < 121og (A A/f),”
§ EXPLICIT BOUNDS FOR PRIMALITY TESTING AND RELATED PROBLEMS > 7. Explicit bounds for the algebraic case
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“X(p) í 1 occurs for Np < 3 log (A A/f),”
§ EXPLICIT BOUNDS FOR PRIMALITY TESTING AND RELATED PROBLEMS > 7. Explicit bounds for the algebraic case
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Lemma 5.8 (RH).We have E A(P*)[1-X(PA)](^) log[^]<4n(v^4 0(x1/4)), degp>l where the constant implied by the “ O “ symbol is absolute.”
§ EXPLICIT BOUNDS FOR PRIMALITY TESTING AND RELATED PROBLEMS > 5. Detailed estimates
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Theorem 1 (ERH).For i = 1,2, ... let Kj be a number field whose discriminant has absolute value A;, with a nonprincipal character x¡ defined modulo , .. Let p( be a prime ideal of minimal norm such that yf,-(p(-) ^ 0, 1 and degp; = 1.Assume that A(./yf(.-> oo as i -► oo.Then Npi<(l+o(l))log2(A2N,i).”
§ EXPLICIT BOUNDS FOR PRIMALITY TESTING AND RELATED PROBLEMS > 4. AN ASYMPTOTIC BOUND
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Theorem 3 (ERH).Let G be a nontrivial subgroup of Z/(m)* such that n e G for all positive n < x relatively prime to m .Then x < 3(log m) .”
§ EXPLICIT BOUNDS FOR PRIMALITY TESTING AND RELATED PROBLEMS > 5. Detailed estimates
plain- Asserted: unclear — It is unclear whether the authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: unclear — It is unclear why the paper says it holds.
- Rests on an assumption not shown here.
8 more claims
Create a free account to see all 37 claims and to verify the 14 references still open.
- It may state two separate claims as one. 9
- The quote only partly states this claim. 7
- Probably not a substantial claim. 13
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ EXPLICIT BOUNDS FOR PRIMALITY TESTING AND RELATED PROBLEMS > 7. Explicit bounds for the algebraic case
“Rosser and Schoenfeld [37] give C = 1.03883.”
§ EXPLICIT BOUNDS FOR PRIMALITY TESTING AND RELATED PROBLEMS > References
“37. R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), 84-85.”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ EXPLICIT BOUNDS FOR PRIMALITY TESTING AND RELATED PROBLEMS > 1. Introduction
“A generalization of this, due to Lagarias, Montgomery, and Odlyzko [24]”
§ EXPLICIT BOUNDS FOR PRIMALITY TESTING AND RELATED PROBLEMS > References
“24. G. L. Miller, Riemann's hypothesis and tests for primality, J. Comput. System Sei. 13 ( 1976), 300-317.”
Citations
Cites
Handbook of Mathematical Functions
McQuarrie, D. A. (1966) · American Journal of Physics · doi:10.1119/1.1972842 · Cited by 40,433
Bhatia, R., Bredon, G. E., Walter, W. L., Rotman, J. J., Murty, M. R., Gilman, J., Walters, P., Golubitsky, M., Karatzas, I., Cohen, H., et al. (1977) · Cited by 8,252
The Feynman Lectures on Physics
Feynman, R. P., Leighton, R. B., Sands, M., & Treiman, S. B. (1964) · Physics Today · doi:10.1063/1.3051743 · Cited by 2,939
The feynman lectures on physics
De Shalit, A. (1967) · Journal of the Franklin Institute · doi:10.1016/0016-0032(67)90572-8 · Cited by 2,279
(1999) · Translations of Mathematical Monographs · doi:10.1090/mmono/186/05 · Cited by 2,093
Davenport, H. (1980) · Graduate Texts in Mathematics · doi:10.1007/978-1-4757-5927-3 · Cited by 1,893
Approximate formulas for some functions of prime numbers
Rosser, J. B., & Schoenfeld, L. (1962) · Illinois Journal of Mathematics · doi:10.1215/ijm/1255631807 · Cited by 1,546
Edwards, H. M. (1974) · Cited by 1,487
Lang, S. (1994) · Graduate texts in mathematics · doi:10.1007/978-1-4612-0853-2 · Cited by 1,304
Riemann's hypothesis and tests for primality
Miller, G. L. (1976) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(76)80043-8 · Cited by 856
Research works printed but not linked: 2
- Ingham, A. E., 1990, The distribution of prime numbers
- J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, in Algebraic Number Fields (A. Fröhlich, ed.), Academic Press, London, 1977.
Cited by
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Constructing elliptic curve isogenies in quantum subexponential time
Childs, A. M., Jao, D., & Soukharev, V. (2010) · Cited by 239
Constructing elliptic curve isogenies in quantum subexponential time
Childs, A., Jao, D., & Soukharev, V. (2014) · Journal of Mathematical Cryptology · doi:10.1515/jmc-2012-0016 · Cited by 200
Artin's Primitive Root Conjecture – A Survey
Moree, P. (2012) · Integers · doi:10.1515/integers-2012-0043 · Cited by 190
Factoring integers with the number field sieve
Buhler, J. P., Lenstra, H. W., & Pomerance, C. (1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091539 · Cited by 188
Metadata
- Authors
- Bach, E.
- Affiliations
- Royal Society (GB)
- Corresponding author
- Bach, Eric
- ORCID
- Bach, Eric
- Venue
- Mathematics of Computation
- Publisher
- American Mathematical Society (AMS)
- Published
- 1990
- Volume
- 55
- Issue
- 191
- Pages
- 355-380
- ISSN
- 0025-5718 (ISSN-L)
- 1088-6842
- OpenAlex
- W2011809718
- Semantic Scholar
- 42cc3b8f279ba771452289deea5476acdc5ea963
- Cited by
- 282
- References
- 58
- Citations by year
- 2026: 13 · 2025: 18 · 2024: 16 · 2023: 4 · 2022: 8 · 2021: 9 · 2020: 3 · 2019: 8 · 2018: 8 · 2017: 8 · 2016: 13 · 2015: 9 · 2014: 19 · 2013: 6 · 2012: 11
- FWCI
- 7.25
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Mathematics of Computation (publishedVersion)
- Funders
- National Science Foundation (8552596, 8504485)
- Topics
- Physical Sciences › Mathematics › Algebra and Number Theory › Analytic Number Theory Research
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Mathematics › Geometry and Topology › Algebraic Geometry and Number Theory
- Keywords
- primality testing, explicit bounds, extended Riemann hypothesis, abelian extensions of number fields, Miller-Rabin test, explicit constants
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
A language model drew the claims from the paper on 2026-11-21, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-11-21 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Explicit bounds for primality testing and related problems. https://app.cochat.ai/papers/10.1090/s0025-5718-1990-1023756-8
- The paper
- Bach, E. (1990). Explicit bounds for primality testing and related problems. Mathematics of Computation. https://doi.org/10.1090/s0025-5718-1990-1023756-8
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.