Statistical evidence for small generating sets

Bach, Eric; Huelsbergen, Lorenz

doi:10.1090/S0025-5718-1993-1195432-5

Statistical evidence for small generating sets
HTML articles powered by AMS MathViewer

by Eric Bach and Lorenz Huelsbergen PDF

Math. Comp. 61 (1993), 69-82 Request permission

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 \[ 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 \[ (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

Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, DOI 10.1090/S0025-5718-1980-0583518-6
A. I. Borevich and I. R. Shafarevich, Number theory, Pure and Applied Mathematics, Vol. 20, Academic Press, New York-London, 1966. Translated from the Russian by Newcomb Greenleaf. MR 0195803
H. Brown and H. Zassenhaus, Some empirical observations on primitive roots, J. Number Theory 3 (1971), 306–309. MR 288072, DOI 10.1016/0022-314X(71)90004-7
D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. (3) 12 (1962), 179–192. MR 132732, DOI 10.1112/plms/s3-12.1.179
Herman Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952), 493–507. MR 57518, DOI 10.1214/aoms/1177729330
Harvey Cohn, A classical invitation to algebraic numbers and class fields, Universitext, Springer-Verlag, New York-Heidelberg, 1978. With two appendices by Olga Taussky: “Artin’s 1932 Göttingen lectures on class field theory” and “Connections between algebraic number theory and integral matrices”. MR 506156
Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR 606931
Robert E. Dressler, A property of the $\varphi$ and $\sigma _{j}$ functions, Compositio Math. 31 (1975), no. 2, 115–118. MR 392792
P. D. T. A. Elliott, The distribution of primitive roots, Canadian J. Math. 21 (1969), 822–841. MR 246835, DOI 10.4153/CJM-1969-092-6
P. D. T. A. Elliott, A problem of Erdős concerning power residue sums, Acta Arith. 13 (1967/68), 131–149. MR 220689, DOI 10.4064/aa-13-2-131-149
P. Erdös and M. Kac, The Gaussian law of errors in the theory of additive number theoretic functions, Amer. J. Math. 62 (1940), 738–742. MR 2374, DOI 10.2307/2371483

On a classical problem of probability theory

6A

Selected papers of Alfréd Rényi

William Feller, An introduction to probability theory and its applications. Vol. I, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020
S. W. Graham and C. J. Ringrose, Lower bounds for least quadratic nonresidues, Analytic number theory (Allerton Park, IL, 1989) Progr. Math., vol. 85, Birkhäuser Boston, Boston, MA, 1990, pp. 269–309. MR 1084186
E. J. Gumbel, Statistics of extremes, Columbia University Press, New York, 1958. MR 0096342
H. Halberstam, On the distribution of additive number-theoretic functions. III, J. London Math. Soc. 31 (1956), 14–27. MR 73627, DOI 10.1112/jlms/s1-31.1.14
D. R. Heath-Brown, Artin’s conjecture for primitive roots, Quart. J. Math. Oxford Ser. (2) 37 (1986), no. 145, 27–38. MR 830627, DOI 10.1093/qmath/37.1.27
Christopher Hooley, On Artin’s conjecture, J. Reine Angew. Math. 225 (1967), 209–220. MR 207630, DOI 10.1515/crll.1967.225.209
James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837–850. MR 1002631, DOI 10.1090/S0894-0347-1989-1002631-0
G. Kolesnik and E. G. Straus, On the first occurrence of values of a character, Trans. Amer. Math. Soc. 246 (1978), 385–394. MR 515545, DOI 10.1090/S0002-9947-1978-0515545-6
J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
D. H. Lehmer and Emma Lehmer, Heuristics, anyone?, Studies in mathematical analysis and related topics, Stanford Univ. Press, Stanford, Calif., 1962, pp. 202–210. MR 0144868
D. H. Lehmer, Emma Lehmer, and Daniel Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), 433–451. MR 271006, DOI 10.1090/S0025-5718-1970-0271006-X
Kevin S. McCurley, The least $r$-free number in an arithmetic progression, Trans. Amer. Math. Soc. 293 (1986), no. 2, 467–475. MR 816304, DOI 10.1090/S0002-9947-1986-0816304-1
Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
Albert W. Marshall and Ingram Olkin, Inequalities: theory of majorization and its applications, Mathematics in Science and Engineering, vol. 143, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR 552278
Harold Davenport, Multiplicative number theory, 3rd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York, 2000. Revised and with a preface by Hugh L. Montgomery. MR 1790423
Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0

The nth prime is greater than

45

Jonathan Sorenson and Ian Parberry, Two fast parallel prime number sieves, Inform. and Comput. 114 (1994), no. 1, 115–130. MR 1294306, DOI 10.1006/inco.1994.1082
A. J. Stephens and H. C. Williams, An open architecture number sieve, Number theory and cryptography (Sydney, 1989) London Math. Soc. Lecture Note Ser., vol. 154, Cambridge Univ. Press, Cambridge, 1990, pp. 38–75. MR 1055399

Bemerkung über die Auflösung quadratischer Congruenzen

D. Suryanarayana, On $\Delta (x,\,n)=\phi (x,\,n)$ $-x\phi (n)/n$, Proc. Amer. Math. Soc. 44 (1974), 17–21. MR 332636, DOI 10.1090/S0002-9939-1974-0332636-5
Stan Wagon, Primality testing, Math. Intelligencer 8 (1986), no. 3, 58–61. MR 846996, DOI 10.1007/BF03025793
Samuel S. Wagstaff Jr., Greatest of the least primes in arithmetic progressions having a given modulus, Math. Comp. 33 (1979), no. 147, 1073–1080. MR 528061, DOI 10.1090/S0025-5718-1979-0528061-7
A. E. Western and J. C. P. Miller, Tables of indices and primitive roots, Royal Society Mathematical Tables, Vol. 9, Published for the Royal Society at the Cambridge University Press, London 1968. MR 0246488