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)

 

Statistical evidence for small generating sets


Authors: Eric Bach and Lorenz Huelsbergen
Journal: Math. Comp. 61 (1993), 69-82
MSC: Primary 11N69
MathSciNet review: 1195432
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For an integer n, let $ G(n)$ denote the smallest x such that the primes $ \leq x$ generate the multiplicative group modulo n. We offer heuristic arguments and numerical data supporting the idea that

$\displaystyle G(n) \leq {(\log 2)^{ - 1}}\log n\log \log n$

asymptotically. We believe that the coefficient $ 1/\log 2$ is optimal. Finally, we show the average value of $ G(n)$ for $ n \leq N$ is at least

$\displaystyle (1 + o(1))\log \log N\log \log \log N,$

and give a heuristic argument that this is also an upper bound. This work gives additional evidence, independent of the ERH, that primality testing can be done in deterministic polynomial time; if our bound on $ G(n)$ is correct, there is a deterministic primality test using $ O{(\log n)^2}$ multiplications modulo n.

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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11N69

Retrieve articles in all journals with MSC: 11N69


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1993-1195432-5
PII: S 0025-5718(1993)1195432-5
Article copyright: © Copyright 1993 American Mathematical Society