STATISTICAL EVIDENCE FOR SMALL GENERATING SETS

For an integer n, let G(n) denote the smallest x such that the primes less-than-or-equal-to x generate the multiplicative group modulo n. We offer heuristic arguments and numerical data supporting the idea that G(n) less-than-or-equal-to (log 2) -1 log n log log n asymptotically. We believe that the coefficient 1/log2 is optimal. Finally, we show t he average value of G(n) for n less-than-or-equal-to N is at least (1 + o(l)) log log N log log log N, and give a heuristic argument that th is is also an upper bound. This work gives additional evidence, indepe ndent of the ERH, that primality testing can be done in deterministic polynomial time; if our bound on G(n) is correct, there is a determini stic primality test using O(log n)2 multiplications modulo n .