Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Explicit bounds for primality testing and related problems

Author: Eric Bach
Journal: Math. Comp. 55 (1990), 355-380
MSC: Primary 11R44; Secondary 11Y11, 11Y40
MathSciNet review: 1023756
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11R44, 11Y11, 11Y40

Retrieve articles in all journals with MSC: 11R44, 11Y11, 11Y40

Additional Information

Keywords: Primality, Extended Riemann Hypothesis
Article copyright: © Copyright 1990 American Mathematical Society