Remote Access Mathematics of Computation
Green Open Access

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

Article copyright: © Copyright 1993 American Mathematical Society