CoChat

Explicit bounds for primality testing and related problems

Open access
Bach, Eric · 1990 · Mathematics of Computation

The 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

Crossref · 10.1090/s0025-5718-1990-1023756-8

Cites

62 of 66 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 Valid · 0 Not valid · 15 Not checked · 22 Own results and interpretations

8 more claims

Create a free account to see all 37 claims and to verify the 14 references still open.

See all claims — free account
  • It may state two separate claims as one. 9
  • The quote only partly states this claim. 7
  • Probably not a substantial claim. 13

Create a free account to see these claims.

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.

2 of 2

Citations

Cites

Show all 66 references

Research works printed but not linked: 2

  1. Ingham, A. E., 1990, The distribution of prime numbers
  2. 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

See all 284

Metadata

Authors
Bach, E.
Affiliations
Royal Society (GB)
Corresponding author
Bach, Eric
Venue
Mathematics of Computation
Published
1990
Volume
55
Issue
191
Pages
355-380
ISSN
  • 0025-5718 (ISSN-L)
  • 1088-6842
OpenAlex
W2011809718
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
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.