Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1990-1023756-8
PII: S 0025-5718(1990)1023756-8
Keywords: Primality, Extended Riemann Hypothesis
Article copyright: © Copyright 1990 American Mathematical Society